黄仕杰 洪 璇

(上海师范大学信息与机电工程学院 上海 200234)

基于同态实现多候选人的电子投票方案

黄仕杰 洪 璇

(上海师范大学信息与机电工程学院 上海 200234)

选举是当今公民实现民主的重要方式，相比于传统选举方式，电子选举以密码学为基础，可以有效避免在各个环节中出现徇私舞弊现象，并且在计票阶段也比传统选举方式更快、更准确。在满足电子选举的公正性、唯一性、匿名性等八个基本特性的基础上，该方案通过使用Paillier加密的加法同态性来避免在计票环节对选民选票进行舞弊操作，同时能够大幅度提高电子选举在最后计票环节的效率。

电子选举 同态加密 Paillier公钥密码体制 RSA公钥密码体制 加法同态性

0 引 言

传统选举在其发展过程中，发现其并不能实现选举的公正性，而且在实行传统选举过程中，因为人为失误的因素，会导致选举结果最后的不可信，甚至导致选举失败[6]。在2000年美国大选中，曾因纸质选票的样式设计误导了选民，导致总统候选人对最后的选票结果产生争执，最后由最高联邦法院裁决选出美国总统。

Chaum[1]在1981年提出了一个基于公钥密码体制的无法追踪的电子邮件方案，这是电子投票的雏形。1993年Fujioka等提出了比较完善的盲签名方案。目前电子选举方案主要使用的技术有：基于盲签名的电子选举[5]、基于秘密共享的电子选举、基于混合网络的电子选举以及基于同态加密的电子选举，共四种方案。

本文提出了一个基于同态加密密码体制提出的电子选举方案，使用同态加密保证选票的保密性和不可追踪性[2]，最后对选票结果的密文进行恢复，得出选举结果。该选举方案中主要参与者有：认证中心、计票中心、投票人、候选人以及负责验证选票正确性的可信第三方。

1 同态加密技术

1.1 同态加密体制

同态加密技术是由Rivest等在1978年首次提出[3]。同态加密的提出，使得人们可以对密文直接进行计算，并且计算后的结果解密后得出的明文与对应明文进行同样的计算后得出的结果一样[10]。设R、S是两个环，R表示明文空间，S表示密文空间，定义算法E: R→S。

(1) 加法同态

满足从E(x)和E(y)可以通过加法计算E(x)+E(y)计算出E(x+y)，同时不需要知道x、y的值。

(2) 乘法同态

满足从E(x)和E(y)可以通过乘法计算E(x)E(y)计算出E(xy)，同时不需要知道x、y的值。

(3) 混合乘法同态

满足从E(x)和y可以通过乘法计算yE(x)计算出E(xy)的值，同时不需要知道x、y的值。

1.2 同态加密在电子选举中的应用

Cramer等在1997年，第一次提出了基于ELGamal密码体制的加法同态性的电子投票方案，利用ELGamal的加法同态性将选票的密文累乘后，再通过私钥将最后的投票结果解密出来，进一步节省了计票环节的时间。目前仍然没有有效的全同态加密算法，不过存在有成熟且具有单一同态性质的密码算法(RSA、ElGamal、Paillier)能够满足部分安全多方计算场景中的应用[8]。在文献[11]中，提及虽然Paillier公钥密码体制自身加解密效率过低，但是Paillier的同态性在密文操作上所消耗的时间相对较少，十分符合电子投票在计票环节利用同态加密的同态性进行选票累加的需求。所以本文选取基于大整数因子分解的Paillier加密作为主要加密算法。

2 加密算法介绍

2.1Paillier公钥密码体制基础知识

Paillier[3]公钥密码体制是一种具有语义安全性、加法同态性以及混合乘法同态性的公钥密码体制，它的安全性主要是依赖于大整数因子分解的困难性[4]。

2.2Paillier公钥密码体制加解密过程

(1) 参数初始化

(2) 加密过程

对于明文m(m∈Z_n)，对应的密文c为：

c=Encrypt(g,n,m)=gm×rnmodn2

(3) 解密过程

对于密文c，对应的明文为：

m=Decrypt(λ,μ,c)=L(cλmodn2)×μmodn

