李亚伟,王维琼,谢 琼

(长安大学 理学院,西安 710064)

电子投票是基于密码学技术设计并通过网络实现的一种投票方式.与传统的唱票表决相比,电子投票的投票和计票过程更高效、选举结果更准确.随着互联网与密码学技术的发展,电子投票得到大力发展.近年来,电子投票系统在许多西方国家的选举中得到应用,其中爱沙尼亚首先在国家层面的选举使用电子投票.目前,美国、加拿大等地的议会和立法中已开始使用电子投票.我国部分领域也在尝试使用电子投票,其中2005年上海市长宁区某街道进行团支部直选时首次在政治领域使用电子投票.

最早的电子投票方案可追溯到1981年,由 Chaum[1]基于混合网络和RSA 公钥加密体制提出.1992年,Fujilka 等人[2]基于盲签名提出了可适用于大规模选举的FOO 方案,使电子投票走向实用.1997年,Cramer等人[3]首次提出了多候选人的电子投票问题,并利用ElGamal 加密系统设计了一个多选一的电子选举方案,该方案需要可信的计票中心参与接收并统计选票.2001年,Damgård 等人[4]基于Paillier 加密系统提出了一个多选多的电子投票方案,该方案无法避免重复投票现象且需要可信计票机构参与.2006年,仲红等人[5]基于安全多方求和提出一个无需第三方计票机构参与的多选多电子投票方案,但选举结束后会公开所有候选人的得票数.2012年,Pang 等人[6]基于混合网络和PET 协议提出一个多选多电子选举方案.2015年,杨婷婷等人[7]基于安全多方排序协议设计了一个多选多电子投票方案,但方案使用的排序协议要求参与者两两之间有安全信道,对通信环境要求较高.2018年,娄宇等人[8]基于全同态加密算法提出一个多候选人的电子投票方案,其计票工作由第三方计票中心完成且公开所有候选人得票数.2019年,刘霆等人[9]将随机线性分组码的秘密分享应用于多候选人电子投票方案中,解决了防投票记录篡改、关键信息存储的安全性等问题.同年,付伟伟等人[10]基于随机矩阵提出一个多选一电子投票方案,该方案满足可验证性,但需要计票中心参与.2021年,邵清等人[11]基于ElGamal 强盲签名和区块链技术提出了电子投票方案,此方案没有明确选举场景、选票形式等,重点关注选票的可验证性、不可篡改性等问题,且用智能合约取代可信第三方完成计票.文献[12-16]等结合区块链、同态加密等技术提出了完整的安全电子投票系统.

保密选票内容是安全电子投票方案的一个基本要求.但在计票阶段,候选者得票数同样属于关键信息.因为破坏者可能根据候选人之间得票数的差异,在下次选举时通过拉拢选票的手段,破坏选举的公平性.因此,文献[6]首次提出了投票方案中“全隐私”的概念,是指既保护选民选票内容又保护候选人得票数.上述文献[6,7]提出的方案保护了落选者得票数.

为保密选票内容,可以用加密技术对选票信息进行加密.同时为方便后续计票,加密后的信息需要满足一定的同态性质.而同态加密[17]满足上述需求,能够在不解密密文的前提下,通过对密文的操作实现对相应明文的计算.姚期智[18]提出的安全多方计算主要解决互不信任的数据拥有者之间的安全协同计算问题,基于此思想设计电子投票方案可解决计票时第三方机构参与的问题.

尽我们所知,已有的电子投票方案仅统计候选人的赞成票数.然而在实际的选举场景中,时常会遇到以下情况:某些候选人赞成票数名列前茅,但选民对其反对声音也很高.例如,在有50 位合法选民的选举活动中,有两位候选人得票情况如表1.根据已有的电子投票方案候选人2 获胜,但是候选人1 当选更能反映选民的意愿.

表1 可能的得票情况

为了避免上述有争议的选举结果出现,本文在综合考虑候选人赞成票数和反对票数的前提下,基于安全多方计算,结合ElGamal 同态加密系统提出一个无需第三方计票机构参与、全隐私的多选多电子投票方案.

1 预备知识

1.1 半诚实模型及其安全性定义

1.2 ElGamal 加密系统

1.3 IsEq 协议

2 多选多电子投票方案的设计

2.1 投票场景

2.2 表决方式

2.3 投票方案

本文设计的投票方案分为初始化阶段、投票阶段和计票阶段,具体过程如下:

2.3.1 初始化阶段

2.3.2 投票阶段

2.3.3 计票阶段

3 方案分析与比较

3.1 正确性分析

3.2 全隐私性分析

定理2 得证,即本方案满足对选民选票信息的隐私保护.

由于本方案仅输出获胜候选人的名单,且即使在计票阶段每位候选人保存了获胜候选者对应的获胜票数,但其无法将票数与候选人对应起来,则方案满足对获胜者得票数的隐私保护.同时,由于门限ElGamal 加密系统的特性,任何人都无法解密式(4)中的wj,sj,因此无法得到落选者的得票数,即方案满足对落选者得票数的隐私保护.

综上,本方案满足全隐私性,并且保护了所有落选者的得票数.

3.3 其它安全性质分析

(1)无收据性是指任何选民都无法向他人证明自己的选票.本方案中每位选民将加密选票发送给所有候选人,由于门限ElGamal 加密系统的特性,选民靠自己不能解密任何密文,则无法向候选人证明自己的选票.

(2)公平性是指所有选民同时得到选举结果.该方案的选举结果在计票阶段结束之后输出,任何人都无法提前获知选举结果.因此,本方案满足公平性.

3.4 复杂性分析与比较

本文设计的方案使用了门限ElGamal 加密系统,分析时只考虑费时的模指数运算,每次加密操作需要2 次模指数运算,每次解密操作需要n+m+1次模指数运算.

投票阶段,所有选民需要3nm次加密.计票阶段,所有选民和候选人最多执行m(n+2+k)次加密和m+k次解密.因此投票阶段和阶段最多需要模指数运算2[3nm+m(n+2+k)]+(m+k)(n+m+1)次.计票阶段,最多需要调用m(3n+2k+t+1)次IsEq 协议,根据文献[23],本文执行IsEq协议所需模指数运算复杂度综上所述,本方案的计算复杂度为.

将本文设计的方案与文献[6,7]中提出的全隐私多候选人电子投票方案进行对比,如表2所示.本方案考虑了候选者所得反对票数,且其全隐私性实现了对所有候选者得票数的保护.

表2 全隐私电子投票方案的对比

4 结语

为使选举结果更符合选民的意愿,本文首次考虑了候选人反对票数.在此基础上提出了一个满足全隐私性、无需第三方参与的多选多电子投票方案,并且本方案的全隐形实现了对所有候选人得票数的保护.此外,分析表明方案同时满足公平性和无收据性.下一步工作将研究符合实际应用场景需求、满足更多安全性质且高效的电子投票方案.