电子投票系统中mix-net安全性改进*1

李程慧，　陈　伟，　马　瑞

（1.浙江师范大学行知学院，浙江金华　321004；2.浙江师范大学数理与信息工程学院，浙江金华321004）

电子投票系统中mix-net安全性改进*1

李程慧1，陈伟2，马瑞1

（1.浙江师范大学行知学院，浙江金华321004；2.浙江师范大学数理与信息工程学院，浙江金华321004）

现有基于mix-net的电子投票系统在选票提交阶段存在选票提交重复、混合阶段存在欺骗的混合服务器、计数阶段存在无效的选票计数等问题.为此，从匿名性和抗重复性2个方面对mix-net的安全性进行改进.匿名性方面，提出了无序mix-net和置换矩阵.抗重复性方面，在HTDH2密码系统的基础上，增加过滤阶段，删除攻击者克隆的选票；增加删除重复的选票阶段，删除欺骗的混合服务器克隆的选票.新方案能够删除mix-net输入端重复的选票、检测出混合服务器“克隆”的选票及攻击者修改的选票.与现有方案相比，该方案具有选票提交独立和有效计数的优势.

密码学；电子投票系统；mix-net；匿名性；选票独立；HTDH2

0　引言

Mix-net是电子投票系统的重要组成部分，通过对选票进行重加密和置换，删除输出密文与输入密文之间的对应关系，从而实现匿名性.

在mix-net匿名性改进方面，文献［1］提出了optimistic mix-net方案，该方案引入乘积校验，并且对明文进行2次加密.然而，这个mix-net方案有2个缺陷：其一，选民仅仅对外层密文所用的随机数提供零知识证明，容易导致攻击者通过构造密文这一方来识别选票［2］；其二，每个混合服务器的置换在每次会话中都是相同的，容易造成攻击置换的攻击［3］.文献［4］提出了RPC方案（随机部分校验），该方案的特点是每个混合服务器是一组的，验证时每个混合服务器揭示部分输入与输出关系.它是以正确性和隐私性为代价来提高效率.正如Khazaei等［5］指出：它没有检查打开的承诺是否与置换一致，也没有强调在执行混合之前要删除非独立的选票.2010年，西班牙Scytl公司结合RPC与optimistic mix-net 2种方案的优点提出Scytl方案［6］，该方案最大的亮点就是提出了分组验证的思想.但是，如果恶意混合服务器仅仅改变2张选票的密文且没有改变它们的乘积，同时验证阶段这2张选票恰好分在同一组，那么就能顺利通过验证.这种不易被察觉的攻击方式目前仍然没有有效的解决方法.

对mix-net抗重复性的研究一直没有明显的进展.现有对付“relation attack”［7］的方式也仅仅采用计算复杂的零知识证明.文献［8］指出，抗重复攻击实际上是难以检测和预防的，该文献提出在混合后用零知识证明检测废票，用明文等价测试（PET）检测克隆体，但计算非常繁琐.文献［9］提出了TDH2密码系统，并且证明了其在随机预言模型下是CCA安全的.文献［10］在TDH2密码系统的基础上提出了HTDH2密码系统，使得密文具有不可延展性.

基于以上分析，如何解决mix-net的匿名性和抗重复性2大安全难题，成为急需解决的问题，本文主要从这2个方面展开研究.匿名性方面，能够防止攻击者破坏第1个混合服务器所带来的攻击；抗重复性方面，删除mix-net输入端重复的选票，检测出输出端混合服务器“克隆”的选票，实现选票独立性.

1　预备知识

1.1零知识证明

零知识证明允许证明者在不向验证者提供任何秘密信息的前提下，向验证者证明其真的掌握这些秘密信息，使验证者相信某个事实是正确的，同时又不向验证者泄露这些秘密信息.对于零知识证明系统，需要满足完备性、合法性和零知识特性3条性质［11］.

1.2增扩密码系统

