劉 高，劉憶寧，王 東

(1.桂林電子科技大學數(shù)學與計算科學學院，廣西 桂林 541004;2.桂林電子科技大學廣西可信軟件重點實驗室，廣西 桂林 541004)

一種可驗證的多候選人電子投票方案*

劉 高1，劉憶寧2，王 東1

(1.桂林電子科技大學數(shù)學與計算科學學院，廣西 桂林 541004;2.桂林電子科技大學廣西可信軟件重點實驗室，廣西 桂林 541004)

電子投票相對傳統(tǒng)投票具有安全、便捷、低成本的優(yōu)勢，近年來得到了廣泛的關(guān)注。2012年孫培勇等人提出了基于多方求和的多候選人電子投票方案。經(jīng)分析發(fā)現(xiàn)該方案不滿足可驗證性，給出了一種具有可驗證性的多候選人電子投票方案，保證計票結(jié)果的不可欺騙性。

電子投票；安全多方求和；隨機數(shù)；可驗證性；不可欺騙性

1 引言

電子投票(E-voting)可有效解決傳統(tǒng)投票方案中的效率低下、程序繁瑣等問題，因而受到了各方的關(guān)注，但同時，如何保證電子投票中的安全性是一個重要的研究領(lǐng)域。為了實現(xiàn)電子投票方案的安全性，主要依靠密碼技術(shù)等手段。1981年，一種相對傳統(tǒng)投票方式具有高效、節(jié)能、方便的電子投票方案[1]被提出來，隨著電子投票不斷深入實際應用，更多的安全性質(zhì)被提出來。比如無收據(jù)性 (投票者不可獲得或構(gòu)造使得賄選者確信的選票收據(jù))[2]、選票的完全保密性、計票的公平性和無爭議性[3]。形式上，電子投票可分為“二選一”(1-out-of-2)、“多選一”(1-out-of-m)和“多選多”(k-out-of-m)等。除了同態(tài)加密，多數(shù)加密算法不能對加密后的數(shù)據(jù)進行操作，從而限制了候選人數(shù)，一般處理的是“二選一”選舉方式。1996年多候選人選舉問題[4]被首次提出。隨后一種基于ElGamal同態(tài)加密系統(tǒng)的“1-out-of-m”多候選人投票方案[5]被提出，但其計算復雜度太高，并且不能進行“k-out-of-m”多候選人選舉。2001年，一種基于Paillier密碼體制的“k-out-of-m”投票方案[6]被提出，該方案不能杜絕某個投票者對同一個候選人重復投票現(xiàn)象，并且對計票中心和投票者造成大量計算負擔，使得該方案不能實際應用。2006年，仲紅等提出一種基于多精度計算[7]和安全多方求和協(xié)議[8]的無可信第三方“k-out-of-m”多候選人選舉方案[9]，并稱其滿足選票的完全保密性、無收據(jù)性、健壯性、公平性、無爭議性和高效性。2011年，劉憶寧等人[10]提出一種改進的電子投票方案，該方案利用拉格朗日插值代替可信第三方產(chǎn)生隨機數(shù)，并且繼承了Bingo voting的安全性質(zhì)，具有更好的健壯性。隨后孫培勇等人[11]分析發(fā)現(xiàn)其不滿足完全保密性，并且提出改進的多候選人選舉方案，利用隨機數(shù)對每個投票者的選票進行“盲化”，實現(xiàn)選票完全保密性。

但是，分析發(fā)現(xiàn)孫培勇等人提出的多候選人選舉方案不滿足可驗證性[12]，從而不能保證計票結(jié)果的不可欺騙性。為了解決這一安全隱患，基于離散對數(shù)困難性問題，我們提出了一種可驗證的多候選人電子投票方案以保證可驗證性，實現(xiàn)了所計票數(shù)的不可欺騙性。

2 孫-劉電子投票方案及安全性分析

2.1 孫-劉電子投票方案

在本地表決階段，投票者Pi(i=1,2,…,n)生成選票，為mk位二進制序列00…0a100…0a2…00…0am，其中aj=0或1代表對Cj(j=1,2,…,m)的贊同或反對，并將該二進制序列轉(zhuǎn)化為十進制數(shù)vi。

Figure 1 Transfer matrix

圖1 傳送矩陣

2.2 孫-劉電子投票方案的安全性分析

3 一種改進的多候選人投票方案

(1)本地表決。

每個投票者Pi(i=1,2,…,n)對Cj(j=1,2,…,m)進行表決。設(shè)置aj=1表示贊成，反之，設(shè)置aj=0表示否定，再將對所有候選人的選票按照順序組成一個mk位二進制序列00…0a100…0a2…00…0am。最后將該二進制序列轉(zhuǎn)化為十進制數(shù)vi。

(2)發(fā)送選票。

(3)統(tǒng)計選票。

4 改進方案的安全性分析

該方案繼承了孫-劉方案的安全性質(zhì)，基于離散對數(shù)難題，每個投票者將自己的選票和隨機數(shù)“分類”，并且通過安全信道發(fā)送“分類結(jié)果”給其他投票者。然后每個投票者累積“分類結(jié)果”，并和公布的信息比較，因此驗證了計票結(jié)果是否被篡改，實現(xiàn)了計算安全意義上的可驗證性。具體的性質(zhì)分析如下：

(1)選票完全保密性。

投票者Pi利用隨機數(shù)Ri對選票vi進行盲化，得到si=vi+Ri，拆分成n份之后發(fā)送給其他投票者，即使其他n-1個投票者合謀攻擊也不能恢復投票者Pi的選票，實現(xiàn)了完全保密性。

