無可信中心的電子投票方案

摘 要：給出一個無可信中心的電子投票方案，即使在管理機構和計票機構都不可信的情況下仍能夠保證投票的安全性。該方案能夠始終保證投票者的匿名性，即使選票公開，任何人都不能確定投票者的身份；解決了選票碰撞的問題，即不同的投票人必定產生不同的選票。

關鍵詞：電子投票； 雙線性映射； 可信中心

中圖分類號：TP309 文獻標志碼：A

文章編號：1001-3695(2008)07-2159-02



Electronic voting scheme without trustfulparty

WE Huaijian， BAO Wansu， WEI Yun， HUANG Xuxu， LU Mingwei



(Institute of Electronic Technology， PLA Information Engineering University， Zhengzhou 450004， China)



Abstract:This paperproposed an electronic voting scheme without a trustful party which was secure even if the managing centre and the tally were untrustworthy. The scheme could also provide unconditional anonymity of the voter. No one could determine the identity of the voter even published the vote. And solved the problem ofvoting collison in the scheme. Different voters generate different votes.

Key words： electronic voting； bilinear pairing； trustful party

電子投票是以密碼技術為理論基礎，通過計算機和網絡來完成投票的。與傳統的投票方式相比，電子投票的一個顯著優點是投票者無須到一個指定的投票中心投票，管理機構也無須進行選票發放，可以節省大量的人力和物力資源。

一個安全的投票方案應具有以下性質^[1]：

a）秘密性。除了投票者以外，選票的內容不能被其他人知道。

b）匿名性。任何人都無法將一張選票和某一投票者聯系起來。

c）惟一性。只有有資格的人能提交一張合法的選票，冒充他人選舉則一定能被追蹤到。

d）完整性。所有合法的選票都能被正確計入。

e）穩固性。不誠實的投票者不能破壞選舉。

f）可驗證性。選舉的結果可以被檢驗，任何人無法偽造選舉結果。狹義的可驗證性保證合法的選票被計入；廣義的可驗證性可以使任何感興趣的第三方參與檢驗，同時不泄露投票者的隱私。

按選票發送的方式可分為兩種^[1]：（a）投票者對選票進行加密后再發送選票；（b）投票者通過匿名的通信信道發送選票。Benaloh和Cranor等人^[2~4]提出了一些電子投票方案。然而，當選舉人數較多時數據的通信量和計算量太大，這些方案均不適合于大群體的選舉。1998年，Chaum^[5]和Ohta^[6]分別利用匿名通信信道給出了一個適合于大群體選舉的投票方案，而且保證了投票者的匿名性。但是這兩個方案都沒有解決選票的秘密性問題。當投票者發現自己的選票沒有被正確計入時，他必須通過公開選票來要求計票機構加入自己的選票，這樣就泄露了自己的選票，而且管理者可以知道選舉的一些中間結果，這樣他能通過泄露這些信息影響選舉的最終結果。Fujioka等人^[1]利用比特承諾協議和盲簽名技術提出了一個實用、秘密、適合大群體選舉的電子投票方案。該方案解決了投票者身份的匿名性問題，但是沒有解決選票碰撞的問題，即如果兩個投票者使用相同的隨機密鑰及以相同的方式投票，那么選票及簽名就完全一樣，于是計票機構去掉一些重復的選票而偽造另一些“合法的”的選票，但投票者無法察覺；并且該方案在計票時需要投票者提供自己的隨機密鑰k，如果投票者提供一個非法的密鑰，則對應的選票無法打開。

由于投票既要保證投票者的匿名性，又要使得每個投票者最多投一票，投票者必須既能讓計票中心對發送的投票有效性進行驗證，又能對計票中心和管理中心保持匿名性；而且當投票者多投票時，計票中心能夠辨認出投票的無效性。

文獻[7]中王育民等人提出了一個基于群簽名和時限承諾協議的電子投票方案。該方案在一定的時間段T內，能夠無條件地保證投票者的匿名性；但在時間段T后，管理中心仍能驗證投票者的身份，因此該方案不能真正保證投票者的匿名性。本文構造一個基于ID的電子投票方案，即使在管理中心和計票中心不可信的情況下也能夠滿足電子投票的安全性質，并且能夠始終保證投票者的匿名性。

1 相關定義

 以|G|表示群G的階，n為一整數，Zn表示模n的剩余類環，以‖表示兩個串的級連， H1、H2表示抗碰撞的哈希函數，Z表示整數。

定義1^[8] 設G1=〈P〉是一循環加群；q∈Z，|G1|=q，G2是一循環乘群；|G2|=q，a，b∈Z*q，對映射e∶G1×G1→G2，如果：

a）對于任意R，Q∈G1，有e(aR，bQ)=e(R，Q)ab；

b）存在R，Q∈G1，滿足e(R，Q)≠1，其中1為G2的幺元；

c）對于任意R，Q∈G1，計算e(R，Q)是可行的，則稱映射e為雙線性映射。

由定義1，顯然有e(aR，bQ)=e(R，abQ)=e(abR，Q)。

設G1=〈P〉是一循環加群，q∈Z，|G1|=q，若：

a）給定元素P，Q∈G，找到一個n∈Z*q，使得Q=nP，則稱其為DLP問題^[8]。

b）給定元素P、aP、bP，其中a，b∈Z*q，計算abP，則稱其為CDH問題^[8]。

c）給定元素P、aP、bP、cP，其中a，b，c∈Z*q，計算是否c≡ab mod q，則稱其為DDH問題^[8]。

定義2^[8] 如果群G1對于DDH問題能在多項式時間內解決，而DLP和CDH問題不能在多項式時間內解決，則稱G1為DiffieHellman群。

2 基于ID的電子投票方案

