一种适用于大规模场景的匿名电子投票系统

高小龙 王 玉 安 鹏 唐 波 刘金会,

1(西北工业大学网络空间安全学院 西安 710129)

2(北京市国防动员委员会办公室 北京 100053)

3(北京明朝万达科技股份有限公司 北京 100142)

4(西北工业大学深圳研究院 广东深圳 518057)

(3325605783@qq.com)

投票是体现民主和公平的一种重要形式，大到如国家领导人的选举，小到如班级内部的民主决定，都离不开投票.近几十年来，随着社会的不断发展，选民的数量越来越多，同时对选举的公平性、匿名性、可验证性等要求也逐步提高.因此，国内外出现了各种各样的电子投票系统.电子投票相较于传统的纸质投票，节省了人力物力财力，同时更加高效、准确和公平.美国、巴西、印度、加拿大等国家已经在国内大范围使用电子投票系统，使用场景涉及政治、经济等多方面.然而在2022年7月，巴西总统认为电子投票系统不安全，要求废除使用.除巴西外，法国、意大利、瑞士和澳大利亚等国家的电子投票系统此前也都曾出现过严重漏洞.因此，为了电子投票的进一步推广和发展，解决其安全性问题刻不容缓.

电子投票系统是基于密码学的综合性系统，现有的电子投票系统所依赖的密码学技术大致可以分为4类：混合网络、盲签名、同态加密和秘密共享.其中，秘密共享技术安全性更强，数据处理效率更高.

本文系统是基于秘密共享的电子投票系统，使用2台或2台以上的投票服务器完成计票工作.只要有1台投票服务器是诚实的就可以保证投票的匿名性.除此之外，本文系统还满足正确性，即完整性和可靠性，既要保证合法有效的投票得到统计，也要保证非法无效的投票不会影响投票结果.关于选票的合法有效，首先考虑选民身份的合法性，其次考虑选票格式的合法性.

1 相关工作

近几十年来，随着科研人员对秘密共享技术的研究不断深入，基于秘密共享技术的电子投票系统得以快速发展.

Schoenmakers[1]提出了一种公开可验证秘密共享(publicly verifiable secret sharing, PVSS)协议，在效率和困难问题假设方面都有所改进，可用于电子投票；Iftene[2]基于秘密共享技术，提出了一种多机构电子投票方案，其中的各个机构可以具有不同的权重；Zwierko等人[3]提出了一种基于代理的安全电子投票方案，代理生成过程中的预计算代替了选民的计算，减小了选民客户端的计算负担；Yuan等人[4]基于Mignotte阈值秘密共享技术，提出了一种分布式的可验证电子投票方案，满足匿名性和可追溯性的同时，提高了计算速度；Gutub等人[5]提出了一种秘密共享方案，该方案基于共享中的并行技术生成秘密输出；Li等人[6]提出了一种具有多级访问机构的多秘密共享方案，不需要任何权限中心，由云服务器进行计票且计算成本低；Joy等人[7]在量子处理器中实现了量子秘密共享协议，应用于一种全新的量子二进制投票协议；Shen等人[8]基于多项式承诺，针对智慧城市应用提出了一种高效的云辅助可验证秘密共享方案；Pilaram等人[9]通过使用基于格的多阶段秘密共享(threshold multi-stage secret sharing, TMSSS)方案共享私钥，提出了一种匿名阈值签名方案，保证安全性的同时效率更高；Hao等人[10]对现有的电子投票方案进行了改进，用屏蔽值掩盖选民的选票，实现了强制抵抗性；Sutradhar等人[11]针对量子秘密共享协议中存在的缺少参与者信息的情况下无法重建秘密的问题，提出了一种解决方案；Kiamari等人[12]提出了一种基于错误学习(learning with errors, LWE)问题的可验证多秘密共享方案，不需要过多的通信就能实现验证性；Tejedor-Romero等人[13]提出了一个名为DiverSEC的分布式远程电子投票系统，确保了投案的匿名性和完整性；Bartolucci等人[14]提出了一种基于区块链技术的电子投票方案；Lu等人[15]设计了一种基于秘密共享的电子投票协议，可以防止投票数提前泄露；Yan等人[16]基于中国剩余定理，提出了一种可逆图像的秘密共享算法；Gutub等人[17]提出了一种分配模型，用于多用户身份验证；Srinivasan等人[18]提出了一个编译器，可以用于生成局部泄露的弹性秘密共享方案；Alkhodaidi等人[19]在基于计数的秘密共享方案中引入一种新算法，通过增加密钥的长度，可以生成无限的共享密钥；马英[20]提出了一种基于隐私计算的数据共享模型，并提出了数据统计分析的应用流程.

