一种可验证的多候选人电子投票方案*

刘 高，刘忆宁，王 东

(1.桂林电子科技大学数学与计算科学学院，广西 桂林 541004;2.桂林电子科技大学广西可信软件重点实验室，广西 桂林 541004)

一种可验证的多候选人电子投票方案*

刘 高1，刘忆宁2，王 东1

(1.桂林电子科技大学数学与计算科学学院，广西 桂林 541004;2.桂林电子科技大学广西可信软件重点实验室，广西 桂林 541004)

电子投票相对传统投票具有安全、便捷、低成本的优势，近年来得到了广泛的关注。2012年孙培勇等人提出了基于多方求和的多候选人电子投票方案。经分析发现该方案不满足可验证性，给出了一种具有可验证性的多候选人电子投票方案，保证计票结果的不可欺骗性。

电子投票；安全多方求和；随机数；可验证性；不可欺骗性

1 引言

电子投票(E-voting)可有效解决传统投票方案中的效率低下、程序繁琐等问题，因而受到了各方的关注，但同时，如何保证电子投票中的安全性是一个重要的研究领域。为了实现电子投票方案的安全性，主要依靠密码技术等手段。1981年，一种相对传统投票方式具有高效、节能、方便的电子投票方案[1]被提出来，随着电子投票不断深入实际应用，更多的安全性质被提出来。比如无收据性 (投票者不可获得或构造使得贿选者确信的选票收据)[2]、选票的完全保密性、计票的公平性和无争议性[3]。形式上，电子投票可分为“二选一”(1-out-of-2)、“多选一”(1-out-of-m)和“多选多”(k-out-of-m)等。除了同态加密，多数加密算法不能对加密后的数据进行操作，从而限制了候选人数，一般处理的是“二选一”选举方式。1996年多候选人选举问题[4]被首次提出。随后一种基于ElGamal同态加密系统的“1-out-of-m”多候选人投票方案[5]被提出，但其计算复杂度太高，并且不能进行“k-out-of-m”多候选人选举。2001年，一种基于Paillier密码体制的“k-out-of-m”投票方案[6]被提出，该方案不能杜绝某个投票者对同一个候选人重复投票现象，并且对计票中心和投票者造成大量计算负担，使得该方案不能实际应用。2006年，仲红等提出一种基于多精度计算[7]和安全多方求和协议[8]的无可信第三方“k-out-of-m”多候选人选举方案[9]，并称其满足选票的完全保密性、无收据性、健壮性、公平性、无争议性和高效性。2011年，刘忆宁等人[10]提出一种改进的电子投票方案，该方案利用拉格朗日插值代替可信第三方产生随机数，并且继承了Bingo voting的安全性质，具有更好的健壮性。随后孙培勇等人[11]分析发现其不满足完全保密性，并且提出改进的多候选人选举方案，利用随机数对每个投票者的选票进行“盲化”，实现选票完全保密性。

但是，分析发现孙培勇等人提出的多候选人选举方案不满足可验证性[12]，从而不能保证计票结果的不可欺骗性。为了解决这一安全隐患，基于离散对数困难性问题，我们提出了一种可验证的多候选人电子投票方案以保证可验证性，实现了所计票数的不可欺骗性。

2 孙-刘电子投票方案及安全性分析

2.1 孙-刘电子投票方案

在本地表决阶段，投票者Pi(i=1,2,…,n)生成选票，为mk位二进制序列00…0a100…0a2…00…0am，其中aj=0或1代表对Cj(j=1,2,…,m)的赞同或反对，并将该二进制序列转化为十进制数vi。

Figure 1 Transfer matrix

图1 传送矩阵

2.2 孙-刘电子投票方案的安全性分析

3 一种改进的多候选人投票方案

(1)本地表决。

每个投票者Pi(i=1,2,…,n)对Cj(j=1,2,…,m)进行表决。设置aj=1表示赞成，反之，设置aj=0表示否定，再将对所有候选人的选票按照顺序组成一个mk位二进制序列00…0a100…0a2…00…0am。最后将该二进制序列转化为十进制数vi。

(2)发送选票。

(3)统计选票。

4 改进方案的安全性分析

该方案继承了孙-刘方案的安全性质，基于离散对数难题，每个投票者将自己的选票和随机数“分类”，并且通过安全信道发送“分类结果”给其他投票者。然后每个投票者累积“分类结果”，并和公布的信息比较，因此验证了计票结果是否被篡改，实现了计算安全意义上的可验证性。具体的性质分析如下：

(1)选票完全保密性。

投票者Pi利用随机数Ri对选票vi进行盲化，得到si=vi+Ri，拆分成n份之后发送给其他投票者，即使其他n-1个投票者合谋攻击也不能恢复投票者Pi的选票，实现了完全保密性。

(2)无收据性。

(3)公平性。

(4)无争议性。

在统计选票阶段，由于每个投票者是半诚信的，假若存在一个或者少数的投票者得到最后的统票结果和大多数人不一样，那么说明这少部分投票者是不诚实的，和假设矛盾。

(5)可验证性。

5 实例分析

以孙-刘电子投票方案中的7选3为例。为方便起见，假设模127的一个原根为g=57,h=106。那么投票者本地表决结果如表1所示。

Table 1 Local votes in the improved scheme表1 改进方案的本地表决结果

6 结束语

针对孙-刘电子投票方案中存在违背统票结果的不可欺骗性的缺点，基于离散对数困难性问题给出了改进方案，使其满足计算安全意义上的可验证性，保证了所计票数的不可欺骗性。

[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]. 计算机研究与发展，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)，研究方向为信息安全协议。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)；广西研究生教育创新计划资助项目(YCSZ2015149);广西高等学校高水平创新团队及卓越学者计划；桂林电子科技大学创新团队

TP309

A

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

通信地址：541004 广西桂林市桂林电子科技大学数学与计算机科学学院

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