定义1（增扩密码系统） 一个密码系统CS=（Gen，Enc，Dec）是一个基本密码系统CSB=（GenB，EncB，DecB）的增扩，如果存在一个增扩算法Aug∈PPT和一个剥离算法Strip∈PT（PT和PPT分别指确定性多项式时间和概率性多项式时间）满足如下关系［12］：

1）输入1n，Gen产生基本密钥（pkB，skB）=GenB（1n）和扩展密钥（pkA，skA）=AugB（pkB），输出（pk，sk）=（（pkA：pkB），（skA：skB））；

2）当输入（（skA：skB），c）时，解密算法输出

其中：Gen是密钥产生算法；Enc是加密算法；Dec是解密算法；GenB是基本密钥产生算法；EncB是基本加密算法；DecB是基本解密算法.

2　mix-net方案

本文mix-net方案以HTDH2［10］密码系统为基础，基于DDH（判定Diffie-Hellman）问题和安全提交增扩密码系统SSA来设计，在抗重复攻击和匿名性方面进行改进.本文的设计思路与文献［10］基本一致，但为了确保进入mix-net的选票相互独立，在选票提交阶段增加加密扩展密文，在过滤阶段删除攻击者“克隆”的选票；为防止攻击者破坏第1个混合服务器所带来的攻击，采用无序mix-net；为了删除混合服务器“克隆”的选票，增加删除重复选票这一操作.

2.1设计思想

本文在匿名性和抗重复性2个方面对mix-net的安全性进行改进.

1）匿名性：为了防止攻击者破坏第1个混合服务器所带来的攻击，采用无序mix-net，使得第1个混合服务器具有随机性；其次，为了防止攻击者推测每个混合服务器的置换，引入置换矩阵，并且给出每次会话中每个混合服务器的置换选取方法，该方法结合了关系揭示法［4］和密文分组法［6］，采用Fiat-Shamir技术［13］.

2）抗重复性：由于ElGamal体制具有同态性，攻击者可以重加密选民的选票，使得“克隆”的选票与合法有效的选票不具有独立性，从而在解密阶段推测出选民的真实选票.为了防止以上攻击的发生，采用SSA系统［12］，使得密文具有不可延展性.

2.2无序mix-net

定义2（无序mix-net） 一个mix-net称之为无序的，如果满足以下3个条件：

1）混合服务器的排序通过一种乱序的方法确定；

2）第1个混合服务器由最初的输入确定；

3）后一个混合服务器由前一个混合服务器的输出确定.

根据定义2，混合服务器的顺序仅仅由它的输入确定，在混合阶段之前，任何人都不知道它的顺序.

给定混合服务器M1，M2，…，Mk，每个混合服务器Mi（i=1，2，…，k）有l（l≥2）个不同的置换.如：

其中：πi，j表示第i个混合服务器的第j-1个置换；i=1，2…，k，j=1，2，…，l-1.

为了能够实现全局可验证的mix-net方案，每个混合服务器对每个置换进行承诺.例如：若对πi，j进行承诺，则第i个混合服务器随机选择一个比特串x，计算其哈希值h（x‖πi，j），并将计算结果公开.

每个混合服务器都有一个编号，从1到k.在混合阶段开始之前，每个混合服务器Mj从一个集合中随机选择Rj，并公开对Rj的承诺.每个混合服务器Mj对Rj解除承诺，并共同计算一个随机种子R，最终得到Q=h（R，L0），其中L0为最初密文列表.之所以将R作为哈希函数的一个参数，是为了避免任何人能够计算Q，换言之，Q值仅仅由混合服务器计算.笔者建立一个数组来标记未使用的混合服务器的编号，并且将Q作为公众已知的随机比特产生器的种子.将发生器产生的随机比特流切成长度为r=「log2k的一个数w，在数组中查找w mod k，如果找到，则编号为w的混合服务器作为第1个混合服务器；否则数字w被丢弃，再次对随机比特流进行切分.当第1个混合服务器确定以后，随机比特流再次被切分，获得一个长度为s=「log2l的一个数z，那么在当前的会话中第1个混合服务器使用第z个置换，即选择置换矩阵中πw，z-1.同理，第2个混合服务器及其置换由第1个混合服务器输出的密文和数Q决定.这个过程一直持续到确定出最后一个混合服务器为止.正如Fiat和Shamir指出的，没有一种方法能够从哈希函数的输入中预测出输出的结果.因此，哈希函数输出的结果对每个混合服务器都是未知的，从而保证了混合服务器的顺序是不能被预知的.