虽然基于秘密共享的电子投票方案系统有安全性和数据处理效率方面的优势，但系统组成复杂，因此，应用于大规模投票场景时，系统多方之间的通信复杂度是此类方案的一大挑战.而当电子投票系统要求可验证性时，这个问题就显得更加突出.

本文主要贡献如下：

1) 提出了一个非交互可验证的安全电子投票系统，选举机构可以根据需要，生成相应的选票类型，应用场景广泛.

2) 满足可靠性、完整性、匿名性、不可重用性、可验证性、公平性、合法性和惩罚性等安全属性.

3) 使用一种非交互式的零知识验证方法，在保证安全性的同时，降低了系统的通信复杂度.当系统应用2～6个投票服务器时，对于1万选民以下的小型投票场景，系统耗时在5 s以内；对于10万选民以上的大型投票场景，系统耗时在50 s以内，是可以容忍的耗时.

2 预备知识

2.1椭圆曲线密码学

椭圆曲线密码学(ECC)是一种基于椭圆曲线数学难题的公钥算法，在20世纪80年代首先由Koblitz[21]和Miller[22]分别提出.其最大的优势在于，相比于RSA加密算法，ECC使用相同长度的密钥可以提供更强的安全性.

2.1.1 基于椭圆曲线的加密算法

设置阶段:{p,a,b,G,n}.选取大素数p，a,b∈Fp，基点G=(x,y)，|G|=n，n也为大素数，G为n阶循环群.随机选取d∈[1,n-1]，计算P=dG.

私钥：d∈[1,n-1]；公钥：{p,a,b,G,n,P}.

加密：

1) 对消息M，随机选取临时密钥k∈[1,n-1]，计算c1=kG；

2) 计算kP=(x,y)，c2=mxmodn；

3) 密文为(c1,c2).

解密：

1) 计算Q=dc1=kdG=kP=(x,y)；

2) 计算M=c2x-1modn.

2.1.2 基于椭圆曲线的签名算法

私钥：d∈[1,n-1]；公钥：{p,a,b,G,n,P}.

签名：

1) 随机选取临时密钥k∈[1,n-1]，计算kG=(x,y)；

2) 计算e=Hash(M),r=xmodn以及s=k-1(e+rd) modn；

3) 签名即为(r,s).

验证：

1)sk=e+rdmodn；

2)kG=s-1(eG+rp)=(x1,y)；

3) 验证r=x1是否成立.

2.2 Beaver的安全多方计算协议

每个服务器协议开始时，有输入向量x的份额[xi]，服务器根据运算电路C，想要计算得到C(x).为了保证匿名性，只有所有服务器都诚实才能恢复出电路中所有线路上的值.

算术电路中有加法门和乘法门.

加法门：[y+z]i=[y]i+[z]i.

乘法门：[Ay]i=A[yi].

利用三元组(a,b,c)，服务器计算yz：

1) 计算[d]i=[y]i-[a]i和[e]i=[z]i-[b]i；

2) 计算聚合值

de+db+ea+c=

(y-a)(z-b)+(y-a)b+(z-b)a+c=

(y-a)z+(z-b)a+c=

yz-az+az-ab+c=

yz-ab+c=yz.

2.3 分布式点函数

对于隐私数据xi，有s个服务器，分布式点函数将隐私数据分为[xi]1,[xi]2,…,[xi]s∈Fp，要求满足xi=[xi]1+[xi]2+…+[xi]s∈Fp，且只有当所有的服务器都诚实，才可以恢复出原始的隐私数据xi.

2.4 秘密共享非交互式证明

