基于关联环签名的抗第三方欺诈安全电子投票方案
2015-01-13张文芳王小敏
张文芳, 熊 丹, 王小敏
(1. 西南交通大学信息科学与技术学院,四川 成都610031;2. 西南交通大学信息安全与国家计算网格四川省重点实验室,四川 成都610031)
传统的选举方式需要投票人去指定地点投票 和人工计票,效率低且人为因素的过多引入易造成失误和违规行为. 与传统人工选举相比,电子选举可以节约大量的人力物力,且具有公平、安全和高效的明显优点,已成为信息安全领域的一个热点研究问题.
为设计出安全实用的电子投票系统,研究者们先后提出了基于不同密码技术的投票方案.Chaum在公钥密码体制基础上使用Mix 机实现匿名通信,提出了第1 个密码学意义上的电子选举方案,要求只有在所有投票者合作的前提下才能完成投票,协议效率和可行性较低. 在此基础上,随后出现了一系列基于Mix-net 的电子投票系统[1-6],协议的安全性和可靠性有所提高.为确保每个Mix 服务器在处理选票过程中无法篡改选票,这类方案需要大量的零知识证明计算,协议运行效率较低.虽然文献[2]Mix-net 电子投票方案实现了大规模选举,但该方案的安全性建立在注册中心绝对可信的基础上.
Fujioka 等采用比特承诺与盲签名技术,实现了第1 个实用的适合于大群体的电子投票方案(简称FOO 方案)[7],协议运行效率有了很大提升,但该方案存在选票碰撞、选票可能无法打开以及管理中心可以冒充投票者进行投票等问题.此后受FOO 协议启发,出现了多种基于群、盲签名的电子投票方案.文献[8]提出了一种基于RSA 密码体制的电子投票协议,该方案不允许投票者中途弃权,难以满足投票协议的实际需求.2003 年,陈晓峰等利用群签名协议和时限承诺协议设计了一个电子投票方案[9],虽然解决了选票碰撞问题,但只有在注册机构与管理机构或计票机构诚信公正的前提下才能保证投票者身份的匿名性,否则将会通过选票追踪到投票人的所有信息.2011 年,Chen 等提出了一个基于双陷门承诺和盲签名技术的投票方案[10],能够满足电子投票协议的基本安全要求,但是该方案需要借助于匿名通信信道完成投票过程,实用性不高.2013 年,Ghavamipoor H 等设计了一个匿名电子投票协议[11],利用投票者无需生成公私钥对的方法提高了协议效率,但投票阶段必须依赖于一个不可追踪的安全电子邮件系统向认证机构发送选票,妨碍了其实际应用.
关联环签名不仅能够保证签名者身份的匿名性,又可实现选票的不可重用性,适合于需要保护投票者身份不可泄露的电子投票系统. 2004 年,Liu 等首次利用关联环签名构造了一个匿名投票系统[12],由于将计算量较大的环签名用于投票环节,投票效率不高,也未能实现选票的秘密性和选举过程的公平性. Tsang 等在文献[12]的基础上,提出了利用简短关联环签名代替原有环签名的改进方案[13].由于其投票机制与文献[12]相似,协议效率仍然较低,无法实现大规模选举.文献[14]的环签名电子投票方案则存在选举证书设计缺陷导致可以冒充他人抢先投票,使合法投票者无法行使相应的选举权,同时破坏了投票协议的不可重用性和稳定性.
针对现有方案存在的选票碰撞、投票者无法中途弃权、投票效率低下,以及由第三方机构不诚实行为导致的安全隐患等问题,本文提出了一个基于关联环签名的高效安全电子投票方案.方案使用身份序列码解决了选票碰撞问题,同时,通过在投票过程中引入可公开验证的信息公告机制允许投票者在任意阶段中途弃权,并防止了第三方机构的不诚实行为对投票过程的破坏及对选票结果的干扰.此外,将计算量较大的关联环签名用于注册阶段,在后续的投票和计票阶段则利用基于身份序列码的个体签名进行身份验证,无需任何匿名通信信道,有效提高了投票协议效率,适合于大规模选举.
1 电子投票基本性质
一个安全的投票方案应具备以下性质:
(1)合法性:只有合法投票者才能参与投票,其他未被授权者不能参与投票.
(2)匿名性:选票对应的投票者身份是匿名的,即任何人都无法将一张选票和某一投票者联系起来.
(3)秘密性:选票的内容是保密的,除投票者自身外,其他任何人都无法知道其投票内容.
(4)公平性:在选举的中间过程,任何人的行为均无法影响选举结果.
(5)不可重用性:每个合法投票者只能参与一次投票活动,不能重复投票.
(6)完整性:所有有效选票都应该正确地计算在最终的选举结果中.
(7)稳固性:不诚实的投票者不能破坏选举.
(8)广义可验证性:任何人都可以根据公布的选举信息验证选举结果的正确与否.
2 关联环签名机制
环签名是Rivest 等在如何匿名泄漏秘密的背景下提出的一种新型签名技术[15],其最大特点是能够实现签名者身份的无条件匿名性.随后针对不同应用环境、满足特殊属性的环签名被相继提出[12,16-20],关联环签名[12]为其中一种,它能确定两个不同环签名是否由同一用户生成.
为便于描述本文投票方案,首先简要介绍关联环签名机制.
2.1 参数初始化
设q 是一素数,G=〈 g〉是q 阶子群,在G 中求解离散对数问题是困难的. H1∶{0,1}*→Zq,H2∶{0,1}*→G 是单向散列函数.对i=1,2,…,n,每一用户Ui拥有公私钥对(xi,yi),且yi=gxi.
2.2 签名生成
设消息m∈{0,1}*,公钥集合为L ={y1,y2,…,yn},签名者Uπ私钥为xπ,对应公钥为yπ,其中1≤π≤n,Uπ利用如下算法产生关联环签名:
(1)计算h = H2(L)和= hxπ,然后选择u∈RZq,计算cπ+1=H1(L,~,m,gu,hu).
(2)对i = π + 1,…,n,1,…,π - 1,选择si∈RZq,计算ci+1=H1(L,~,m,gsi,ycii,hsi~yci).
(3)计算sπ=u-xπcπmod q.
最后,输出签名σL(m)=(c1,s1,s2,…,sn,~).
2.3 签名验证
验证者收到关于m 及L 的签名σL(m)=(c1,s1,s2,…,sn,~)后,按如下步骤验证签名的正确性:
(1)计算h=H2(L),然后对于i =1,2,…,n,计算z'i=gsi,z″i=hsi~yci,ci+1=H1(L,~,m,z'i,z″i),i≠n.
(2)检验c1=H1(L,~,m,z',z″n)是否成立,如果成立,则接受签名,否则拒绝此签名.
3 基于关联环签名和盲签名的电子投票方案
3.1 相关定义
投票者(Vi):作为环体(V1,V2,…,Vn)中的某一成员对候选人进行投票.
注册中心(R):验证每一个投票者身份的合法性,为合法投票者发放身份序列码Ni,并为Ni签名.
管理中心(A):验证盲化选票的合法性,并为合法选票进行盲签名.
计票中心(C):对投票者去盲后的选票进行验证并签名,然后统计并公布最终结果.
R,A,C 各有自己的RSA 签名系统. R 在其签名系统中的公钥为(eR,nR),私钥为dR;A 在其签名系统中的公钥为(eA,nA),私钥为dA;C 在其签名系统中的公钥为(eC,nC),私钥为dC.
3.2 方案描述
本文电子投票方案的工作流程如图1 所示,分为注册、投票和计票3 个阶段,详细过程见下文的注册协议、投票协议和计票协议.
图1 电子投票方案示意Fig.1 Diagram of the proposed electronic voting scheme
3.2.1 注册协议
合法投票者到注册中心R 进行匿名注册,具体步骤如下:
(1)按3.1 节方法对系统进行初始化,其中公钥集合L={y1,y2,…,yn}由所有具备选举资格者公钥组成.
(3)注册中心R 按3.3 节的签名验证算法,首先验证签名σL(mi)=(c1,s1,s2,…,sn,~)的正确性.若正确,则检查该σL(mi)中的~y 值是否已存在于注册列表List1 中,如果存在,说明Vi为重复注册,拒绝此次请求;如果不存在,说明Vi为新的合法投票者.
如果Vi是新的合法投票者,注册中心R 利用收到的公钥eVi验证签名SdVi(mi)是否正确. 若正确,注册中心R 为Vi随机选取一个具有唯一标识的身份序列码Ni,并对Ni签名,签名结果记为SdR(Ni)=mod nR;若不正确,R 要求投票者重新发送. 最后,注册中心R 将{Ni,SdR(Ni)发送给投票人Vi. 同时,将{mi,σL(mi),SdVi(mi),Ni,SdR(Ni),eVi}保存到注册信息表List1 中.
注册结束后公布List1,接受公开验证.在注册公示时间t1内,未能在注册期及时注册的投票者可以公开注册,公布自己的签名,要求注册中心为其发放身份序列码和对应签名,并公布其注册信息于List1 中;同时已注册者查询List1,如果查询不到自己的注册信息,投票者可以公示自己的签名{mi,σL(mi),SdVi(mi),Ni,SdR(Ni),eVi},并公开验证签名σL(mi)和SdVi(mi)的正确性,进而要求注册中心R 在所有人的监督下为其发放身份序列码和对应签名{Ni,SdR(Ni)},并公布投票者相应信息{mi,σL(mi),SdVi(mi),Ni,SdR(Ni),eVi}于List1上.上述方法能够有效防止注册中心的不诚实行为.此外,若公示时间结束后,投票者依然没有注册,则被视为自动弃权.
3.2.2 投票协议
在规定的投票期限内,投票者按照如下协议进行投票(只有Ni存在于List1 的投票者才有权参与如下投票过程):
(1)投票者Vi首先生成电子选票EVi={CiNi},然后随机选择一盲化因子ri对选票EVi进行盲化,记盲化后的选票为EBVi=EVi·reAi mod nA. 其中,Ci为某一合法候选人.
(2)Vi对选票EBVi进行签名,记为SdVi=mod nVi,然后将{Ni,EBVi,SdVi(EBVi)}发送给管理机构A.
(3)管理机构A 首先检查Ni是否已经存在于投票信息表List2 中.如果已经存在,说明投票者Vi重复投票,拒绝此次请求;如果不存在,验证签名SdVi(EBVi)的正确性.
翻译诗学研究不可避免地带有跨语言、跨文化、跨学科的性质。《翻译诗学》一书突破了语言学、翻译理论的拘囿,涉及到中国古代诗论、画论、文论,在建构过程中,参考了西方的文学理论、语言哲学和现象学等理论,实现了“翻译和诗学、中西哲学和美学、中西文论和语言理论、中国译学史料和翻译实践的紧密结合”(同上)。
若签名SdVi(EBVi)正确,A 为Vi的盲化选票EBVi进行签名,记为SdA(EBVi)=mod nA,并将{EBVi,SdA(EBVi)}发 送 给Vi,同 时 将{Ni,EBVi,SdVi(EBVi),SdA(EBVi)}保存到投票信息表List2 中;若不正确,则要求投票者重新发送.
投票结束后公布List2,接受公开验证.在投票公示时间t2内,未能在投票期及时投票的投票者可以公开投票,公布自己的盲化选票和签名,要求管理机构A 为其发送签名并将其投票结果公布于List2 中;同时已投票者查询List2,如果查询不到自己的投票信息,投票者可以公布自己的盲化选票和签名{Ni,EBVi,SdVi(EBVi)},在所有人的监督下,要求管理机构A 为其签名并发送{EBVi,SdA(EBVi)}给投票者,并将其投票结果{Ni,EBVi,SdVi(EBVi),SdA(EBVi)}公布到List2 中.如果公示期结束,投票者依然没有投票,则被视为中途弃权.
3.2.3 计票协议
投票人Vi将消盲后的选票公布于计票信息表List3 中,计票中心C 根据List3 统计并公布选举的最终结果(只有Ni存在于List2 中的投票者才有权参与如下计票过程):
(2)Vi对选票EVi签名,得到SdVi(EVi)=mod nVi,然后Vi将{Ni,EVi,SdA(EVi),SdVi(EVi)}公布于List3 中.任何人均可验证签名SdA(EVi)和SdVi(EVi)的正确性.若SdA(EVi)和SdVi(EVi)都正确,说明选票EVi为Vi的合法投票,并且EVi没有被篡改.如果Ni在List3 中重复出现,说明投票者Vi重复投票,仅对其选票统计一次.
超过计票期限,投票者依然未将选票公布于List3 中,则被视为中途弃权.
(3)计票中心C 根据List3 统计并公布投票的最终结果.
4 方案分析
4.1 投票协议安全属性分析
(1)合法性
只有具备选举资格者才拥有环签名公钥集合L 对应的某一私钥,并利用私钥生成正确的关联环签名,保证只有合法投票者才能参与后续投票,未被授权者无权参与投票.
(2)匿名性
在投票之前,投票者Vi利用关联环签名进行匿名注册,注册中心R 只能确认投票者Vi为n 个合法投票者之一,但无法确定投票者真实身份. 同时投票者为自己生成一对公私钥对(eVi,dVi),与注册中心为其发放的具有唯一身份标志的序列码Ni相对应,并将Ni和(eVi,dVi)用于后续投票和计票过程的身份验证.任何人只能确定Ni对应某一合法投票者,却无法得知其真实身份.
(3)秘密性
方案在投票阶段使用盲签名技术盲化选票,管理中心A 接收及公布的选票均是盲化后的选票,因此在计票之前,除投票者自身外任何人都无法获知选票内容.
(4)公平性
投票阶段,采用盲签名技术对选票进行盲化并由管理中心A 签名,除投票者本人外,任何人不知道选票内容,因此选举的中间结果不会被泄漏,并且管理中心A 的不诚实行为在List2 公布后能被及时发现和有效制止.因此,在选举的中间过程,任何人的行为均无法影响选举结果.
(5)不可重用性
利用关联环签名的可链接性,注册机构R 能有效判断任意两个关联环签名是否来自同一投票者,如有不诚实投票者试图重复注册,将会被发现,保证了任一合法投票者只能进行一次注册. 同时,投票者自己生成的公私钥对和注册机构为其发放的身份序列码Ni都具有唯一性,且盲化选票EBVi和身份序列码Ni将被对应地公布于投票信息表List2 中,若投票者在投票阶段重复投票将会被发现,因此每个合法投票者只能进行一次投票.
(6)完整性
所有注册信息、投票信息以及计票信息不仅可以被注册中心R、管理中心A 和计票中心C 验证,而且由于这些信息被相应地公布于公告信息表List1、List2 和List3 中,因此任何人都能验证投票者信息的正确性. 当投票者发现其信息未被公布时,可公布相应信息并公开验证相关签名的有效性,因此可以在所有人的监督下,要求注册中心、管理中心和计票中心重新公布其信息并统计最终结果.因此,所有有效选票都能被正确地计算在最终的选举结果中.
(7)稳固性
只有具备选举资格的成员才能成功注册,进而参与后续投票.在注册阶段、投票阶段以及计票阶段拒绝注册、拒绝投票及拒绝计票的投票者均被视为中途弃权. 而每一阶段的协议运行都具有独立性,因此投票者在任意阶段的弃权行为不会影响选举的正常进行.此外,不可重用性保证每个投票者只能进行一次投票. 综上,投票者的不诚实行为无法破坏选举过程.
(8)广义可验证性
由于选举相关信息被分别公布于公告信息表List1、List2 和List3 中,任何人都可验证注册信息、选票信息和计票结果的正确性,因此方案具有广义可验证性.
4.2 性能分析
(1)有效避免由第三方机构欺诈行为引起的安全隐患
本文方案虽然存在注册中心、管理中心和计票中心等第三方机构,但由于在选举的任意阶段都采用独立的信息公告机制,且分别设置了公示时间,供投票者查询自己的信息是否得到正确公布,同时,在所有人的监督下能够及时发现并有效制止第三方机构的不诚实行为.因此任何第三方机构单独或者合谋均无法冒充投票者进行投票,也不能篡改或者删除投票者的投票信息,避免了第三方机构的恶意行为或合谋攻击引起的安全隐患,即方案的安全性不依赖于对第三方机构绝对可信的前提假设.
(2)无需借助匿名通信信道
方案利用关联环签名对投票者进行无条件匿名注册,同时为投票者发放具有唯一性的合法临时身份Ni用于后续的投票及计票过程,任何人只能确定投票者的合法性而无法得知其真实身份. 因此,任一阶段均无需借助匿名通信信道隐藏投票者身份.
(3)选票的抗碰撞性
由于本方案在盲化选票中加入具有唯一标识的投票者身份序列码Ni,保证所有选票互不相同,因此具有选票抗碰撞性,进而保证选举过程的公平性.
(4)投票者可在任意阶段中途弃权
由于不存在可信中心的限制,且方案各个阶段均采用信息公告机制,具备广义可验证性,因此可以保证选举的各个阶段都具有独立性.投票者在任意阶段弃权,体现在各公告信息表中的投票者数目不相等,并不会影响选举的正常进行,因此投票者可以在任意阶段中途弃权.
(5)高效性
环签名的大计算量成为制约其应用于大规模电子投票的主要因素. 与现有方案不同的是,本文将计算量大的关联环签名应用于注册阶段实现合法投票者的匿名注册,并通过为合法投票者发放一个唯一的临时身份标识Ni,结合其自己产生的单签名公私钥(eVi,dVi),用于后续投票和计票阶段的匿名身份认证. 由于本文方案的投票阶段仅使用(eVi,dVi)实现普通的个体签名及验证,故有效保证了投票阶段的高效性和实用性,适合于大规模选举.
下面将本文方案和文献[2,9,13-14]中方案的投票效率进行对比,表1 给出相关符号的定义.
表1 相关符号定义Tab.1 Symbol definitions
根据文献[21],tE≈8.24tECM,tE≈240tM,tE≈600tH,tE≈3.2tECP,tECA≈5tM,可以推出:tE≈240tM,tECM≈29.13tM,tECP≈75tM,tECA≈5tM,tH≈0.4tM. 对比各方案投票效率如表2 所示.
表2 各方案投票效率比较Tab.2 Comparison of voting efficiency of various schemes
从表2 可以看出,文献[2]和本文方案的投票效率高,本文方案投票时间复杂度仅为961 个模乘运算,较文献[9,13-14]的方案效率至少提高42.9%;其次是文献[9]方案,且这3 个方案的投票效率均与投票者规模n 无关,适合大规模选举.而文献[13-14]方案的投票协议复杂度随n 的增加而增大.由于在大规模选举中,n 的值一般较大,因此文献[13-14]方案的投票效率低,不适合于大规模选举.
4.3 性能比较
将本文方案与现有的几种电子投票方案进行了性能比较,如表3 所示.
表3 各投票方案综合性能比较Tab.3 Performance comparison of the voting schemes
从表中可以看出,文献[2]方案虽然能满足各方面的安全要求,且投票效率高,但其安全性依赖于对注册机构的绝对可信.文献[9]方案同样存在可信第三方安全隐患,并且方案需要借助匿名通信信道.文献[13]方案没有实现协议的秘密性和公平性,同时投票效率过低,不适合于大规模选举.文献[14]方案也需要依赖可信机构,而且不诚实的投票者可以冒充其他投票者投票,破坏了投票协议的不可重用性和稳定性,另外方案投票效率较低,无法满足大群体选举.本文方案不存在第三方安全隐患,无需借助于匿名通信信道,也不存在选票碰撞问题,投票者可在任意阶段中途弃权而不影响选举的进行,能满足协议的安全性要求,而且投票过程效率高,适合于大规模选举.
5 结 论
本文针对电子投票过程中存在安全隐患和投票效率低等缺陷,利用关联环签名结合盲签名技术,提出了一个新的安全电子投票方案. 该方案无需依赖任何可信第三方和匿名通信信道,且因引入身份序列码和信息公开验证机制,具备抗选票碰撞性以及投票者可以在任意阶段弃权的功能.关联环签名具有保证投票者身份匿名性和不可重用性的优势,但却存在计算量大的缺点,而本文将其运用于注册环节,在后续的投票和计票阶段则利用基于序列码的个体签名进行身份验证,克服了关联环签名用于电子投票系统导致投票效率低的固有难题,提高了投票协议的效率和实用性,适合于大规模选举.
[1] PENG K,BOYD C,DAWSON E,et al. A correct,private,and efficient mix network[C]∥The 7th International Workshop on Theory and Practice in Public Key Cryptography 2004,LNCS 2947. Berlin:Springer-Verlag,2004:439-454.
[2] 高虎明,王继林,王育民. 一个基于Mix net 的电子投票方案[J]. 电子学报,2004,32(3):1047-1049.GAO Huming, WANG Jilin, WANG Yumin. An electronic voting scheme based on Mix net[J]. Chinese Journal of Electronics,2004,32(3):1047-1049.
[3] CICHON J, KLONWSKI M, KUTYLOWSKI M.Distributed verification of mixing-local forking proofs model[C]∥The 13th Australasian Conference of Information Security and Privacy 2008,LNCS 5107.Berlin:Springer-Verlag,2008:128-140.
[4] PENG K. A general and efficient countermeasure to relation attacks in mix-based e-voting[J]. International Journal of Information Security,2011,10(1):49-60.
[5] PANG L,SUN M H,LUO S S,et al. Full privacy preserving electronic voting scheme[J]. The Journal of China Universities of Posts and Telecommunications,2012,19(4):86-93.
[6] HAENNI R,KOENIG R E. A generic approach to prevent board flooding attacks in coercion-resistant electronic voting schemes[J]. Computers & Security,2013,33(2):59-69.
[7] FUJIOKA A,OKAMOTO T,OHTA K. A practical secret voting scheme for large scale elections[C]∥Advances in Cryptology-AUSCRYPT 1992,LNCS 718.Berlin:Springer-Verlag,1993:244-251.
[8] KU W,WANG S. A secure and practical electronic voting scheme[J]. Computer Communication,1999,22(3):279-286.
[9] 陈晓峰,王育民. 基于匿名通讯信道的安全电子投票方案[J]. 电子学报,2003,31(3):390-393.CHEN Xiaofeng,WANG Yumin. A secure electronic voting scheme based on anonymous communication channel[J]. Chinese Journal of Electronics,2003,31(3):390-393.
[10] CHEN Xiaofeng,WU Qianhong,ZHANG Fangguo,et al. New receipt-free voting scheme using doubletrapdoor commitment[J]. Information Sciences,2011,181(8):1493-1502.
[11] GHAVAMIPOOR H, SHAHPASAND M. An anonymous and efficient e-voting scheme[C]∥The 7th International Conference on E-Commerce in Developing Countries:With Focus on E-Security (ECDC).[S.l.]:IEEE,2013:1-13.
[12] LIU J K, WEI V K, WONG D S. Linkable spontaneous anonymous group signature for ad hoc groups[C]∥The 9th Australasian Conference on Information Security Privacy 2004, LNCS 3108.Berlin:Springer-Verlag,2004:325-335.
[13] TSANG P P,WEI V K. Short linkable ring signatures for E-voting,E-cash and attestation[C]∥The 1st Information Security Practice and Experience Conference 2005, LNCS 3439. Berlin: Springer-Verlag,2005:48-60.
[14] 范安东,孙琦,张扬松. 基于环签名的匿名电子投票方案[J]. 四川大学学报:工程科学版,2008,40(1):113-117.FAN Andong, SUN Qi, ZHANG Yangsong. A anonymous electronic voting scheme based on ring signature[J]. Journal of Sichuan University:Engineering Science Edition,2008,40(1):113-117.
[15] RIVEST R,SHAMIR A,TAUMAN Y. How to leak a secret[C]∥Advances in Cryptology-Asiacrypt 2001,LNCS 2248. Berlin:Springer-Verlag,2001:552-565.
[16] DOWSLEY R,HANAOKA G,IMAI H. Roundoptimal deniable ring authentication in the presence of big brother[C]∥Information Security Applications,LNCS 6513. Berlin:Springer-Verlag,2011:307-321.
[17] XIONG H,CHEN Z,LI F G. Bidder-anonymous English auction protocol based on revocable ring signature[J]. Expert Systems with Applications,2012,39(8):7062-7066.
[18] YUEN T H,LIU J K,AU M H. Efficient linkable and/or threshold ring signature without random oracles[J]. Computer Journal,2013,56(4):407-421.
[19] DENG L Z,ZENG J W. Two new identity-based threshold ring signature schemes[J]. Theoretical Computer Science,2014,535(4):38-45.
[20] YEON H J,CHANG K Y,SOOK C H,et al.Collusion-resistant convertible ring signature schemes[J]. Science China Information Sciences,2015,58(1):1-16.
[21] JUANG W S. Ro-cash:an efficient and practical recoverable pre-paid offline e-cash scheme using bilinear pairings[J]. Journal of Systems and Soft,2010,83(1):638-645.