喬匯東，胡 瑛

（湖南工程學院 計算機與通信學院，湘潭411104）

1 電子投票基本要求

通常認為，一個安全的電子選舉方案應該滿足如下七個方面的安全性.①完整性，即所有有效的選票都應當被正確統(tǒng)計；②堅固性，即無人能破壞選舉，合法選民可以退出投票而不會影響到投票的正常進行；③匿名性，即任何人都不能將選票與該選票的投票者對應起來；④唯一性 只有合法的投票者可以投一次票；⑤合法性，即有選舉權(quán)的投票人才能參加選舉的；⑥公正性，即無人能知道選舉的中間結(jié)果；⑦可驗證性，即投票人可以驗證自己的選票被統(tǒng)計到最后結(jié)果中.

電子投票發(fā)展至今，一些新的要求也出現(xiàn)在電子投票方案中，主要包括：①穩(wěn)固性，投票系統(tǒng)可以對一些局部錯誤進行容錯；②廣泛的可驗證性，所有人都可自行驗證投票是否公平進行；③無收據(jù)性，投票人不能向其他人證明自己投票的內(nèi)容.其中，無收據(jù)性的概念主要用于防范“選票收買”和“強迫投票”的違規(guī)行為，而這兩者是選舉舞弊的常見手段，因而，無收據(jù)性方面的研究得到了重視.

2 電子投票方案研究現(xiàn)狀

目前，主要電子投票系統(tǒng)有：基于同態(tài)加密的投票系統(tǒng)、基于匿名信道和盲簽名的投票系統(tǒng)、基于Mix－net的投票系統(tǒng)或者是基于秘密分享和安全多方計算的投票系統(tǒng).眾多電子投票方案中，F(xiàn)ujioka［1］等人提出的，基于盲簽名的投票系統(tǒng)被普遍認為是一個高效實用，最有代表性，且適合大群體選舉的電子投票方案，后續(xù)很多方案都借鑒了其中的一些方法，雖然這種投票機制一直被視為最具實用價值的，然而，后來的研究顯示它仍存在一些突出的缺點：驗證機構(gòu)權(quán)力過大；投票者在驗證機構(gòu)注冊之后如果放棄投票將會造成混亂；合法的選票之間可能會有重復；沒有投票人的協(xié)助無法打開選票.為了解決這些問題，賴瑾［2］等提出：設置發(fā)放唯一選票序列號的發(fā)放中心，以保證選票不發(fā)生碰撞；在驗證機構(gòu)設置多個驗證者，以門限多重簽名的方式受理投票者的注冊請求來防范驗證機構(gòu)可能存在的舞弊行為；設置監(jiān)票人監(jiān)督計票工作；允許最終投票的人數(shù)少于前去注冊登記的人數(shù)，權(quán)利機關(guān)此時有權(quán)補上這個差異以此解決中途棄權(quán)的問題.馮澤濤［3］的方案則以多重驗證、可驗證的投票編號等技術(shù)來解決簽證人欺詐和選票碰撞問題.而陳曉峰［4］等則在他們的方案里采用時限比特承諾解決了沒有投票人的協(xié)助無法打開選票的問題.總的來說，對于管理者的信任仍是這些投票方案的安全基礎，而這一點對于很多選舉來說顯然并不合適，另外，大部分此類方案中無收據(jù)性也沒有得到實現(xiàn).無收據(jù)性的概念由Benaloh［5］提出，利用高度剩余加密技術(shù)，他在其論文中首次給出了基于特定物理假設voting booth的無收據(jù)投票方案，但Martin［6］隨后證明了在多個計票機構(gòu)情況下，其方案不滿足無收據(jù)性.Lee［7］則提出了用“可信賴第三方”來實現(xiàn)無收據(jù)，其投票方案基于同態(tài)加密實現(xiàn)，但這種完全的信任被陳曉峰［8］等認為是不合適的，后者同樣使用同態(tài)加密提出了一個較為完備的基于半信任模型的無收據(jù)投票系統(tǒng)，然而，其方案中管理機構(gòu)和投票者之間的交互比較頻繁，方案步驟一定程度上取決于候選人的數(shù)量，如果候選人較多，則每個投票者都需要和管理機構(gòu)進行多次交互才能完成選票的產(chǎn)生，這些情況使得該方案在大群體選舉中并不合適.無收據(jù)性從邏輯上來說也常常和可驗證性等問題的解決有一定的沖突，無收據(jù)要求不能證明選票內(nèi)容，而可驗證要求能驗證投票結(jié)果，這使得兩者常不可兼得，比如在一些基于同態(tài)和門限簽名的方案中，實現(xiàn)了無收據(jù)，然而卻無法防止計票機構(gòu)的舞弊行為，因為投票者無法監(jiān)督具體到自己的每一票的開票結(jié)果，而無收據(jù)性問題的要求非常高，目前大部分方案實現(xiàn)仍然是困難的.