零知识证明是一方向另一方证明某个命题，而除了对该命题的证明以外，不会泄露任何其他信息，传统的零知识证明算法有非交互式零知识证明(non-interactive zero-knowledge, NIZK)和简短无交互证明(succinct non-interactive adaptive argument of knowledge, SNARK)等.

秘密共享非交互式证明(secret-shared non-interactive proofs, SNIPs)与传统零知识证明的目的基本一致，但相比而言效率高100倍[23].工作流程如下：

1) 客户端评估.

客户端将自己的隐私信息用可加性的分布式点函数进行划分，然后计算验证函数中乘法门的每个输出，并使用插值法将其描述为多项式形式，发送给相应的服务器.

2) 服务器进行一致性检查.

服务器除接收到客户端发送的多项式形式的乘法门输出外，还持有相应的输入份额.服务器据此，利用简单的仿射运算就可以得出每个乘法门的输出.根据计算出的输出插值计算出输出多项式，与客户端发送的输出多项式进行比较.若相同，则一致性检查通过，否则不通过.

3) 多项式验证和份额乘法.

主要借助Beaver的安全多方计算协议中乘法门的计算方法，对2)中乘法门的输出值进行计算.

4) 输出验证.

如果所有的服务器都诚实，每个服务器公布其输出端的份额数据，所有的服务器将监听到的广播消息进行加和，检查最后验证函数的值是否为1，是则符合对格式的要求，否则不合要求，抛弃该数据.

3 系统目标

3.1 系统模型

本文系统中主要涉及四方实体：权威机构、选举机构、选民和投票服务器.其各自在系统中的任务如下：

1) 权威机构.为选民生成公私钥对，用以确定合法的选民群体和认证选民身份.

2) 选举机构.主要负责发起投票，涉及确定候选者名单、合法的选民名单以及其他相关参数等内容.

3) 选民.对选举机构发起的投票内容进行合法投票.

4) 投票服务器.最少有2台，主要负责接收选民发来的选票，将合法的选票计入投票结果.

如图1所示，本文系统的基本应用流程如下：

1) 选民注册及发起投票(①②).首先，选民在权威机构进行注册用于表征身份；然后，由选举机构确定合法的选民群体，并发起投票，将投票和选民的相关信息发送给投票服务器，将投票相关信息和对应的选民序号发送给选民.

2) 选民上传选票(③).大量合法的选民在各自客户端将选票数据及其验证信息发送到少量的几个投票服务器中.

3) 验证及累加选票(④).由投票服务器对选民进行身份验证，对选票进行格式验证，验证通过后，将选票信息存储在本地聚合器中.

4) 广播投票数据(⑤).当各个投票服务器的聚合器中新选票数目达到一定值，将聚合器中的信息进行广播.所有投票服务器收到彼此的广播后，将广播的信息进行加和操作，得到这些选票的统计数据.在整个投票过程中，系统各方不知道任何一位选民的选票内容，保证了系统匿名性.

图1 电子投票系统工作模型

3.2 安全要求

本文系统要求实现以下安全属性：

1) 可靠性.非法无效的选票极大的概率不会被计入投票系统的聚合器.

2) 完整性.合法有效的选票应该以极大的概率被计入投票系统的聚合器.

3) 匿名性.选民的投票内容保密，本文系统中，可以有2台或2台以上的投票服务器，只要有1台投票服务器是诚实的，就可以保证选票和选民之间对应关系的不可知.

4) 不可重用性.任何选票，不能被多次计入投票统计结果，任何人都只能投1次票.

5) 可验证性.没有人能伪造投票结果，选民可以验证自己的投票是否被统计.

6) 公平性.投票参与的各方都无法在投票未结束前知道选票消息，直到所有投票服务器广播了其聚合器中的数据.

7) 合法性.只有经过授权的选民，其所投出的选票才合法有效，可以被计入投票统计结果.

8) 惩罚性.如果某选民具有选票多次重用、多次选票格式错误等恶意行为，系统能够对该选民进行惩罚.

4 具体方案构造

本节将对投票系统中运行的完整细节进行描述，涉及划分选票的分布式点函数和投票服务器间验证选票有效性的安全多方计算等实现细节.

