基于公共云的安全电子投票协议分析与设计

刘 玉

(合肥学院 管理系， 合肥 230601)

基于公共云的安全电子投票协议分析与设计

刘 玉

(合肥学院 管理系， 合肥 230601)

电子投票具有海量数据和实时性的特点，且需要大规模数据运算，导致传统方案往往难于部署。公共云具有的强大计算和存储能力，给大规模电子投票系统的部署带来新的机遇，但同时也对安全性保障方面提出了新的挑战。本文提出了一种基于多公共云的安全电子投票协议，可以充分利用公共云处理大量数据的能力，并能有效保证电子投票系统的安全可靠性。安全性和性能分析表明，所提出方案可以满足电子投票系统的安全需求，同时能够节省计算开销和通信开销。

电子投票；公共云；半可信；审计

随着计算机和通信技术的发展，特别是随着网络的迅猛发展，人们利用计算机或各种通信设备在任何地方通过网络进行投票成为现实。由于远程电子投票(Electronic Voting，E-Voting)的方便性和实施成本的低廉，必将对社会经济的发展和国家民主进程产生积极而重大的影响。比如，可以吸引更多的符合规则的人来投票、方便残疾人投票、投票不受天气等状况的影响等。在最近的二十多年中，人们对电子投票展开了深入研究，提出了许多电子投票协议。与传统的人工投票相比，电子投票可以节省大量的人力物力，选举管理机构不必像人工选举那样进行大量的人工选票发放和选票统计工作，而投票人也不必集中起来一起投票。电子投票不仅在组织、选票、搜集和统计方面节省了大量的人力和成本，而且在一定程度上保证了选举人的利益。因而，电子投票方式受到了越来越多的关注。

一个安全的电子投票系统需要满足以下要求：

(1)投票人所投的票必须保密；

(2)完整性(completeness)：所有合法选票被正确计票；

(3)准确性(soundness)：任何无效的票都不能被计票，每个合法的选票不能够被修改、复制或移走；

(4)公平性(fairness)：任何事情不能影响投票最终结果，例如选票的中间结果不能泄露，不能发生选票增加的情形；

(5)合法性(eligibility)：只有具有投票权的投票者才可以投票；