隨著研究的發(fā)展，一些新的方案中，也開始以群簽名和環(huán)簽名來構(gòu)造投票系統(tǒng)，如陳曉峰［4］等提出的方案使用了群簽名和知識簽名，崔國華［9］等則利用了群簽名的推廣列表簽名，而宋春來［10］提出的方案使用了環(huán)簽名.群簽名和環(huán)簽名由于其本身的匿名性為電子投票帶來了主要便利，而鏈式環(huán)簽名同時還解決了唯一性問題，保證了投票者無法多投選票.但環(huán)簽名方案效率偏低，每次簽名產(chǎn)生與簽名驗證過程需要使用該環(huán)中所有成員的公鑰逐一進行運算，如果成員較多，其運算量很大，若成員太少又有可能容易暴露投票者的信息，通常要以之實現(xiàn)大群體的投票是困難的.由于一個完備的群簽名通常具備匿名、不可偽造、不可關(guān)聯(lián)、抗聯(lián)合攻擊、可跟蹤等特性，使得群簽名方案比較適合用來作為構(gòu)造電子投票系統(tǒng)的基礎.以知識簽名構(gòu)造的群簽名方案通常在實現(xiàn)群簽名的各項性能上表現(xiàn)良好，其研究也十分活躍，在這些方案中選擇的合適方案做為構(gòu)造電子投票系統(tǒng)的基礎更為可行.

3 準備工作

3.1 知識簽名

知識簽名由Camenisch［11］提出，并在后續(xù)的研究中逐步完善，主要知識簽名形式有：

定義：滿足等式c＝H（m‖y‖g‖gsyc）的數(shù)組（c，s），即為關(guān)于消息m的y以g為底的離散對數(shù)的知識簽名，表示為：SPK｛α：y＝gα｝（m），其中希臘字母α表示簽名者持有的秘密，符號｜｜表示二進制串連接符，H 表示安全Hash函數(shù)H：｛0，1｝＊→｛0，1｝k.

這樣一個知識簽名（c，s）只有在知道秘密x＝loggy的情況下才能生成，當知道x的值時，簽名者隨機選取r∈Z＊n，然后進行計算：c＝H（m）‖y‖g‖gr），s＝r－cx mod n ，就可以得到簽名（c，s），能生成這樣一個簽名說明了簽名者知道y以g為底的離散對數(shù)x，不知道x的情況下任何人想偽造一個簽名都必須能夠解決離散對數(shù)問題，所以這樣一個知識簽名可以證明y是由某個以g為底的離散對數(shù)x生成的gx，并且簽名者知道關(guān)于y＝gx的秘密值x.在文獻［11］中Camenisch還給出了其他知識簽名，包括：

關(guān)于消息m的y以g，h為底的離散對數(shù)的知識簽名：

SPK｛（α，β）：y＝gahβ｝（m），（α，β）表示簽名發(fā)出者所持有的秘密；

關(guān)于消息m的y以g為底和z以h為底的離散對數(shù)的知識簽名：

SKREP［α：y＝gg∧z＝hα］（m）；

關(guān)于消息m的y以g為底的離散對數(shù)的e次方根的知識簽名：

SKROOTLOG［α：y＝gαe］（m）；

關(guān)于消息m的且v有著形式v＝hαgβe的知識簽名：

E－SKROOTREP［（α，β）：v＝hαgβe］（m）.

3.2 基于知識簽名的群簽名方案

基于知識簽名方案中，比較著名的有CS97和ACJT［12］等經(jīng)典方案，很多其方案也是以它們?yōu)榛A進行改進得到的，CS97群簽名方案由Camenisch在文獻［11］中提出，其基本步驟如下：