1) 选民注册.

在投票开始之前，每个潜在的选民和候选人都应该在选举机构认可的权威机构进行注册，权威机构为每个选民i分发公私钥对(PKi,SKi).公钥PKi可以用作选民i的邮箱地址或者标识，类似于选民的名字，可以由选举机构进行公开.

2) 投票发起.

由选举机构根据需求发起投票.

首先，选举机构确定选民群体L，将合法选民的公钥列表(由权威机构或选民提供)整理，得到L={PK1,PK2,…,PKn}，并为每个选民生成1个应用于此场景下的序号Vi，要求序号空间2λ远远大于实际的选民数量n，借助该序号系统可以快速识别非法用户，这里的空间长度λ暂定为128 b.

然后，选举机构确定候选人信息和投票格式.选举机构将合法的选民公钥列表L={PK1,PK2,…,PKn}、与之对应的选民序号V={V1,V2,…,Vn}和生成的投票格式T发送给投票服务器.投票服务器将依据(L,V,T)对选民选票进行验证.

最后，选举机构将选民序号用选民i投票使用的公钥进行加密EncPKi(Vi)并发送给选民i，将投票格式T公开.至此，投票的前期准备工作结束，计票正式开始.

3) 选票上传.

如图2所示，选民i首先根据投票格式T填写合法的选票内容，然后使用仿射可聚合编码方法(affine aggregatable encodings, AFEs)[23]编码生成选票Ticketi，然后将选票使用可加性的分布式点函数进行划分，划分的个数和投票服务器的个数s相同.

图2 投票上传

图3 选票信息聚合

选民客户端首先根据分布式点函数fv,m:[2λ]→{0,1}|m|，将自己的选票Ticketi分为s份{Ticketi1,Ticketi2,…,Ticketis}.

此外，选民使用SNIPs[23]方法生成关于选票的证明πi={πi1,πi2,…,πis}，在不泄露选票内容的前提下，证明自己的选票Ticketi是有效的.

然后，将划分后的选票用选民自己的私钥SKi进行ECDSA签名，和对应的证明、选民的序号Vi一起，用投票服务器j的公钥PKserverj进行加密，发送到相应的投票服务器j，j∈(1,s)，如

EncPKserverj(SignSKi(Ticketij),πij,Vi).

4) 选票信息聚合.

投票服务器j收到选民i的选票EncPKserverj(SignSKi(Ticketij),πij,Vi)后，首先用自己的私钥SKserverj解密提取出选民序号Vi，验证Vi在本次投票中是否有意义.如果没意义，丢弃该选票，如果Vi已经被标记，将Vi对应的PKi提交给选举机构进行惩罚；否则，进一步用Vi对应的公钥PKi对SignSKi(Ticketij)进行验证，验证失败则丢弃；验证成功则利用πij验证Ticketij的有效性.若上述验证通过，将Ticketij的信息压入投票服务器j的聚合器中，同时将Vi进行标记.如图3所示:

5) 公布投票结果.

当聚合器中聚合了一定数目的选票时，各个投票服务器将自己的聚合器数据进行广播，系统各方通过监听广播，都可以获取投票统计数据和投票成功选民序号.与此同时，选举机构公示投票结果和投票成功的选民序号，可供选民不用监听广播直接请求获得.

5 安全性和性能分析

5.1 安全性分析

本文系统中，可以有2台或2台以上的投票服务器，本文的安全性分析是以2台投票服务器、选票形式为多选1、无特权选民的情况为例进行分析.

1) 正确性.

这里的正确性直接依赖于分布式点函数和秘密共享非交互式证明方法的正确性，本文系统可以大概率地分辨出针对格式的有效和无效选票.采用有效的选票，丢弃无效的选票，从而保证系统的可靠性和完整性.

声明：2台投票服务器A和B，在验证选票合法性的秘密共享非交互式证明协议开始时，分别持有份额向量wA∈Fn和wB∈Fn，并且满足w=wA+wB∈Fn，若协议验证w的汉明重量为1，则认为该选票正确，协议出错的可能性为ε=O(1/|F|).