2.3Paillier算法的同态性

根据上一小节的条件，对明文m1和m2进行加密后，得到对应密文：

c1=gm1×rnmodn2和c2=gm2×rnmodn2。

此时：c1×c2=gm1+m2×r2nmodn2=Encrypt(g,n,m1+m2)，所以paillier算法具有加法同态性[9]。

3 基于同态加密的电子投票方案

3.1 方案概述

在本电子投票方案中，依据paillier密码体制对选票内容进行加密。对加密后的密文取其hash值，用RSA加密体制进行签名。由于paillier密码体制具有加法同态性和混合乘法同态性，所以对密文的任何操作，都等效于对明文做同样的操作。

本方案中，主要参与者有：

(1) 认证中心(CertificateAuthority，缩写CA)

生成该方案中的paillier的公私钥和RSA的公私钥，并将对应的公钥广播出去。负责对投票人的身份进行验证，并且存储在数据库中，确保其真实可靠，避免不诚信的投票人多次投票，在合法投票人注册成功后，向其提供空白选票。选举结束后，将投票结果解密出来。如果最后发生纠纷，可以将有争议的选票恢复成明文。

(2) 计票中心(Count)

对来自投票人的选票进行验证，判断选票的有效性，并且通过paillier密码体制的加法同态性进行选票的数量累加。

(3) 投票人(Vote，缩写V)

投票人(Vote，缩写V)：投票人，包括合法和非法的投票人，投票人用V1,V2,V3,…,Vk表示。

(4) 候选人(Candidate，缩写C)

一场选举中，有多个候选人，对应的候选人用Ce1,Ce2,Ce3,…,Cej表示。

(5) 可信第三方

负责检查选票的正确性。

3.2 方案流程

(1) 方案初始化阶段

构造秘钥：

由认证中心(CA)生成该方案的paillier加密的公钥(g,n)，私钥(λ,μ)；生成该方案的RSA加密公钥(n′,e),私钥d。

构造的选票形式：

假设认证中心计算能力足够大，则有j位候选人，投票人的人数小于10k，为方便最后统计选票结果，构造投票人Vi(i∈(1,2,…,k))的选票形式如下：

设投票号为IDvi，是一串随机生成的唯一身份标识符。设投给候选人Cm的选票内容为：(0,0,…,bm) ，其中bm∈(0,1)，m∈(1,2,…,j)并且bm(m∈(1,2,…,j))中有且只能有一个值为1。那么，构造通用选票如图1所示。

图1 通用选票形式

例如投给第一位候选人的选票形式如图2所示。

图2 投给第二位候选人的选票

