基于同態實現多候選人的電子投票方案

黃仕杰 洪 璇

(上海師范大學信息與機電工程學院 上海 200234)

基于同態實現多候選人的電子投票方案

黃仕杰 洪 璇

(上海師范大學信息與機電工程學院 上海 200234)

選舉是當今公民實現民主的重要方式，相比于傳統選舉方式，電子選舉以密碼學為基礎，可以有效避免在各個環節中出現徇私舞弊現象，并且在計票階段也比傳統選舉方式更快、更準確。在滿足電子選舉的公正性、唯一性、匿名性等八個基本特性的基礎上，該方案通過使用Paillier加密的加法同態性來避免在計票環節對選民選票進行舞弊操作，同時能夠大幅度提高電子選舉在最后計票環節的效率。

電子選舉 同態加密 Paillier公鑰密碼體制 RSA公鑰密碼體制 加法同態性

0 引 言

傳統選舉在其發展過程中，發現其并不能實現選舉的公正性，而且在實行傳統選舉過程中，因為人為失誤的因素，會導致選舉結果最后的不可信，甚至導致選舉失敗[6]。在2000年美國大選中，曾因紙質選票的樣式設計誤導了選民，導致總統候選人對最后的選票結果產生爭執，最后由最高聯邦法院裁決選出美國總統。

Chaum[1]在1981年提出了一個基于公鑰密碼體制的無法追蹤的電子郵件方案，這是電子投票的雛形。1993年Fujioka等提出了比較完善的盲簽名方案。目前電子選舉方案主要使用的技術有：基于盲簽名的電子選舉[5]、基于秘密共享的電子選舉、基于混合網絡的電子選舉以及基于同態加密的電子選舉，共四種方案。

本文提出了一個基于同態加密密碼體制提出的電子選舉方案，使用同態加密保證選票的保密性和不可追蹤性[2]，最后對選票結果的密文進行恢復，得出選舉結果。該選舉方案中主要參與者有：認證中心、計票中心、投票人、候選人以及負責驗證選票正確性的可信第三方。

1 同態加密技術

1.1 同態加密體制

同態加密技術是由Rivest等在1978年首次提出[3]。同態加密的提出，使得人們可以對密文直接進行計算，并且計算后的結果解密后得出的明文與對應明文進行同樣的計算后得出的結果一樣[10]。設R、S是兩個環，R表示明文空間，S表示密文空間，定義算法E: R→S。

(1) 加法同態

滿足從E(x)和E(y)可以通過加法計算E(x)+E(y)計算出E(x+y)，同時不需要知道x、y的值。

(2) 乘法同態

滿足從E(x)和E(y)可以通過乘法計算E(x)E(y)計算出E(xy)，同時不需要知道x、y的值。

(3) 混合乘法同態

滿足從E(x)和y可以通過乘法計算yE(x)計算出E(xy)的值，同時不需要知道x、y的值。

1.2 同態加密在電子選舉中的應用

Cramer等在1997年，第一次提出了基于ELGamal密碼體制的加法同態性的電子投票方案，利用ELGamal的加法同態性將選票的密文累乘后，再通過私鑰將最后的投票結果解密出來，進一步節省了計票環節的時間。目前仍然沒有有效的全同態加密算法，不過存在有成熟且具有單一同態性質的密碼算法(RSA、ElGamal、Paillier)能夠滿足部分安全多方計算場景中的應用[8]。在文獻[11]中，提及雖然Paillier公鑰密碼體制自身加解密效率過低，但是Paillier的同態性在密文操作上所消耗的時間相對較少，十分符合電子投票在計票環節利用同態加密的同態性進行選票累加的需求。所以本文選取基于大整數因子分解的Paillier加密作為主要加密算法。

2 加密算法介紹

2.1Paillier公鑰密碼體制基礎知識

Paillier[3]公鑰密碼體制是一種具有語義安全性、加法同態性以及混合乘法同態性的公鑰密碼體制，它的安全性主要是依賴于大整數因子分解的困難性[4]。

2.2Paillier公鑰密碼體制加解密過程

(1) 參數初始化

(2) 加密過程

對于明文m(m∈Z_n)，對應的密文c為：

c=Encrypt(g,n,m)=gm×rnmodn2

(3) 解密過程