（1）系統(tǒng)建立

群管理員計算下列值：

①一個RSA模n及兩個公開的指數(shù)e1，e2＞1，其中e2與φ（n）互素，e1，e2應較小.

②兩個整數(shù)f1，f2＞1，并且在不知n的因子分解時計算其e1次根及e2次根是困難的.

③階為n的循環(huán)群G＝〈g〉，使得在G中計算離散對數(shù)是困難的.

④一個參數(shù)h∈G，使得計算h關(guān)于g的離散對數(shù)是困難的.

⑤選取一個隨機數(shù)ρ∈Z＊n，計算yR＝hρ作為群管理員的公開密鑰.群組的公開密鑰Y＝（n，e1，e2，f1，f2，G，g，h，yR），保留ρ和n 的素因子作為群管理員的秘密私鑰.

（2）成員加入

要注冊成為一個成員，Alice首先計算她的成員密鑰：

y＝xe1mod n其中x隨機選取自，z＝gy公開z作為Alice的公鑰

為了防止群管理者知道秘密y，Alice需要采用盲簽名的方法來發(fā)送她的加入請求，Alice計算：

U ＝ E－SKROOTLOG［α：z＝gαe1］（‘’）

V＝E－SKROOTLOG［β：g～y＝（zf1gf2）βe2］（‘’），‘’表示空字符

（3）簽名

（4）驗證

驗證者只要驗證3個知識簽名V1，V2，V3通過就可以認為簽名，d，V1，V2，V3）是一個合法的群簽名.簽名V1，V2說明了簽名者有能力給出等式mod n＝（f1βe1＋f2）mod n，從而驗證了簽名者的身份，簽名V3保證了這個簽名是可以被群管理者打開的，所以當3個知識簽名都驗證通過，這個群簽名為有效.

（5）打開簽名

因為簽名V3證明了d＝y(tǒng)Rε和＝hεgζ，所以群管理者可以計算：z＝／d1／ρ恢復出簽名者使用的公鑰z，找到簽名者，并且用知識簽名SKREP［α：h＝y(tǒng)Rα∧＝zdα］（‘’）在不泄露ρ的情況下向他人證明.

4 新的電子投票方案

4.1 系統(tǒng)參與者說明

（1）投票群G，一個由有權(quán)參加投票的人構(gòu)成的群；

（2）群中成員Vi，i＝1，2，…；

（3）群管理機構(gòu)GM，負責建立群，接收合法成員的加入請求，并給合法的選票予以注冊；

（4）計票機構(gòu)C，負責解開選票、統(tǒng)計選舉結(jié)果.

4.2 系統(tǒng)準備

（1）系統(tǒng)初始化階段

系統(tǒng)初始化階段由GM以群管理者的角色完成群的建立和成員加入步驟，基本步驟按照CS97群簽名方案完成.只是在成員加入時，需要GM進行身份的審核，確保擁有投票資格的合法成員才能加入群內(nèi).成員加入完成后，GM將加入成員名單發(fā)布到電子公告牌，如無異議則進入下一階段.

（2）注冊階段

此階段各成員將構(gòu)造自己的選票，并向GM和計票中心C注冊選票.在此次投票的注冊開始時，GM將首先產(chǎn)生選取自的隨機數(shù)rGM，并秘密保存.

投票者Vi構(gòu)造選票，Vi首先確定其選擇的結(jié)果resulti，這應是一個說明Vi最終投票結(jié)果的信息，接著Vi應對resulti添加不定數(shù)量的冗余信息，如時間，地址，或其他任何隨機添加的各種冗余信息，形成vi，但要保證resulti仍能從vi中被正確的識別出來.這個過程我們這里描述為算法diverse（result，r1，r2，r3，…，rn），其特點是無論參數(shù)result或ri，i＝1，2，…，n，n，哪個發(fā)生變化，都將使d＝diverse（result，r1，r2，r3，…，rn）計算得到的d 不同，然而，如果使用算法result＝conclude（d）進行逆向處理，總是能夠得到原參數(shù)中的第一個參數(shù)result，即：