那么可以得出针对j位候选人的电子投票，共有j种选票形式，分别记为(ce1,ce2,…,cej)，在计票阶段只要通过对这j种选票形式进行筛选，则可以判断选票的唯一性，是否选票只投了一位候选人。同时由认证中心对选票内容进行Paillier加密，在每次进行Paillier加密时，选取不同的随机数rm进行加密。其中rm∈(r1,r2,…,rj),0≤rm≤n，并且随机数rm两两之间互质，得到密文结果(Encrypt(ce1),Encrypt(ce2),…,Encrypt(cej)，其中：

投票人注册阶段：

投票人Vi向认证中心CA提交个人身份资料。

认证中心CA验证投票人Vi身份信息合法，若投票人身份合法且确实是第一次投票，则向投票人Vi发放一个投票号(IDVi)，对该投票号(IDVi)进行paillier加密，获得密文c1，即为空白选票：

c1=Encrypt(g,n,IDV)=gIDV×rnmodn2

对加密结果c1，使用注册机构的私钥进行RSA签名：

对加密结果c1，取其哈希值：HASH(c1)；

将投票人身份、投票号(IDV)、空白选票c1、选票的签名SIGRA(c1)以及其哈希值HASH(c1)收录到数据库中，防止投票人多次投票，并且将(c1,SIGCA(c1),HSAH(c1))作为票据交给投票人V。

(2) 生成选票阶段

投票人获得来自认证中心CA的票据(c1,SIGCA(c1),HSAH(c1))后，先对空白选票c1进行哈希值验证，确保选票的完整性。

验证选票的合法性：

Verify()(f,e)(c1,SIGCA(c1))=True

其中，c1≡GISCA(c1)e(modn′)。

若选票合法，保留其身份信息和票据(c1,SIGCA(c1),HSAH(c1))，在以后的纠纷中证明自己的合法身份。

之后投票人将根据自己的选择，选择候选人Cm(m∈{C1,C2,C3,…,Cj})，将所选的候选人Cm的选票cm进行paillier加密，其中选取特殊的随机数rV，rV与集合(r1,r2,…,rj)中的随机数都互质，并且0≤rV≤n：

投票人将完整选票(SIGCA(c1),c1,c2)交给计票机构，并且自己保留一份以防止以后发生投票内容与公示内容不一致纠纷。

(3) 计票阶段

计票初始时，计票机构使用paillier的公钥初始化，投票箱MBallot：

cBallot=Encrypt(g,n,0)=gMBallot×rnmodn2

=g0×rnmodn2

在选票进行计票之前，引入可信第三方，对来自选民的选票进行检查，验证其身份的唯一性，以及投票内容的唯一性。

假设可信第三方也持有此次电子投票Paillier加密的密钥(λ,μ)，以及对选票内容进行Paillier加密的随机数集合(r1,r2,…,rj)。可信第三方获得来自投票人的选票，取其中的SIGCA(c1)与数据库中的对比，判断选票的合法性以及身份的唯一性。若判断通过，则构造匹配值：Matchm=(rm/rV)nmodn2，得到匹配值集合(Match1,Match2,…,Matchj)。

计算c2与(Encrypt(ce1),Encrypt(ce2),…,Encrypt(cej))中的商得到集合(q1,q2,…,qj)，比较集合(q1,q2,…,qj)与集合(Match1,Match2,…,Matchj)，如果有且仅有一对值相等，则说明该选票只投了一位候选人，将这张选票交给计票中心。

若选票通过步骤(2)的检查，则将c2累加入投票箱cBallot中：

cBallot=cBallot×c2

(4) 投票结果公示阶段

认证中心CA使用paillier密码体制的私钥对投票结果进行解密：

MBallot=Decrypt(λ,μ,cBallot)

并且对最后投票结果MBallot以及各张选票进行公示。

4 方案安全性分析与效率分析

4.1 方案安全性分析

(1) 合法性

合法投票人才有权参加选举活动，在认证中心会对所有的投票人进行身份认证排除不具备投票权利的投票人。

(2) 匿名性

在构造选票的过程中，使用的是paillier公钥密码体制对选票进行加密，除了投票人本身，其他任何人都无法根据选票追踪调查到相应的选民身份，无法将选票和选民一一对应。

(3) 公正性

任何人及任何事情都不应该影响到投票的最终结果，投票的中间过程更不能被泄露；每位合法的选民，都可以获得自己的唯一选票号，公平公正地行使自己选举权。

(4) 唯一性

合法选民有且只有一次投票机会。通过保留选票内容以及唯一选票号IDvi，避免不诚信的投票人多次投票。

(5) 可验证性

在最后的选举结束之后，可以通过恢复选票，使得每位投票人都能够比较容易验证自己的选票有没有篡改或舍弃。

(6) 正当性

(7) 完整性

所有合法的投票都可以通过paillier公钥密码体制的加法同态性累计，被计入最后的选票结果中。

(8) 无争议性

基于RSA的公钥签名方案和基于paillier同态加密方案被证明是安全的。所以基于paillier加密的电子投票方案的算法以及其参数、公钥等可以完全公开，投票人通过自己保留完整选票(SIGCA(c1),c1,c2)，在电子投票结束后，都可以通过将选票解密来验证选票的正确性。

4.2 方案效率分析

目前同类使用paillier加密算法构造的电子选举方案较少，所以选择与基于ElGamal加密算法同态性的电子选举方案作比较[12]。在文献[12]中提出一种基于ElGamal加密算法同态性来保护选民身份信息不被暴露，同时保证选民选票在计算过程中的正确性以及安全性。但是该方案使用ElGamal算法进行选票的加密，由于加密算法的特性，对每张选票进行加密都会相应获得两段密文。设ElGamal加密算法的公钥为(p,g,y)，私钥为x，则对选票M进行加密，获得密文密文：C1,C2:C1=gkmodp,C2=K×Mmodp。在整个加密过程中需要进行两次幂运算，增大了计算复杂度，以及因为获得比明文长度长两倍的密文，也增大了存储空间的使用。相比之下，本方案在加密过程中只需要进行一次幂运算。同时文献[12]对选民提供的选票没有进行唯一性认证，无法防范不诚信的合法投票人构造非法选票，构造的选票格式与文献[12]所定义的不一致影响选举的正确进行。本方案在保留使用加密算法的同态性来累计选举结果的基础上，选择使用paillier加密算法来简化幂运算，同时构造匹配值集合(Match1,Match2,…,Matchj)来保证选民提交的选票的合法性，是符合规范的。

5 结 语

本文在paillier公钥密码体制的基础上，提出了一种电子投票的方案。本方案使用paillier加密的同态性，构造特殊的选票以实现在对选票不解密的情况下，能对选票实现汇总，最后在投票结束后，将选票结果恢复出来。本方案还需进一步完善，降低运算规模，能适合更大规模的选举。

[1]ChaumDL.Untraceableelectronicmail,returnaddresses,anddigitalpseudonyms[J].CommunicationsoftheACM,1981,24(2):84-90.

[2] 祁明,肖国镇.一个适合大规模电子选举的秘密投票方案[J].电子与信息学报,1997,19(5):717-720.

[3]RivestRL,AdlemanL,DertouzosML.Ondatabanksandprivacyhomomorphisms[M]//FoundationsofSecureComputation,1978:169-179.

[4]PaillierP.Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses[C]//ProceedingsofInternationalConferenceontheTheoryandApplicationofCryptographicTechniques.Springer,1999:223-238.

[5] 谢金宝,刘晖波.基于盲、群签名和秘密共享的新型电子安全选举模型[J].微型机与应用,2000,19(9):38-42.

[6] 冯泽涛,张勇.一个有效的电子选举方案[J].计算机与信息技术,2007(5):24-26,29.

[7] 宋春来,殷新春,孟纯煜.一种安全实用的大规模选举协议[J].计算机应用与软件,2008,25(8):40-41,47.

[8]BonehD,GentryC.Afullyhomomorphicencryptionseheme[D].PaloAlto,CA,USA:StanfordUniversity,2009.

[9]NishideT,SakuraiK.Distributedpailliercryptosystemwithouttrusteddealer[C]//Proceedingsofthe11thInternationalConferenceonInformationSecurityApplications.Springer,2010:44-60.

[10] 袁春明.基于Paillier公钥密码体制的零知识证明方案[J].计算机与现代化,2011(4):45-46,49.

[11] 白健,杨亚涛,李子臣.Paillier公钥密码体制同态特性及效率分析[J].北京电子科技学院学报,2012,20(4):1-5.

[12] 李蓓.基于同态加密策略的电子选举系统[J].计算机应用,2015,35(S1):66-68,88.

AN ELECTRONIC VOTING SCHEME REALIZING MULTI CANDIDATESBASED ON HOMOMORPHISM

Huang Shijie Hong Xuan

(CollegeofInformation,MechanicalandElectricalEngineering,ShanghaiNormalUniversity,Shanghai200234,China)

Election is an important way to achieve democratic citizenship in modern society. Compared with the traditional approach, electronic voting election can effectively avoid the phenomenon of favoritism in each section based on cryptography, and it is much faster and more accurate in vote counting. On the basis of satisfying the eight properties of fairness, uniqueness, anonymity and so on, the proposed scheme applied the addition homomorphism encrypted by Paillier in order to avoid the fraud operation on electors votes in vote counting. Meanwhile, it is able to greatly enhance the efficiency of electronic voting in the last vote counting section.

Electronic vote Homomorphic encryption Paillier public key cryptography RSA public key cryptography Addition homomorphism

2015-12-09。上海市自然科学

14ZR1431000)。黄仕杰，硕士生，主研领域：信息安全。洪璇，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.03.051