對于密文c，對應的明文為：

m=Decrypt(λ,μ,c)=L(cλmodn2)×μmodn

2.3Paillier算法的同態性

根據上一小節的條件，對明文m1和m2進行加密后，得到對應密文：

c1=gm1×rnmodn2和c2=gm2×rnmodn2。

此時：c1×c2=gm1+m2×r2nmodn2=Encrypt(g,n,m1+m2)，所以paillier算法具有加法同態性[9]。

3 基于同態加密的電子投票方案

3.1 方案概述

在本電子投票方案中，依據paillier密碼體制對選票內容進行加密。對加密后的密文取其hash值，用RSA加密體制進行簽名。由于paillier密碼體制具有加法同態性和混合乘法同態性，所以對密文的任何操作，都等效于對明文做同樣的操作。

本方案中，主要參與者有：

(1) 認證中心(CertificateAuthority，縮寫CA)

生成該方案中的paillier的公私鑰和RSA的公私鑰，并將對應的公鑰廣播出去。負責對投票人的身份進行驗證，并且存儲在數據庫中，確保其真實可靠，避免不誠信的投票人多次投票，在合法投票人注冊成功后，向其提供空白選票。選舉結束后，將投票結果解密出來。如果最后發生糾紛，可以將有爭議的選票恢復成明文。

(2) 計票中心(Count)

對來自投票人的選票進行驗證，判斷選票的有效性，并且通過paillier密碼體制的加法同態性進行選票的數量累加。

(3) 投票人(Vote，縮寫V)

投票人(Vote，縮寫V)：投票人，包括合法和非法的投票人，投票人用V1,V2,V3,…,Vk表示。

(4) 候選人(Candidate，縮寫C)

一場選舉中，有多個候選人，對應的候選人用Ce1,Ce2,Ce3,…,Cej表示。

(5) 可信第三方

負責檢查選票的正確性。

3.2 方案流程

(1) 方案初始化階段

構造秘鑰：

由認證中心(CA)生成該方案的paillier加密的公鑰(g,n)，私鑰(λ,μ)；生成該方案的RSA加密公鑰(n′,e),私鑰d。

構造的選票形式：

假設認證中心計算能力足夠大，則有j位候選人，投票人的人數小于10k，為方便最后統計選票結果，構造投票人Vi(i∈(1,2,…,k))的選票形式如下：

設投票號為IDvi，是一串隨機生成的唯一身份標識符。設投給候選人Cm的選票內容為：(0,0,…,bm) ，其中bm∈(0,1)，m∈(1,2,…,j)并且bm(m∈(1,2,…,j))中有且只能有一個值為1。那么，構造通用選票如圖1所示。

圖1 通用選票形式

例如投給第一位候選人的選票形式如圖2所示。

圖2 投給第二位候選人的選票

