一個無可信第三方的自組織群體中匿名表決方案

摘要：在一個自組織群體中，成員之間是平等的關系，沒有管理者或可信的第三方，典型的網絡環境如移動Ad hoc網。給出了這種環境下匿名表決的形式化模型和安全定義，提出了一個具體方案， 基于RSA假設和離散對數困難性假設，在此安全定義下證明了方案的安全性。該方案允許參與者對某問題匿名表決，安全地計算表決結果，參與者之間也不需要任何交互，而且表決協議很容易轉換為一個匿名的門限簽名方案，在Ad hoc網中保護用戶的隱私。

關鍵詞：電子表決； 自組織群體； 匿名服務； 電子政務

中圖法分類號：TN96；TP309.2文獻標識碼：A

文章編號：1001－3695(2007)01-0152－03

1引言

與傳統的選舉方式相比，電子投票的一個顯著優點是投票者無須到指定的投票地點投票。隨著Internet的迅速發展，電子投票已成為電子政務的一項重要內容，許多學者對此作了大量研究[1~6]，已有一些用于電子選舉的系統推出。瑞士日內瓦州政府最近推出了一個電子投票網站，鼓勵本州居民嘗試在線投票，專家希望借此降低政府的投票開支。1998年，Eletion.com公司在亞尼桑拉州進行了一次電子選舉試驗，選民只需要點擊兩三次鼠標就可以完成投票。Election.com公司的競爭對手，華盛頓州的Votehere.net向阿拉斯加州的非正式民意調查提供了網上投票系統。過去阿拉斯加州有三個地區的投票率非常低，因為那里冬季一天有20個小時處于黑夜，雪天更是妨礙了人們參與選舉，通過網絡投票可以大大降低政府用于選舉的投資，增加了選民，特別是偏遠地區的選民參與國家活動的機會。Votehere還為各種協會、聯盟和大學提供遠程選舉服務。戴爾公司已經在銷售Hart InterCivic公司開發的電子投票系統，該系統可以簡化投票過程并很快統計出投票結果，該系統還增加了一些額外的功能，如使視力障礙者和殘疾人也可以方便地投票。2000年2月在華盛頓成立了Internet投票技術聯盟，從事開發用于Internet投票的技術標準。

然而目前的電子投票系統都有一個可信的第三方或半可信的第三方，在一些環境下，這樣的第三方并不存在，如移動Ad hoc 網絡[7]環境。考慮下面一個場景，一個自組織的委員會（如一個民主評議委員會，此時每一個成員就評議地位而言應該是平等的）要對某問題表決，希望成員發表對問題的真實看法。首先這里沒有可信任的管理者；其次，如果要求成員公開發表意見或不能提供發言者的匿名性，那么很難保證成員愿意發表自己的真實意見，因為事實上考慮到以后的個人利益，成員更樂意去猜度領導人或其他成員的意見。顯然，我們更需要的是一種合理表決機制的設計，而不能完全依靠思想教育鼓勵參與者發表真實意見。這樣一種在沒有可信第三方的環境下的匿名表決機制不僅僅可以用于上述應用，還可以用于如移動Ad hoc 網中的門限匿名簽名，以保護用戶隱私。這里設計的困難在于既要保證表決者的匿名性和決議的不可偽造性，又要保證能夠識別不同的決議來自不同的表決者，而且沒有第三方的幫助。本文給出了這樣一種表決機制，在這種環境下匿名表決的形式化模型和安全定義，提出了一個具體方案，并在此安全定義下證明方案的安全性質。該方案允許參與者對某問題進行匿名表決，安全地統計表決結果，而且本文的表決協議很容易轉換為一個匿名的門限簽名方案，在電子商務中保護用戶的隱私。

2匿名表決的形式化模型和安全定義

目前在使用密碼技術設計電子商務或電子政務的安全應用中，大多僅僅給出了方案的設計，而沒有形式化地設計模型。這些方案的分析也是非正式的，往往憑借的是設計者的直覺和經驗，不能給出正式的安全性證明，難以保證方案的安全性。這里首先給出匿名表決的形式化模型和安全定義，其中，一個表決者的功能用一個多項式時間圖靈機或算法來模擬。

注意到在上述表決協議中，每個表決者的身份是匿名的，但不同表決者是可以區分的。如果表決的意見是任意的消息，那么該方案自然地轉換為一個無須第三方的門限匿名簽名方案，而且可以隨著安全要求方便地改變門限，這可以用于電子商務中保護用戶的隱私。最后，無論是形成決議還是統計結果，協議都是非交互的，遵從了現實中人們發表了意見就離開的設計原理。對于每一個表決者，本文方案的計算復雜性為O(n)次模指數運算，數據復雜性為O(nl)bits，其中l為RSA模數和公用模數P的二進制表示的最大者，一般為1 024bits。從實現來看，對于1 000個參與者以下規模的組織，完成一次表決在個人計算機上只需幾分鐘，發送的數據大約為0.1MB，因此本文的方案是實用的。

5結束語

本文在參與者具有對等關系的組織中，對沒有可信任的第三方環境下的匿名表決，給出了電子表決方案的形式化模型。基于RSA函數的逆和離散對數困難性假設，提出了一個具體的匿名表決方案，在相應的安全定義下證明了方案的安全性。而且該方案很容易轉換為一個無須第三方的門限匿名簽名方案，可以隨著安全要求方便地改變門限，用于電子商務中保護用戶的隱私。效率分析表明本文方案是實用的。

參考文獻：

［1］J Belnaloh， M Yung. Distributing the Power of a Government to Enhance the Privacy[C]. Proceedings of the 5th ACM on Distributed Computing， 1986.5262.

［2］T Asano， T Matsumoto， H Imai. A Study on Some Schemes for Fair Election Secret Voting[C]. Proceedings of the 1991 Symposium on Cryptography and Information Security， 1991.

［3］K Sako. Electronic Voting Schemes Allowing open Objection to the Tally[J]. IEICE， 1994，E77A(1)：2430.

［4］K Sako， J Kilian. Secure Voting Using Partially Compatible Homomorphism[C]. CRYPTO’94， SpringerVerlag，1994.411424.

［5］T Okamoto. Receiptfree Electronic Voting Schemes for Largescale Elections[C]. Proc. of Workshop on Security Protocols’97， Sprin￣gerVerlag，1997.2535.

［6］H Martin， K Sako. Efficient Receiptfree Voting Based on Homomorphic Encryption[C]. Proceedings of Eurocrypt’00， SpringerVerlag， 2000.393403.

［7］L Zhou， Z Haas. Securing Ad hoc Networks[J]. IEEE Network， 1999，13(6)：2430.

［8］S Goldwasser， S Micali， R Rivest. A Digital Signature Scheme Secure Against Adaptive Chosenmessage Attacks[J]. SIAM Journal of Computing， 1988，17(2)： 281308.

［9］M Abe， M Ohkubo， K Suzuki. 1outofn Signatures from a Variety of Keys[C]. Proceedings of ASIACRYPT’02， SpringerVerlag， 2002.415432.

作者簡介：

周克復(1978)，男，四川綿陽人，助教，碩士研究生，主要研究方向為密碼學與網絡安全；

王尚平（1962），男，陜西扶風人，教授，博士，主要研究方向為密碼學與網絡安全；

梁小龍（1982），河北秦皇島人，本科生。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文