電子投票系統中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