那么可以得出針對j位候選人的電子投票，共有j種選票形式，分別記為(ce1,ce2,…,cej)，在計票階段只要通過對這j種選票形式進行篩選，則可以判斷選票的唯一性，是否選票只投了一位候選人。同時由認證中心對選票內容進行Paillier加密，在每次進行Paillier加密時，選取不同的隨機數rm進行加密。其中rm∈(r1,r2,…,rj),0≤rm≤n，并且隨機數rm兩兩之間互質，得到密文結果(Encrypt(ce1),Encrypt(ce2),…,Encrypt(cej)，其中：

投票人注冊階段：

投票人Vi向認證中心CA提交個人身份資料。

認證中心CA驗證投票人Vi身份信息合法，若投票人身份合法且確實是第一次投票，則向投票人Vi發放一個投票號(IDVi)，對該投票號(IDVi)進行paillier加密，獲得密文c1，即為空白選票：

c1=Encrypt(g,n,IDV)=gIDV×rnmodn2

對加密結果c1，使用注冊機構的私鑰進行RSA簽名：

對加密結果c1，取其哈希值：HASH(c1)；

將投票人身份、投票號(IDV)、空白選票c1、選票的簽名SIGRA(c1)以及其哈希值HASH(c1)收錄到數據庫中，防止投票人多次投票，并且將(c1,SIGCA(c1),HSAH(c1))作為票據交給投票人V。

(2) 生成選票階段

投票人獲得來自認證中心CA的票據(c1,SIGCA(c1),HSAH(c1))后，先對空白選票c1進行哈希值驗證，確保選票的完整性。

驗證選票的合法性：

Verify()(f,e)(c1,SIGCA(c1))=True

其中，c1≡GISCA(c1)e(modn′)。

若選票合法，保留其身份信息和票據(c1,SIGCA(c1),HSAH(c1))，在以后的糾紛中證明自己的合法身份。

之后投票人將根據自己的選擇，選擇候選人Cm(m∈{C1,C2,C3,…,Cj})，將所選的候選人Cm的選票cm進行paillier加密，其中選取特殊的隨機數rV，rV與集合(r1,r2,…,rj)中的隨機數都互質，并且0≤rV≤n：

投票人將完整選票(SIGCA(c1),c1,c2)交給計票機構，并且自己保留一份以防止以后發生投票內容與公示內容不一致糾紛。

(3) 計票階段

計票初始時，計票機構使用paillier的公鑰初始化，投票箱MBallot：

cBallot=Encrypt(g,n,0)=gMBallot×rnmodn2

=g0×rnmodn2

在選票進行計票之前，引入可信第三方，對來自選民的選票進行檢查，驗證其身份的唯一性，以及投票內容的唯一性。

假設可信第三方也持有此次電子投票Paillier加密的密鑰(λ,μ)，以及對選票內容進行Paillier加密的隨機數集合(r1,r2,…,rj)。可信第三方獲得來自投票人的選票，取其中的SIGCA(c1)與數據庫中的對比，判斷選票的合法性以及身份的唯一性。若判斷通過，則構造匹配值：Matchm=(rm/rV)nmodn2，得到匹配值集合(Match1,Match2,…,Matchj)。

計算c2與(Encrypt(ce1),Encrypt(ce2),…,Encrypt(cej))中的商得到集合(q1,q2,…,qj)，比較集合(q1,q2,…,qj)與集合(Match1,Match2,…,Matchj)，如果有且僅有一對值相等，則說明該選票只投了一位候選人，將這張選票交給計票中心。

若選票通過步驟(2)的檢查，則將c2累加入投票箱cBallot中：

cBallot=cBallot×c2

(4) 投票結果公示階段

認證中心CA使用paillier密碼體制的私鑰對投票結果進行解密：

MBallot=Decrypt(λ,μ,cBallot)

并且對最后投票結果MBallot以及各張選票進行公示。

4 方案安全性分析與效率分析

4.1 方案安全性分析

(1) 合法性

合法投票人才有權參加選舉活動，在認證中心會對所有的投票人進行身份認證排除不具備投票權利的投票人。

(2) 匿名性

在構造選票的過程中，使用的是paillier公鑰密碼體制對選票進行加密，除了投票人本身，其他任何人都無法根據選票追蹤調查到相應的選民身份，無法將選票和選民一一對應。

(3) 公正性

任何人及任何事情都不應該影響到投票的最終結果，投票的中間過程更不能被泄露；每位合法的選民，都可以獲得自己的唯一選票號，公平公正地行使自己選舉權。

(4) 唯一性

合法選民有且只有一次投票機會。通過保留選票內容以及唯一選票號IDvi，避免不誠信的投票人多次投票。

(5) 可驗證性

在最后的選舉結束之后，可以通過恢復選票，使得每位投票人都能夠比較容易驗證自己的選票有沒有篡改或舍棄。

(6) 正當性

(7) 完整性

所有合法的投票都可以通過paillier公鑰密碼體制的加法同態性累計，被計入最后的選票結果中。

(8) 無爭議性

基于RSA的公鑰簽名方案和基于paillier同態加密方案被證明是安全的。所以基于paillier加密的電子投票方案的算法以及其參數、公鑰等可以完全公開，投票人通過自己保留完整選票(SIGCA(c1),c1,c2)，在電子投票結束后，都可以通過將選票解密來驗證選票的正確性。

4.2 方案效率分析

目前同類使用paillier加密算法構造的電子選舉方案較少，所以選擇與基于ElGamal加密算法同態性的電子選舉方案作比較[12]。在文獻[12]中提出一種基于ElGamal加密算法同態性來保護選民身份信息不被暴露，同時保證選民選票在計算過程中的正確性以及安全性。但是該方案使用ElGamal算法進行選票的加密，由于加密算法的特性，對每張選票進行加密都會相應獲得兩段密文。設ElGamal加密算法的公鑰為(p,g,y)，私鑰為x，則對選票M進行加密，獲得密文密文：C1,C2:C1=gkmodp,C2=K×Mmodp。在整個加密過程中需要進行兩次冪運算，增大了計算復雜度，以及因為獲得比明文長度長兩倍的密文，也增大了存儲空間的使用。相比之下，本方案在加密過程中只需要進行一次冪運算。同時文獻[12]對選民提供的選票沒有進行唯一性認證，無法防范不誠信的合法投票人構造非法選票，構造的選票格式與文獻[12]所定義的不一致影響選舉的正確進行。本方案在保留使用加密算法的同態性來累計選舉結果的基礎上，選擇使用paillier加密算法來簡化冪運算，同時構造匹配值集合(Match1,Match2,…,Matchj)來保證選民提交的選票的合法性，是符合規范的。

5 結 語

本文在paillier公鑰密碼體制的基礎上，提出了一種電子投票的方案。本方案使用paillier加密的同態性，構造特殊的選票以實現在對選票不解密的情況下，能對選票實現匯總，最后在投票結束后，將選票結果恢復出來。本方案還需進一步完善，降低運算規模，能適合更大規模的選舉。

[1]ChaumDL.Untraceableelectronicmail,returnaddresses,anddigitalpseudonyms[J].CommunicationsoftheACM,1981,24(2):84-90.

[2] 祁明,肖國鎮.一個適合大規模電子選舉的秘密投票方案[J].電子與信息學報,1997,19(5):717-720.

[3]RivestRL,AdlemanL,DertouzosML.Ondatabanksandprivacyhomomorphisms[M]//FoundationsofSecureComputation,1978:169-179.

[4]PaillierP.Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses[C]//ProceedingsofInternationalConferenceontheTheoryandApplicationofCryptographicTechniques.Springer,1999:223-238.

[5] 謝金寶,劉暉波.基于盲、群簽名和秘密共享的新型電子安全選舉模型[J].微型機與應用,2000,19(9):38-42.

[6] 馮澤濤,張勇.一個有效的電子選舉方案[J].計算機與信息技術,2007(5):24-26,29.

[7] 宋春來,殷新春,孟純煜.一種安全實用的大規模選舉協議[J].計算機應用與軟件,2008,25(8):40-41,47.

[8]BonehD,GentryC.Afullyhomomorphicencryptionseheme[D].PaloAlto,CA,USA:StanfordUniversity,2009.

[9]NishideT,SakuraiK.Distributedpailliercryptosystemwithouttrusteddealer[C]//Proceedingsofthe11thInternationalConferenceonInformationSecurityApplications.Springer,2010:44-60.

[10] 袁春明.基于Paillier公鑰密碼體制的零知識證明方案[J].計算機與現代化,2011(4):45-46,49.

[11] 白健,楊亞濤,李子臣.Paillier公鑰密碼體制同態特性及效率分析[J].北京電子科技學院學報,2012,20(4):1-5.

[12] 李蓓.基于同態加密策略的電子選舉系統[J].計算機應用,2015,35(S1):66-68,88.

AN ELECTRONIC VOTING SCHEME REALIZING MULTI CANDIDATESBASED ON HOMOMORPHISM

Huang Shijie Hong Xuan

(CollegeofInformation,MechanicalandElectricalEngineering,ShanghaiNormalUniversity,Shanghai200234,China)

Election is an important way to achieve democratic citizenship in modern society. Compared with the traditional approach, electronic voting election can effectively avoid the phenomenon of favoritism in each section based on cryptography, and it is much faster and more accurate in vote counting. On the basis of satisfying the eight properties of fairness, uniqueness, anonymity and so on, the proposed scheme applied the addition homomorphism encrypted by Paillier in order to avoid the fraud operation on electors votes in vote counting. Meanwhile, it is able to greatly enhance the efficiency of electronic voting in the last vote counting section.

Electronic vote Homomorphic encryption Paillier public key cryptography RSA public key cryptography Addition homomorphism

2015-12-09。上海市自然科學

14ZR1431000)。黃仕杰，碩士生，主研領域：信息安全。洪璇，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.03.051