2.3具体方案

假设有n个合法选民，k个混合服务器，每个混合服务器有l个置换，第i个混合服务器Mi的第j个置换记为πi，j-1，并对其进行承诺.每个混合服务器Mj随机选取Rj∈Zp，并公开对Rj的承诺；然后，Mj对Rj解除承诺；最后，所有的混合服务器共同计算一个随机种子R.假设存在一个认证的公告板BB，记录选票信息和证据，对公众公开.

方案如下：

十九大报告着重指出:“为在新的历史条件下，夺取中国特色社会主义伟大胜利，决胜全面建成小康社会、进而全面建设社会主义现代化强国”，“必须坚持人民主体地位。”马克思创始人以唯物史观为立论基础，历史的、具体的阐述了人民主体思想核心意蕴及实现途径，为无产阶级革命和社会主义现代化建设提供了锐利的思想武器。而《法兰西内战》作为马克思人民主体思想在深入发展阶段的思想结晶，其对巴黎公社人民主体实践进行了理论总结。马克思主义作为我国的指导思想，我们有必要从理论源头上对“人民主体”思想进行梳理，为我国“人民主体”思想进行理论上的构建和实践上的开展提供可借鉴的思想资源。

选票提交阶段：

第1步：产生基本密钥.输入参数1n，GenB选择素数p，q，整数z及生成元g和g0，p=2q+1，H：G5× ｛0，1｝n→Zq，GenB的输出（pkB，skB）定义为（（p，g，g0，H，h），（p，z））.

第2步：产生扩展密钥.输入基本密码系统的公钥pkB时，增扩密码系统AugB输出（pkA，skA）=（（p，g，g0），⊥），其中⊥表示空值.

第3步：增扩算法.假设第i个选民Alice的明文为mi∈，输入（pkA，pkB）：=（（p，g，g0），（p，g，g0，H，h）），Li∈｛0，1｝n，Aug随机选择一对数（ri，si）∈，并且计算密文

第4步：加密扩展密文.输入（Li，ui，ei，u0，i，ci，fi），EncB随机选取ti∈Zq，计算密文

选票过滤阶段：

一旦选票提交阶段结束，就开始选票过滤阶段.假设初始密文列表为，T≥n（之所以提交的选票个数T不小于选民个数n，是因为可能存在攻击者“克隆”的选票）.

第7步：加密内层密文.输入L2，EncB随机选取t*l∈Zq，计算密文

选票混合阶段：

第8步：执行无序mix-net.将L3作为mix-net的输入，令其中Q=h（R，D），Q，，计算0以为种子执行随机比特产生器按照匿名性设计方法将随机比特流切成一个长度为r=「log2k的数w，确定第1个混合服务器.再次切分随机比特流确定第1个混合服务器的置换.第1个混合服务器对列表密文D0进行重加密和置换，输出，并且产生混合证据，利用零知识证明输出密文的乘积是输入密文乘积的重加密.依次类推，确定其余混合服务器.记最后一个混合服务器的输出为其中

第12步：ElGamal解密.输入CSB的私钥，执行），则输出⊥；否则输出

2.3.1方案分析

本文mix-net流程图如图1所示.

图1　mix-net流程图

方案分为4个阶段：选票提交阶段、过滤阶段、混合阶段和解密阶段（ElGamal解密）.其中过滤阶段和混合阶段中的删除重复选票是本方案的创新之处，也是在HTDH2方案基础上增加的算法.

由于攻击者在客户端和服务器端造成的威胁程度不同，所以本文在混合阶段之前增加一个过滤阶段，该阶段是针对攻击者在客户端所造成的威胁（克隆选票）而设计的执行步骤，目的是在mix-net输入源头上控制选票的合法性，起到“净化”输入的作用.之所以将第9步外层密文解密设计在混合阶段之后，目的是检测混合服务器是否存在欺骗行为.