(6)唯一性(uniqueness：任何投票者最多只能投票一次；

(7)确定性(invariableness)：计票的结果是确定的。也就是说，不论对计票结果进行多少次重复计算，结果都是相同的。

由于电子投票具有海量数据和实时性的特点，且需要大规模数据运算，导致现有的方案部署往往需要大规模的投入，且需要专业的设备维护和机房管理人员。云计算技术的发展，使得电子投票系统中存储和计算可以外包(outsource)到公共云，从而减少系统软硬件的维护成本。但由于公共云的半可信(Semi-Trust)假设，使得传统的电子投票方案无法直接进行应用。本文提出了一种基于多公共云的安全电子投票协议，可以充分利用公共云能够处理大量数据的能力，并保证了电子投票系统的安全性。

1 相关工作

从第一个投票协议提出以来，许多人对其做了大量的研究。第一个密码学意义上的投票协议是由Chaum[1]于1981年提出的。该协议采用了公钥密码体制，并利用数字签名花名册来隐藏投票人的身份，然而却不能无条件的保证投票人的身份被跟踪。后来，Chaum提出了一个新的投票协议[2]；它保证了投票人的无条件匿名性，但整个投票过程能被单个投票人破坏。

随着密码学相关理论的逐渐发展，盲签名也随着发展，各种投票方案不断涌现。但是这个时候的方案的一个最大的不足就在于实用性不强，不适应大型投票。例如，针对安全方面的不足，Benalon和Tuinstra于1994年提出了一系列可验证选举结果的投票协议[3]；Nurmi，Saloma和Santean提出了双代理协议[4]，还有要求投票人之间交互的投票协议[5]等等。这些协议不是太复杂，不适合大型选举，就是安全方面仍存在漏洞。

直到Fujioka，Okamoto和Ohta提出了一个适合大型选举的安全选举协议[6]，(简称F00方案)，电子选举方案才在各个非政府部门得到了广泛应用。该方案中应用了公开密钥、数字签名、盲签名(B1ind Signature)、比特承诺协议(Bit Commitment)等多种密码学技术，保证了选票的秘密性和公平性，而且也解决了投票者身份的匿名性问题，同时其算法易于实现、网络通信量较小，适合于大规模投票。但是，它仍然有一些缺点：首先，它没有解决“选票碰撞”的问题。其次，使用比特承诺协议虽然保证了选票的公平性，但是在计票时需要投票者提供自己的随机密钥k。如果投票者提供一个非法的密钥，则对应的选票无法打开。最后，Fujioka的方案要求合法投票者的数目与最后的合法选票数目要相等，即不允许有人弃权，使得这个方案缺乏实用性。并且在这个方案中，管理机构的作弊行为可通过投票完毕后的审计工作识别出来，但是如果没有全体投票人的共同参与，是不可能恢复合理公正的选举结果的。

后期得到广泛应用的选举系统，大多数是建立在F00方案的基础上的：其中比较著名的有Washington大学的Sensus系统[7]和MIT的EVOX系统[8]。文献[9]也在完善F00的基础上提出了一种新的电子投票方案能够提供投票者中途弃权。此外，文献[10]给出了一种具有可验证性的多候选人电子投票方案,保证计票结果的不可欺骗性。文献[11]从计算开销优化的角度设计了一个抗第三方欺诈的安全电子投票方案，相比于其他方案能够进行高效实现。

目前比较常用的实用投票系统为Helios[12]和Prêt à Voter[13]，其中Helios 采用的是开放式审计选举，简化加密协议，着重实现公开审计，即使管理机构腐败也能验证完整性。每个人都可以作为审计者，重点坚持无条件的完整性。而Prêt à Voter提供了一个实用的方法,用一个简单的端到端可核查的选举，保证高度的透明度,同时保留秘密投票。保证可审核性来自选举的本身,而不是需要信任系统组件的位置。

从目前国内外的所发表的论文和实现的投票系统来看，电子投票系统在不断地改进和发展，也不断涌现出新的想法和方案。但利用公共云作为基础的电子投票系统尚未见有方案提出。公共云的利用具有双面特性，一方面，公共云具有的强大计算和存储能力，能够为大规模电子投票系统的部署带来新的机遇，另外一方面，公共云的半可信假设为电子投票的安全性带来了新的挑战。

2 基于公共云的电子投票协议

2.1 基本假设

现实选举会牵扯到多方利益，我们可以假设他们互相制约。所以本方案的前提也是多云不共谋。我们认为公共云是自私半可信的，会按照协议进行计算和存储，但是希望获得秘密信息或篡改信息。通过公共云平台的加入，其他现实机构的大部分计算和验证工作都被云分担，减少了现实机构的设立和维护开销。并且公共云高速的计算能力使得大量的计算和存储开销变得更经济，即使由于安全性要求而添加的运算和验证都消耗了足够少的时间和花费。

方案分为五个主体部分：

选民(Voter):有投票权利的人。

管理中心(Administration Center):发放选民权利和个人信息的机构，提供申诉和部分审计功能。方案中认为是可信的。

以及三个假设为互相不共谋的公共云，其中公共云1(Cloud-1)主要提供认证和计算服务；公共云2(Cloud-2)辅助Cloud-1进行验证选票；公共云3(Cloud-3)负责对Cloud-1的计算进行审计。

2.2 主要流程

(1)注册阶段。如图1所示，具体过程为：

①每个有投票权的选民都可以获取唯一的选民，选民向管理中心申请，经身份验证后获得选民。

②管理中心同时给选民发放相应的唯一申诉标识、公钥和给选民签发的证书 。选民也在云端存储。

③选民可以验证收到的证书和签名，若不正确可以提出申诉。

图1 注册阶段图示

(2)投票阶段。

①选票构建方式，如图2所示，左半部分对m个候选人有一个随机的排序，右半部分包括选民的选择和一个加密码，加密码用于还原候选人排序，真正的顺序表只有管理中心拥有。选择结束左半部分删除，只留右半部分，这样只拥有一部分选票的人是无法解密的。并且要求选民只能选择一个候选人。

图2 投票格式

②选择结束并确认后，选择项是一个m维的01向量形式，且原则上只有一项为1，其他项为0。记选民Ui的选票值为：

(xi1,xi2,xi3,…,xim)，公钥PK=(n,g)。

通过Paillier加密，得到：

然后选民对IDi，加密码和{vij,j∈[1,m]}的哈希值签名得Si：

Si=SUi(H(IDi,Pi,{Vij}))

③选民将(IDi,{Vij,j∈[1,m]},Si,Certi)上传到公共云，此时获得选民选票的公共云有两个，即Cloud-1和Cloud-3。

④Cloud-1和Cloud-3确定接收到选票后分别返回给选民一个确认收到的信息和其选票的哈希值，并附有Cloud-1和Cloud-3的签名:

SC1(ack,H(IDi,{Vij})

SC3(ack,H(IDi,{Vij})

⑤Cloud-1首先验证选民的证书Certi是否合法，签名是否有效。并在数据库中搜索检测是否是第一次投票。若不合法则选票作废，同时通知Cloud-3此票作废。

(3)验票阶段。以下步骤用于验证选民是否进行了正确投票，从而避免出现多票或负票情况：

①Cloud-2同时开启仲裁程序，用户收到Cloud-1和Cloud-3的确认消息并验证合法后联系Cloud-2，发送自己的IDi，证书Certi和Cloud-1的确认消息。

②Cloud-2验证用户身份属实后，随机产生一系列的hj和一个随机混淆因子α，并产生一个哈希表，内容为：

{H(gh1α-n),H(gh2α-n)，…，H(ghmα-n)} ，

签名后发给选民。

并将Ci发给Cloud-2。

⑤Cloud-1计算，

这样，只需验证计算得到的值是否在Cloud-2提供的哈希表中，即可证明用户的选票是否有效。若不存在，则用户此选票作废。

⑥Cloud-1得到最终验证结果，需要告知Cloud-3， Cloud-3得到Cloud-1对选票的验证结果后，才认为此选票是可以进行下一步处理的。若长时间得不到验证结果， Cloud-3会提出申诉，要求审计。

⑦验证阶段结束后，Cloud-1宣布已获得签名的投票者的总数，并公布(IDi,H({Vij)},Si,Certi)列表和对应选票是否有效的信息，其中选票内容为哈希值，只有选民才能确定是否正确。

⑧由于公共云的存储和计算能力都很强，所以验证阶段和计票阶段是交互进行的，管理中心设定时间段T，每隔时间T， Cloud-1就会更新此时间段内的公告板数据，并对此时间段内的选票进行计票。

(4)计票阶段。

①Cloud-1对加密码Pi进行计算，还原顺序。

③Cloud-3随机抽取任意时间段同时进行同样的计算，同时公示用以审计，概率上确保Cloud-1无法修改计算结果。

④投票截止后Cloud-3将最终计算结果，即统计所有时间段的总和:

{PiVi1,PiVi2,PiVi3,…,PiVim}

将之发给管理中心，并公示结果，同时Cloud-3根据Cloud-1的公告进行计算审计。

⑤管理中心首先按照之前检验过的选票列表公告进行对应，确保数量上没有问题后，对云端计算得到的结果进行Paillier解密得到最终投票结果。

(5)审计阶段。分为选民审计、管理中心审计和Cloud-3审计。

选民审计过程：

①Cloud-1公布还原计算过程和选票的散列值供审计。选民拥有投票编号，可以追踪审计自己选票的解密统计过程。

②选民可以检查投票人的数量是否符合选票的数量。

③选民可以检查自己的选票是否在公告中，若不存在则公开唯一申诉标识和管理中心的签名S(IDCi,PK)，要求自己的选票加入。

管理中心审计过程：

①管理中心按照之前审计过的有效选票的公告和Cloud-3的计算结果对Cloud-1计算的公告进行审计，若发现有数量不符或还原计算有误可进行处理。

②管理中心同样公布最后结果供选民审计。选民若发现解密信息出现问题可申诉。

公共云Cloud-3审计过程：

①在接收选票的阶段，由于选票是同时发往Cloud-1和Cloud-3的，所以Cloud-3可以审计最终Cloud-1在公告板上放出的关于选票内容和是否有效的信息。

②Cloud-3在选票计算过程中进行随机抽样审计，并在最终根据公告对Cloud-1的计算做验证，可以减少人力审计的工作量。

3 安全性分析

3.1 阻止半可信的公共云为了获取选票内容而参与注册阶段。

若公共云获取了管理中心所颁发的公钥，可能会获知其他选民的选择。方案中选票模式加入了打乱候选人的步骤，可保证不知道加密码Pi的人，即使获取了公钥也无法得知选票结果。同时，Cloud-1和Cloud-2相互制约的设定使得不可能同时获得Pi、公钥和rij，从而可以保证选票的安全。

3.2 阻止公共云计算的内容和公告的内容不一致

比如Cloud-1恶意修改选票，但公告时展示的该选票仍是正确的，选民在审计时无法发现，只有计算结果发生改变。这种情况可以依靠Cloud-3随机抽取时间段同时计算，从而在一定概率上避免该问题的出现。由于Cloud-3必须获知Cloud-1和Cloud-2的验票结果，所以在选票安全和完整性上得到保障。

3.3 阻止公共云拒绝承认选票或冒充选民的行为

本系统中选民可弃权。若公共云没有收到选民的选票，则公告时不会显示选民的编号和信息，管理中心可以对照进行确定。若公共云收到选票但谎称自己未收到，则选民可以持唯一申诉标识和提交选票时云返回的确认信息进行申诉。若有人弃权，但公共云想伪装其投票，则在公告时无法给出管理中心的证书，也很容易发现。

3.4 其他安全性质。

(1)秘密性。选民在注册阶段会获得选民IDi，但选民IDi公布是无法和每个选民对应起来的。选民在投票阶段，选票通过同时投给Cloud-1和Cloud-3保证公平审计，而公告的选票信息为哈希后的信息，管理中心也无法将选民与选票具体内容对应起来。从而保证了秘密性。选民进行申诉时只需给出唯一标识和签名即可，不需提供其他信息，保证了身份的保密性。

(2)完整性。如果协议的各方都诚实，选举结果将是可信的。由于投票者在投票之前都必须到管理机构注册授权，这样就确保了只有合法的投票者才能进行投票。并且设立了公告板，每个选民拥有选民可以在公告板上跟踪审计自己的选票，确保了所有个人和关心选举的结果的人都可以通过这些跟踪机制对选举的结果进行跟踪验证，保证了选举结果的诚实、可靠。因而所有的有效选票都会被正确统计，协议满足完整性。

(3)准确性。对于投票者来说，其扰乱选举的途径有两种：不断发送无效选票或发送错误选票。而这两种情况都可以在验票阶段被检验出来: Cloud-1每收到一份选票，都会检验该选民是否投过票，若已投过，此票直接作废；在验票阶段，若选票内容不正确， Cloud-1最终计算的结果不会在哈希表中。同样，选民被要求跟踪验证自己的选票，同时管理中心也对Cloud-1的计算进行审计，并设置不共谋的Cloud-3进行随机取样，确保不会出现选票更改或删除情况。

(4)公平性。Cloud-2在验证环节的加入，避免了Cloud-1获得信息，并且如果用户没有传给Cloud-1完整的加密信息，例如只传了Vi1，则Cloud-1在验证环节有极大概率解出0，也很容易发现问题。同时Cloud-3的设置，也限制了Cloud-1在计算过程中可能出现的问题。

(5)合法性。协议中包括数字签名和证书，云端公告和管理机构的审计也保证不会有非法人员冒充选民进行投票。如果非法的选票要被计入投票结果，那么这张选票必须有选民签名和管理中心的证书，而这方面造假很容易在公告时被发现。若公共云的公告与计算不一致， Cloud-3的审计计算也有大概率会发现。

(6)唯一性。选民在注册阶段获得唯一身份标识IDi和申诉标识，并需要经过管理中心的验证签名，没有人可以投多次票或获得多次身份。一个人申请多个IDi也是不现实的，所以协议满足唯一性。

(7)确定性。每个选民都可以跟踪验证自己的选票，可以计算公告板上自己的选票信息是否被正确解密，若正确则被成功统计，若不正确则公布申诉标识和签名，要求计入正确的选票。

4 性能分析

(1)通信复杂度。本协议在执行过程中，通信比较频繁的是投票和验票阶段，其中公共云与用户之间的通信共有四轮，公共云之间的通信共两轮。

(2)计算复杂度。协议在执行过程中，Pallier加密和解密各进行了一次，其他计算过程都在云端实现。每一个选民方只需要进行Paillier加密和验票阶段的 计算，管理中心对每一个候选人进行一次Paillier解密。所以除了公共云之外的Paillier计算只有常数次，所以Paillier算法的执行开销不会随着用户规模的增大而快速增长。

总体来说，大规模的数据计算是由公共云进行的，其中的通信开销和选民与管理中心的计算开销相对较少，本方案在性能上较为优秀。

5 结论

由于现在进行选举的数据量日益增大，计算量也成指数型上升，所以引入公共云可以在很大程度上解决电子投票的验证和计票问题，减少了人工工作量，速度上也有很大提升。本文提供了一个基于公共云的电子投票协议方案，详细介绍了协议的过程，并对方案的过程和细节部分进行安全性分析。其中的加密算法采用了同态的Paillier加密，保证让公共云统计的同时无法获得选票内容和最终计票信息。最终计票中心只需要对每个候选人的结果进行解密即可，计算量很小。

[1] David L. Chaum. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms [J]. Communications of the ACM, 1981, 24(2):84-90

[2] David L. Chaum. Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA [C]. In Workshop on the Theory and Application of Cryptographic Techniques, 1988:177-182.

[3] Josh Benaloh, Dwight Tuinstra. Receipt-free Secret-ballot Elections. In Proceedings of the 26th annual ACM symposium on Theory of computing, 1994：544-553.

[4] Hannu Nurmi, Arto Salomaa, Lila Santean. Secret Ballot Elections in Computer Networks, Computers & Security, 1991, 36(10): 553-560.

[5] Richard DeMillo, Michael Merrit. Protocols for Data Security. Computer, 1983, 2(16):39-51

[6] Atsushi Fujioka, Tatsuaki Okamoto, Kazuo Ohta. A Practical Secret Voting Scheme for Large Scale Elections. In Advances in Cryptology-AUSCRYPT’92, 1993：244-251.

[7] Kenneth R. Iversen. A Cryptographic Scheme for Computerized General Elections [C]. In Advances in Cryptology-CRYPTO’91, 1991：405-419

[8] Brandon William DuRette. Multiple Administrators for Electronic Voting. (Accessed on 2017-04-04) http://groups.csail.mit.edu/cis/theses/DuRette-bachelors.pdf.

[9] 罗芬芬, 林昌露, 张胜元, 等. 基于 FOO 投票协议的无收据电子投票方案[J]. 计算机科学, 2015, 42(8): 180-184.

[10] 刘高, 刘忆宁, 王东. 一种可验证的多候选人电子投票方案[J]. 计算机工程与科学, 2015, 37(9): 1667-1670.

[11] 张文芳, 熊丹, 王小敏. 基于关联环签名的抗第三方欺诈安全电子投票方案[J]. 西南交通大学学报, 2015, 50 (5): 905-911, 941.

[12] Ben Adida. Helios: Web-based Open-Audit Voting. In Proceedings of the 17th USENIX Security Symposium, 2008:335-348.

[13] Carlos Aguilar Melchor, Guilhem Castagnos, Philippe Gaborit. Lattice-based Homomorphic Encryption of Vector Spaces [C]. IEEE International Symposium on Information Theory (ISIT 2008), 2008:1858-1862.

Analysis and Design of Secure Electronic Voting Protocol Based on Public Cloud

LIU Yu
(Department of Management, Hefei University, Hefei 230601, China)

Electronic voting, characterized by massive data and real time, needs large-scale data operations. These characteristics lead to the failure of deploying traditional plan. Public cloud has a strong computing and storage capacity that can bring new opportunities for the deployment of large-scale electronic voting systems. However, it also brings about new challenges in security. By introducing the widely available public cloud with strong computing and storage ability, this paper proposes a secure electronic voting protocol based on multi-public cloud, which can make full use of the ability of public cloud to process large amounts of data and ensure the electronic voting system secure. The security and performance analysis shows that the proposed protocol can meet the security requirements of the electronic voting system while saving computing and communication expenses.

electronic voting; public cloud; semi-trust; audit

TP39

A

1674-344X(2017)8-0050-06

2017-06-10

安徽省教育厅人文重点项目(SK2016A0775)；安徽省教育厅人文重点项目(SK2016A0768)；安徽省教育厅教学研究一般项目(2015jyxm313)；合肥学院优秀青年人才支持计划(16YQ12RC)资助

刘 玉(1981-)，女，安徽合肥人，副教授，硕士，研究方向为物流信息化、电子商务、信息安全。