基于群簽名的電子投票方案

喬匯東，胡 瑛

（湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭411104）

1 電子投票基本要求

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

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

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

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

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

3 準(zhǔn)備工作

3.1 知識(shí)簽名

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

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

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

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

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

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

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

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

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

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

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

3.2 基于知識(shí)簽名的群簽名方案

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

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

群管理員計(jì)算下列值：

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

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

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

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

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

（2）成員加入

要注冊(cè)成為一個(gè)成員，Alice首先計(jì)算她的成員密鑰：

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

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

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

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

（3）簽名

（4）驗(yàn)證

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

（5）打開簽名

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

4 新的電子投票方案

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

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

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

（3）群管理機(jī)構(gòu)GM，負(fù)責(zé)建立群，接收合法成員的加入請(qǐng)求，并給合法的選票予以注冊(cè)；

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

4.2 系統(tǒng)準(zhǔn)備

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

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

（2）注冊(cè)階段

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

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

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

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

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

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

（3）投票階段

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

5 安全性分析

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

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

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

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

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

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

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

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

6 結(jié) 論

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

［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］ 賴 瑾，范玉順.一種新的安全、實(shí)用的電子投票方案［J］.計(jì)算機(jī)科學(xué)，2003，30（1）：142－144.

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

［4］ 陳曉峰，王育民.基于匿名通訊信道的安全電子投票方案［J］.電子學(xué)報(bào)，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］.計(jì)算機(jī)學(xué)報(bào)，2003，26（5）：557－562.

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

［10］宋春來，殷新春，孟純煜.基于環(huán)簽名的安全電子投票方案［J］.計(jì)算機(jī)應(yīng)用與軟件，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.