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

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

關(guān)鍵詞：電子表決； 自組織群體； 匿名服務(wù)； 電子政務(wù)

中圖法分類號：TN96；TP309.2文獻(xiàn)標(biāo)識碼：A

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

1引言

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

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn)：

［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.

作者簡介：

周克復(fù)(1978)，男，四川綿陽人，助教，碩士研究生，主要研究方向為密碼學(xué)與網(wǎng)絡(luò)安全；

王尚平（1962），男，陜西扶風(fēng)人，教授，博士，主要研究方向為密碼學(xué)與網(wǎng)絡(luò)安全；

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

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