取F的大小为2λ，其中改变安全参数λ的取值，可以使错误概率ε足够小.

该声明的正确是因为秘密共享非交互式证明协议只有当满足以下条件时才会接收错误的选票：

① 秘密共享非交互式证明的鲁棒性要求，只有当输入满足投票内容对应的关系式时才接受选票；

② 不止1种非零选票w，可以使得等式c2-mC=0成立.其中C为选票对应的运算电路，该等式成立意味着2个内容不同的选票生成的运算电路C是相同的.

这2种错误发生的可能性ε在域F中可以忽略不计.

2) 匿名性.

选民的投票内容保密，本文系统中，只要有1台投票服务器是诚实的，就可以保证选票与选民对应关系的不可知.

这里的匿名性包括分布式点函数和秘密共享非交互式证明协议的零知识性.

对于分布式点函数，假定一个仿真算法Sim可以产生输出.当w=wA+wB∈Fn只能对应1个汉明重量为1的向量，这些输出的分布与正常工作的投票服务器所看到的分布在计算上无法区分.因此，敌手运行Sim程序和在正常工作中获得的信息一样多，因此证明了分布式点函数的零知识性.

对于秘密共享非交互式证明的安全性证明，在文献[23]中有完整的证明步骤，适用于此处.

3) 不可重用性.

任何1张选票，不能被多次计入投票统计结果.本文系统中.成功进行过投票的选民，其选民序号会被标记，因此，任何一位选民都无法进行2次及以上的成功投票.

该安全属性的保证间接依赖于分布式点函数和秘密共享非交互式证明的正确性.

假设当所有服务器对某条选票w都认证通过了，此时，所有服务器中的对应选民序号Vi都会被打上标记.聚合器累计一定数目的选票后，服务器开始广播，仅当所有服务器广播，认定某序号Vi被打上标记后，才认为投票成功.

此时，假设序号为Vi的选民再次投票，根据系统的安全性假设：至少有1个服务器是诚实的.那么，诚实的投票服务器将选票份额及其证明丢弃，缺少1份选票份额及其份额，分布式点函数就无法计算出w=wA+wB∈Fn，此时秘密共享非交互式证明协议的验证函数Vaild(·)≠1，这2项的保证在正确性部分中已经得到讨论，只有可以忽略的错误概率.

4) 可验证性.

系统各方都无法伪造投票结果，选民可以验证自己的投票是否被统计.投票成功的选民序号Vi会被选举机构公开，选民知道自己投票的时间段，只要找到这个时间段成功投票的选民序号{Vi}，查看其中的选民序号就可以验证自己投票是否成功.

只要有1个服务器是诚实的，就可以保证可验证性，这条性质的保证间接依赖于分布式点函数和秘密共享非交互式证明的正确性.

首先讨论验证投票是否成功.只要有1个投票服务器是诚实的，投票不论成功与否，投票是否成功和验证是否存在一定保持一致.

再假设投票成功，讨论验证过的真实投票和选民原始投票不一样的可能性.根据前面对系统正确性的分析，这种可能性是可以忽略的.对于秘密共享非交互式证明来说，和系统正确性中的讨论结果一致.

5) 公平性.

对于该电子投票系统模型中的四方实体：选民、投票服务器，选举机构和权威结构，没有任何一方可以在投票未完成前，知道投票的阶段性状态.直到所有投票服务器广播了其聚合器中的数据，选举机构宣布投票结束后，各方才能知道投票结果.

这里的公平性直接依赖于系统的匿名性.在匿名性得到满足的情况下，投票未结束前，所有的选票信息都分布在各个投票服务器的聚合器数据VoteDataj中，只有投票最后阶段，所有投票服务器的VoteDataj按照分布式点函数算法进行恢复，才能最后得到投票结果VoteData.

对于系统匿名性的讨论分析这里不再累述.

6) 合法性.

只有经过授权的选民，其所投出的选票才合法有效，可以被计入投票统计结果.本文系统首先使用选民序号机制快速判断选民身份的合法性，然后再用选民序号Vi对应的公钥PKi进一步验证其签名的正确性.