此時，Vi利 用 算 法diverse（resulti，r1，r2，r3，…，rn）得到vi，并秘密保存.這里的ri，i＝1，2，…，n指代各種冗余信息的加入，這一構(gòu)造選票的過程是為了確保這樣一個事實：即使Vi投票的結(jié)果resulti已知，其他人仍無法推斷出Vi所使用的選票vi，因為其他人無法知道vi形成過程中使用了哪些ri參數(shù)，而算法conclude又保證任何人在需要的時候可以檢驗選票vi中包含的投票結(jié)果是否為resulti.另外，Vi需要對自己的選票vi負責，如果形成無法conclude或錯誤conclude的結(jié)果，他的選票將作廢或被錯記.然后Vi計算得到待注冊的選票信息mi＝H（vi）Rie1mod n，其中Ri為取自Z＊n的隨機數(shù).接著，Vi對mi進行群簽名，得到Sig（mi）后發(fā)送分組（mi，Sig（mi）Vi）給 GM.

GM驗證簽名，驗證失敗則拒絕此分組，應用簽名打開步驟計算此成員的公鑰，以判斷此成員之前有無發(fā)出過注冊選票，如沒有則補充證據(jù)si，即產(chǎn)生知識簽名si＝SKREP［α：h＝y(tǒng)Rα∧～z＝zdα］（mi），接收注冊選票并保存分組（mi，Sig（mi）vi，si），并將此簽名的公鑰zi發(fā)往電子公告牌.

GM對mi進行下面的計算：wi＝mod n，ti＝gwi，ci＝wirGMmod n，并產(chǎn)生知識簽名：sli＝ESKROOTREP［α：gmi ＝gαe1∧ti＝gα］（‘’），s2i＝SPK｛β：gci＝tiβ｝（‘’）和s3i＝SPK｛β：gci－1＝ti－1β∧gci＝tiβ｝（‘’），ci－1，ti－1指的是 GM 計算給上一位投票者的同類參數(shù)，可以在電子公告牌上查詢.然后將（ci，ti）發(fā)送給電子公告牌并入對應的簽名一欄.接著 GM 發(fā)送分組（ci，ti，s1i，s2i，s3i）給Vi.

Vi收到分組（ci，ti，s1i，s2i，s3i）后，驗證知識簽名s1i，s2i，s3i確 認ci是否為：ci＝md1irGMmod n的形式，以及參數(shù)rGM是否和上一位投票者相同，驗證失敗Vi將公布（ci，ti，s1i，s2i，s3i）進行抗議，并要求重新注冊.若驗證通過，則計算：votei＝ciR－1i，秘密保存注冊選票votei.

（3）投票階段

計票中心C宣布投票開始后，GM把rGM秘密發(fā)送給C，投票者Vi將自己的選票（vi，votei）通過匿名信道秘密提交給C，C執(zhí)行驗證：svotei＝voteir－1GMmod n，（svotei）e1如果和 H（vi）相等，則通過驗證，否則拒絕選票.對于通過驗證的選票vi，C計算resulti＝conclude（vi），把resulti結(jié)果統(tǒng)計到選票當中，并把（svotei，vi，resulti），同時發(fā)送到電子公告牌，如投票者Vi發(fā)現(xiàn)自己的選票vi沒有出現(xiàn)在電子公告牌上，將提出抗議.當投票時間截止后，計票中心C宣布最后的統(tǒng)計結(jié)果.

5 安全性分析

合法性：群成員都是經(jīng)過身份核實而加入群中的，群外的非法攻擊者無法產(chǎn)生有效的群簽名，從而杜絕了外部攻擊，而群內(nèi)部，即使是群管理者GM也無法模仿某個群成員發(fā)出簽名.

完整性：每一張合法的選票都會被群中心C計入.由于使用了diverse算法，即使投票者們選擇的結(jié)果resulti相同，但他們的選票vi也不會相同，所以vi的差別性保證了任何人都可以通過查看電子公告牌上的選票記錄確定自己的票是否被統(tǒng)計，從而使得C無法隱匿選票.

可驗證性：一方面投票者能通過電子公告牌查看自己的選票，另一方面其他任何人也可以通過（svotei，vi，resulti）校驗選票的最終合法性，公告的最終統(tǒng)計結(jié)果能接受所有人的檢驗.