在过滤阶段，只能删除攻击者“克隆”的选票，不能删除被修改的选票，这是因为被攻击者修改的选票在第5步外层密文解密之后，其内层密文与那些合法选票的内层密文是不相同的，在第6步不能将其删除.对于这些被攻击者修改的选票，它们不满足第12步的剥离算法的判定条件，所以不能被解密，从而也不能被计数.

倘若使用本文方案，那么所有的计数都是有效的.如果存在攻击者修改选票的行为，那么实际计数总数小于选民个数，这是因为这些修改的选票不满足第12步的判定条件，不能解密.

2.3.2方案评价

1）本方案在mix-net混合之前删除重复的选票，从而“净化”mix-net的输入.这个功能是通过第5步外层密文解密实现的.假如攻击者对提交的合法选票=（gti，（Li‖ui‖ei‖u0，i‖ci‖fi）yti）进行重加密，从而会得到新的密文=（gti+t，（Li‖ui‖ei‖u0，i‖ci‖fi）yti+t）.虽然密文发生了改变，但是明文信息Li‖ui‖ei‖u0，i‖ci‖fi仍然保持不变.在执行第5步之后，我们会发现存在2个或者多个相同的内层密文Li‖ui‖ei‖u0，i‖ci‖fi.通过执行第6步过滤选票，将攻击者克隆的选票删除，从而使得进入mix-net的选票是相互独立的.

2）本方案能够检测出混合服务器是否“克隆”了选票，并且这些选票不能被计数.文献［14］给出一种不易被发觉的攻击，第1个混合服务器不仅克隆了选票，而且还通过了验证，从而成功地实现了攻击.然而，这种攻击不会对本文所提出的mix-net造成威胁，这是因为在第10步外层密文解密之后，我们会发现它们存在相同的内层密文，并在执行第11步时删除重复的内层密文，使得克隆的选票得不到计数.

3）本方案能够检测出攻击者或者混合服务器是否修改了选票.假设混合服务器将密文c1修改为ξ·c1，将c2修改为ξ-1·c2，由于这2个密文的乘积没有发生变化，所以混合服务器能够通过验证.但是，在执行第12步时，这2个密文不满足剥离算法的条件，从而不能被正确解密.

4）本方案能够防止攻击者破坏第1个混合服务器所带来的攻击.由于本方案的第1个混合服务器是随机的，那么对于攻击者破坏第1个混合服务器所带来的攻击（文献［15］第2种和第4种攻击，以及文献［14］第1种攻击）就不能实现.

3　方案对比

一般重加密mix-net算法的时间复杂度为O（n），新方案算法的时间复杂度也为O（n）.新方案在增强安全性的同时，时间复杂度并没有增加.新方案与现有mix-net方案对比如下：

1）对比于一般的重加密mix-net（如Scytl，Optimistic），新方案具有防止第1个混合服务器遭受破坏所带来的攻击、选票独立、删除重复的选票、发现服务器“欺骗”行为和有效计数的优点.

2）对比于HTDH2方案，新方案的优势体现在过滤阶段和混合阶段.过滤阶段，新方案能够删除攻击者克隆的选票；混合阶段，新方案能够删除混合服务器克隆的选票、作废修改的选票.

4　结语

本文从mix-net的安全需求出发，在匿名性和抗重复性2个方面对mix-net进行改进，增强了现有mix-net系统的匿名性.下一步的工作将在保证mix-net安全性的基础上，进一步提高选票混合效率.

［1］Golle P，Zhong S，Boneh D，etal.Optimisticmixing for exit-polls［C］//Zheng Yuliang.Advances in Cryptology-ASIACRYPT 2002.Heidelberg：Springer，2002：451-465.

［2］Li Chenghui，Chen Wei.An improvement against the attacks based on corrupting mix-servers［J］.Journal of Network&Information Security，2013，4（4）：285-291.