合法性依赖于对用户序号的查验和对用户签名的验证.

首先，序号空间的大小为2λ，这里λ暂定取128 b，远远大于几乎所有的投票场景下的选民数量，因此，敌手难以对选民序号进行碰撞攻击.对于有n名选民的投票场景，碰撞发生的可能性ε=O(n/2λ).

除此之外，对用户私钥签名的验证进一步确保即使发生碰撞，也可以依赖签名的合法性验证选民的合法性.而使用用户序号进行先验的方法简单有效，可以快速筛去大多数恶意的选票，增强系统对拒绝服务攻击的抵抗.

7) 可惩罚性.

因为投票服务器可以简单地将选民序号进行标记，如果某选民存在选票重用、投票格式多次错误等恶意行为，那么，投票服务器就可以将该选民序号发送给选举机构，由机构对该序号Vi对应的选民i，根据实际情况和影响进行处罚.

可惩罚性的实现间接依赖于系统的正确性，因为正确性保证，所有投票服务器都认定的恶意选民会被惩罚，同时只要有1台诚实的投票服务器，行为合法的选民就不会被惩罚.

本文与部分文献安全性比较如表1所示：

表1 电子投票系统安全性比较

5.2 性能分析

为了对系统性能进行评估分析，使用1台戴尔笔记本进行实验，具体配置为Intel®CoreTMi7-8750H CPU，2.20 GHz，8 GB RAM.

为了保证电子投票系统的匿名性，验证过程需要保证零知识性，与使用其他零知识证明算法的电子投票系统相比，本文系统中选民客户端和投票服务器的计算复杂度都更低.尤其是计算最为耗时的指数运算，NIZK和SNARK都无法避免，而本文系统不涉及指数运算，因而为实现零知识所付出的计算成本较低，具体分析如表2所示：

表2 电子投票系统客户端与服务器的计算复杂度对比

注：M为验证函数中乘法门的数量.

本文系统可以应用于多种投票类型，尤其是复杂的投票场景.现在以5台投票服务器的场景为例，研究选票内容长度和选民的客户端耗时之间的关系.数据来自1 000条相同长度的选票取均值，如图4所示：

图4 选票长度和客户端耗时的关系

由图4可以看出，选票内容长度在29b以下时，平均耗时在10 ms以内，长度达到212b时，每张选票的平均耗时也在80 ms以内.长度为212b的选票足以应付绝大多数应用场景.

本文系统可以使用多个投票服务器，此处以2个候选人、2选1的选票种类的场景为例，对投票系统耗时和投票服务器数量、选民数量之间的关系进行分析，每种情况下的数据为8次重复测试取平均值的结果.如图5所示：

图5 投票耗时与投票服务器和选民数量的关系

图5显示，当选民数量在1万人以下时，投票耗时与服务器数量关系不明显，从2台投票服务器到6台投票服务器，投票耗时都在5 s以内.当选民数量达到5万及以上时，系统投票耗时大大增加，同时受投票服务器数量影响明显.当投票服务器的数量达到6台时，系统耗时达到了25 s.当在10万选民、2台投票服务器时，投票时间少于20 s，当投票服务器的数量为6，系统耗时依然在50 s内.

由图5可知，对于1万人以内的小型投票应用场景，该电子投票系统的系统耗时都在5 s以内，即使在10万人的大型投票应用中，也可以把投票耗时维持在50 s以内，适用于大多数投票场景.

6 结 论

本文设计了一种适用于大规模场景的匿名电子投票系统，使用1组投票服务器对一定数量的投票结果进行聚合统计，保护了选民的隐私，同时防御了恶意投票行为.一方面，通过非交互式验证的方式满足了电子投票系统对恶意选票的抵抗能力，也没有显著增加系统各方之间的通信复杂度和计算复杂度；另一方面，秘密共享非交互式证明的零知识性保证了系统匿名性.对于绝大多数的投票场景，本文系统在时间开销方面都表现优秀，尤其是在10万人的大型投票场景中，系统耗时也可以满足多数应用要求.这些投票是在各选民平等投票的假定下进行的，未来将进一步考虑存在特权选民的投票场景.