(2)無收據(jù)性。

(3)公平性。

(4)無爭議性。

在統(tǒng)計選票階段，由于每個投票者是半誠信的，假若存在一個或者少數(shù)的投票者得到最后的統(tǒng)票結(jié)果和大多數(shù)人不一樣，那么說明這少部分投票者是不誠實的，和假設(shè)矛盾。

(5)可驗證性。

5 實例分析

以孫-劉電子投票方案中的7選3為例。為方便起見，假設(shè)模127的一個原根為g=57,h=106。那么投票者本地表決結(jié)果如表1所示。

Table 1 Local votes in the improved scheme表1 改進方案的本地表決結(jié)果

6 結(jié)束語

針對孫-劉電子投票方案中存在違背統(tǒng)票結(jié)果的不可欺騙性的缺點，基于離散對數(shù)困難性問題給出了改進方案，使其滿足計算安全意義上的可驗證性，保證了所計票數(shù)的不可欺騙性。

[1] Chaum D. Untraceable electronic mail,return

Addresses and digital pseudonyms[J]. Communications of the ACM,1981,24(2):84-88.

[2] Benaloh J,Tuinstra D.Receipt-free secret-ballot elections[C]∥Proc of the 26th ACM Symposium on Theory of Computing,1994:544-553.

[3] Groth J. Efficient maximal privacy in boardroom voting and anonymous broadcast [C]∥Proc of the 8th International Conference on Financial Cryptography (FC2004),2004:90-104.

[4] Cramer R,Franklin M,Schoenmakers B,et al. Multiauthority secret-ballot elections with linear work [C]∥Proc of Advances in Cryptology-Eurocrypt’96(LNCS 1070),1996:72-83.

[5] Cramer R,Gennaro R,Schoenmakers B. A secure and optimally efficient multi-authority election scheme [C]∥Proc of Advances in Cryptology-Eurocrypt’97(LNCS 1223),1997:103-118.

[6] Damgard I,Jurik M.A generalisation,a simplication and some applications of Paillier’s probabilistic public-key system [C]∥Proc of the 4th International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2001),2001:119-136.

[7] Rosen K H.Elementary number theory and its applications[M]. New York:Addition Wesley,1984.

[8] Benaloh C. Secret sharing homomorphisms：Keeping shares of a secret secret[C]∥Advances in Cryptology-Crypto’86(LNCS 263),1986:251-260.

[9] Zhong Hong,Huang Liu-sheng,Luo Yong-long.A multi-candidate electronic voting scheme based on secure sum protocol[J]. Journal of Computer Research and Development,2006,43(8):1405-1410.(in Chinese)

[10] Liu Yi-ning,Sun Pei-yong,Yan Ji-hong,et al. An improved electronic voting scheme without a trusted random number generator[C]∥Proc of the 7th China International Conference on Information Security and Cryptology(LNCS 7537),2011:93-101.

[11] Sun Pei-yong,Liu Yi-ning,Yan Ji-hong,et al. Secure E-voting scheme with multi-candidates[J]. Computer Engineering and Applications,2012,48(25):217-219.(in Chinese)

[12] Cranor L F,Cy R K. Disign and implementation of a security-conscious electronic polling system:WUCS-96-02[R]. Seattle:University of Washington,1996.

附中文參考文獻：

[9] 仲紅，黃劉生，羅永龍. 基于安全多方求和的多候選人電子選舉方案[J]. 計算機研究與發(fā)展，2006，43(8):1405-1410.

[11] 孫培勇，劉憶寧，延吉紅，等. 一種安全的多候選人電子投票方案[J]. 計算機工程與應用，2012,48(25):217-219.

劉高(1991-),男,四川宜賓人，碩士生，研究方向為應用密碼學與信息安全。E-mail:gaoliu9865@gmail.com

LIU Gao,born in 1991,MS candidate,his research interests include applied cryptography, and information security.

劉憶寧(1973-),男,河南鞏義人，博士，副教授，CCF會員(E200040278M)，研究方向為信息安全協(xié)議。E-mail:ynliu@guet.edu.cn

LIU Yi-ning,born in 1973,PhD,associate professor,CCF member(E200040278M)，his research interest includes information security protocol.

王東(1976-),男,河南魯山人，碩士，副教授，研究方向為計算機應用。E-mail:3166245@qq.com

WANG Dong,born in 1976,MS,associate professor,his research interest includes computer application.

A verifiable e-voting scheme with multi-candidates

LIU Gao1,LIU Yi-ning2,WANG Dong1

(1.School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004；2.Guangxi Key Lab of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

Compared with traditional voting schemes, e-voting has been widely studied due to the advantages in contrast, including more security, more efficiency and lower cost. In 2012, Sun et al. proposed a multi-candidates e-voting scheme based on the secure sum, however, it did not really achieve the verifiability. In this paper, we present an improved version to satisfy the non-deception requirement and guarantee the correctness of the tally results.

e-voting;secure sum;random number;verifiability;non-deception

1007-130X(2015)09-1667-04

2014-11-12;

2015-03-02基金項目：國家自然科學基金資助項目(61363069)；廣西自然科學基金資助項目(2014GXNSFAA118364)；廣西研究生教育創(chuàng)新計劃資助項目(YCSZ2015149);廣西高等學校高水平創(chuàng)新團隊及卓越學者計劃；桂林電子科技大學創(chuàng)新團隊

TP309

A

10.3969/j.issn.1007-130X.2015.09.011

通信地址：541004 廣西桂林市桂林電子科技大學數(shù)學與計算機科學學院

Address:School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,Guangxi,P.R.China