［3］Li Chenghui，Chen Wei.Cryptanalysis of some publicly-verifiable mix-net［C］//International Conference on Computer，Network Security and Communication Engineering.Shenzhen：CNSCE2014 Organizing Committee，2014.

［4］Jakobsson M，Juels A，Rivest R L.Makingmix nets robust for electronic voting by randomized partial checking［C］//Dan B.Proceedings of the 11th USENIX Security Symposium.Berkeley：USENIX Association，2002：339-353.

［5］Khazaei S，Wikström D.Randomized partial checking revisited［J］.Lecture Notes in Computer Science，2013：7779：115-128.

［6］Allepuz JP.Universally verifiable efficient re-encryption Mixnet［C］//Krimmer R.Electronic Voting 2010.Castle Hofen：Council of Europe，2010：241-254.

［7］Pfitzmann B.Breakingan efficientanonymous channel［C］//MatsuiM.Advances in Cryptology—EUROCRYPT＇94.Heidelberg：Springer，1995：332-340.

［8］Essex A，Clark J，Hengartner U.Cobra：toward concurrentballotauthorization for internet voting［J］.Oxford Economic Papers，1977，29（1）：15-23.

［9］Shoup V，Gennaro R.Securing threshold cryptosystems against chosen ciphertext attack［J］.Journal of Cryptology，2002，15（2）：75-96.

［10］Bulens P，Giry D，Pereira O.Runningmixnet-based elections with Helios［C］//Shacham H.Electronic Voting Technology Workshop/Workshop on Trustworthy Elections.Berkeley：USENIX Association，2011：6.

［11］邱卫东，黄征，李祥学，等.密码协议基础［M］.北京：高等教育出版社，2009.

［12］Wikström D.Simplified submission of inputs to protocols［C］//Hutchison D.Lecture Notes in Computer Science.Heidelberg：Springer，2008：293-308.

［13］Fiat A，Shamir A.How to prove yourself：practical solutions to identification and signature problems［C］//OdlyzkoM A.Advances in Cryptology—Crypto＇86.Heidelberg：Springer，1987：186-194.

［14］Khazaei S，Terelius B，Wikström D.Cryptanalysis of a universally verifiable efficient re-encryption mixnet［C］//Halderman JA.Proceedings of the 2012 International Conference on Electronic Voting Technology/Workshop on Trustworthy Elections.Bellevue：USENIX Association，2012：7.

［15］Wikström D.Five practical attacks for"optimisticmixing for exit-polls"［C］//MatsuiM.Selected Areas in Cryptography.Heidelberg：Springer，2004：160-174.

（责任编辑陶立方）

Security im provement of them ix-net in e-voting

LIChenghui1， CHENWei2， MA Rui1
（1.Xingzhi College，Zhejiang Normal University，Jinhua 321004，China；2.College of Mathematics，Physics and Information Engineering，Zhengjiang Normal University，Jinhua 321004，China）

Since there had been flaws in the existing e-voting based on themix-net such as submitting duplicate votes in the submitting stage，having cheatingmix-servers in themixing stage，and counting invalid votes in the counting stage，to improve the security ofmix-netwould be important.Two improvements in anonymity and non independent voteswere suggested，to enhance the anonymity.The disorderd mix-net and permutation matrix were used to resist replay attacks.The HTDH2 cryptosystem proposed by Philippe Bulens et alwas introduced into vote filtering stage in order to delete possible duplicate votesmade by attackers，and to remove non independent stage in order to delete possible clone votesmade by cheatingmix-servers.The schemewould delete some duplicate votes in the input ofmix-net，check clone votesmade bymix-servers，and detectmodified votesmade by attackers.Compared to the existingmix-net schemes，the scheme had certain advantages in submitting ballots independently and counting validly.

cryptography；e-voting；mix-net；anonymity；independent vote；HTDH2

TP309.7

A

1001-5051（2016）02-0169-06

10.16218/j.issn.1001-5051.2016.02.008

*收文日期：2015-01-08；2015-09-07

李程慧（1989-），女，山东菏泽人，助理实验师.研究方向：信息安全.

陈伟.E-mail：cyberella2000@163.com