一個電子投票方案中參與者包括投票者Vi、管理機構A和計票機構 C。Vi和 C通過一個匿名的通信信道交換信息。

1)初始化 設G1=〈P〉是DiffieHellman群，|G1|=q，q是一素數，G2是一循環乘群，|G2|=q，e：G1×G1→G2是雙線性映射，H1：{0，1}*×G1→Zq和H2：{0，1}*×G1→G1是抗碰撞的哈希函數。

管理機構A的身份信息為ID∈Z*q，A選擇隨機數s∈Z*q，計算Ppub=sP，則A的公開密鑰為{G1，G2，e，q，P，Ppub，IDA，H1，H2}，秘密密鑰為s。

2)投票者加入 Vi首先將其身份信息IDi發送給管理機構A，A對該身份進行驗證后，如果Vi是合法的投票者，Vi選擇xi∈Z*q作為私鑰，計算

S=xiH2(IDA，xiP)，并將S發送給A，A計算Si=sS，并將Si發送給Vi，Vi把Si作為自己的投票密鑰。

最后機構A公布具有投票資格的投票者身份以及投票人數。

3)匿名投票 Vi進行投票時，首先選擇a∈RZ*q，計算U=axiH2(IDA，xiP)，V=xiH2(m，U)，h=H1(m，U+V)，W=aSi+hx-1iSi，則(m，U，V，W，xiP)為投票者Vi對m的投票。

4)驗證 計票機構C計算Q=H2(IDA，xiP)，h=H1(m，U+V)，H2(m，U)。若等式e(W，P)=e(U+hQ，Ppub），e(V，P)=e(H2(m，U)，xiP)成立，說明(m，U，V，W，xiP)是一個有效的投票。因為若等式e(W，P)=e(U+hQ，Ppub)

成立，即說明投票者擁有投票密鑰Si=sS；若等式e(V，P)=e(H2(m，U)，xiP)成立，則說明投票者擁有與xiP對應的秘密密鑰xi。

5)公布結果 C公布投票列表(m，U，V，W，xiP)及計票結果，每個投票者可以驗證他的投票是否在投票列表上，以確定自己的投票是否確實被計入選票。

3 安全性分析

該方案的安全性分析可分為以下六種情況：

a)投票者重復投票。投票者在加入過程中選擇的xiP為一定值，同一投票者重復投票產生的多個選票中xiP必定都相同，故當投票者Vi重復投票時，機構C可以驗證投票的無效性。

b)管理機構A進行投票。

若管理機構A進行投票，當機構C把投票結果公布時，就會出現投票數與投票人數不相等的情況，這只有一種情況：機構A進行投票，因為只有機構A知道秘密密鑰S。

c)管理機構A偽造投票者Vi進行投票。若管理機構A想假冒投票者Vi進行投票，則機構A必須知道Vi的xi。因為G1=〈P〉是DiffieHellman群，而

U=axiH2(IDA，xiP)，V=xiH2(m，U)，S=xiH2(IDA，xiP)，

在多項式時間內求解xi是不可行的，即在該方案中管理機構A不能偽造投票。

d)投票者偽造投票。

若投票者Vj不想用自己的投票密鑰進行投票，而想偽造投票，則Vj必須得到機構A的秘密密鑰。因為G1=〈P〉是DiffieHellman群，且Si=sS，在多項式時間內求解S是不可性行的，即在該方案中投票者不能偽造他人的投票。

e)投票者的匿名性。因為G1=〈P〉是DiffieHellman群，且

U=axiH2(IDA，xiP)，V=xiH2(m，U)，在多項式時間內求解S=xiH2(IDA，xiP)是不可行的，即該方案在投票結束后仍能保證投票者的匿名性。

f)選票碰撞。

在加入過程中，當Vi的xiH2(IDA，xiP）與Vj的xiH2(IDA，xiP）

相等時，管理機構A可以讓Vj重新選擇密鑰xj，計算新的xjH2(IDA，xjP)發送給管理機構A。這樣，對于每個投票結果，xiP都不相等，即不會產生選票碰撞的問題。

4 結束語

本文構造一個基于ID的電子投票方案。該方案即使在管理中心和計票中心不可信的情況下也能夠滿足電子投票的安全性質，且能夠始終保證投票者的匿名性，并解決了選票碰撞的問題。

參考文獻：

［1］ FUJIOKA A， OKAMOTO T，OHTA K. A practical secret voting scheme for large scale elections[C]// Proc ofWorkshop on the Theory and Application of Cryptographic Technigues. London:SpringerVerlag， 1992:244-251.

[2] BENALOH J C， YUNG M. Distributing the power of a government to enhance the privacy of voters [C]// Proc of the 5th Annual ACM Symposium on Principles of Distributed Computing. New York:ACM Press， 1986:52-62.

[3] CRANOR L. Electronic voting: computerized polls may save money， protect privacy [C]// Proc of Hawaii Internet of Conference on System Science. Hawaii:[s.n]，1997:116-124.

[4] SAKO K. Electronic voting system with objection to the centre [C]// Proc ofSymposium on Cryptography and Information Security. 1992:92-113.

[5] CHAUM D. Elections with unconditionally secret ballots and disruption equivalent breaking RSA [C]//Proc of EUROCYPT’88， LNCS 330. New York:SpringerVerlag，1998:177-182.

[6] OHTA K. An electronic voting scheme using a single administrator [C]// Proc of Spring National Convention Record. Berlin: IEICE，1988:A294.

[7] 陳曉峰，王育民.基于匿名通訊信道的安全電子投票方案[J].電子學報，2003，31（3）:390-393.

[8] CHEN Xiaofeng. A new IDbased group signature scheme from bilinear pairings [J].Journal of Electronics，2003(6):892-900.

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