公平性：在選舉過程中，由于選票始終處于盲化因子Ri和rGM的保護下，使得選票情況無法解讀，即使GM也無法獲知選舉情況.

堅固性：使用電子公告牌公示群成員后，GM在投票開始前無法虛構(gòu)成員加入群，注冊階段，由于簽名打開部分的驗證功能，所以不知道其他成員的密鑰情況下，任何人包括GM也無法冒充其他人簽名.注冊過程中GM向投票者發(fā)放的知識簽名證明了GM注冊選票行為的規(guī)范，避免了GM故意破壞選舉的可能，同時由于每張注冊選票的rGM都相同，也避免了在開票階段，GM利用特殊盲化因子影響選舉的可能.

匿名性：由于使用了盲化因子和匿名信道，在最后解開選票后，即使是計票中心和群管理者聯(lián)合起來，也無法從選票本身聯(lián)系到投票者的身份.GM雖然可以在注冊階段跟蹤投票者，卻無法將最終選票和注冊選票聯(lián)系到一起，從而實現(xiàn)了投票者的匿名性.

唯一性：利用群方案中打開簽名的操作，GM可以識別成員有否反復投票，重復或多投的票都將被拒絕.

無收據(jù)性：投票者無法向別人證實電子公告牌上最終選票中哪張是自己的，同時，在注冊階段后他所持有的待提交的選票votei，其內(nèi)容也包含盲化因子rGM，因此他也無法向其他人證明votei中的內(nèi)容.但此方案無法避免強迫投票，并且如果候選人和GM勾結(jié)，那候選人也可以令投票者證實其votei中的投票內(nèi)容從而達成選票的買賣.

6 結(jié) 論

本文在群簽名的基礎上提出了一個利用知識簽名、盲簽名和匿名信道構(gòu)造的一個較為安全的投票系統(tǒng)，系統(tǒng)具備大部分傳統(tǒng)方案的優(yōu)勢，也考慮了無收據(jù)性等較強的要求，實現(xiàn)了一個較為可靠的電子投票方案.

［1］ Fujioka A ，Okamoto T，Ohta K.A Practical Secret Voting Scheme for Lage Scale Elections［C］.AUSCRYPT＇92.LNCS 718，Berlin，Springer－verlag，1993：244－251.

［2］ 賴 瑾，范玉順.一種新的安全、實用的電子投票方案［J］.計算機科學，2003，30（1）：142－144.

［3］ 馮澤濤.一個改進的匿名電子投票方案［J］.計算機安全，2007，（4）：38－41.

［4］ 陳曉峰，王育民.基于匿名通訊信道的安全電子投票方案［J］.電子學報，2003，31（3）：390－393.

［5］ Benaloh J，Tuinstra D.Receipt－free Secret－ballot Ellections［C］.In Proceeding of the 26th Symposium on The Theory of Computing（STOC＇94），Montreal，1994：544－553.

［6］ Martin H，Sako K.Efficient Receipt－free Voting Based on Homomorphic Encryption［C］.EURO－CRYPT＇00.LNCS 921，Berlin，Springer－verlag，2000：393－403.

［7］ Lee B，Kim K.Receipt－free Electronic Voting through Collaboration of Voter and Honest Verifier［C］.In：Proceeding of JWISC2000，Okinawa，Japan，2000：101－108.

［8］ 陳曉峰，王繼林，王育民.基于半信任模型的無收據(jù)的電子投票［J］.計算機學報，2003，26（5）：557－562.

［9］ 崔國華，汪 洋，粟 栗.基于列表簽名的安全電子投票方案［J］.計算機工程與科學，2008，30（1）：4－7.

［10］宋春來，殷新春，孟純煜.基于環(huán)簽名的安全電子投票方案［J］.計算機應用與軟件，2008，25（5）：29－30.

［11］ J.Camenisch.Efficient and Generalized Group Signatures［C］.In：W.Fumy，eds.Advances in Cryptology－EUROCRYPT＇97，LNCS 1233，Springer－Verlag，1997：465－479.

［12］ G.Ateniese，J.Camenisch，M.Joye，G.Tsudik.A Practical and Provably Secure Coalition－resistant Group Signature Scheme［C］.In：Advances in Cryptology－CRYPTO＇00，LNCS 1880，Springer－verlag，2000：255－270.