黃仕杰 洪 璇

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

基于同態(tài)實(shí)現(xiàn)多候選人的電子投票方案

黃仕杰 洪 璇

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

選舉是當(dāng)今公民實(shí)現(xiàn)民主的重要方式，相比于傳統(tǒng)選舉方式，電子選舉以密碼學(xué)為基礎(chǔ)，可以有效避免在各個(gè)環(huán)節(jié)中出現(xiàn)徇私舞弊現(xiàn)象，并且在計(jì)票階段也比傳統(tǒng)選舉方式更快、更準(zhǔn)確。在滿足電子選舉的公正性、唯一性、匿名性等八個(gè)基本特性的基礎(chǔ)上，該方案通過使用Paillier加密的加法同態(tài)性來避免在計(jì)票環(huán)節(jié)對(duì)選民選票進(jìn)行舞弊操作，同時(shí)能夠大幅度提高電子選舉在最后計(jì)票環(huán)節(jié)的效率。

電子選舉 同態(tài)加密 Paillier公鑰密碼體制 RSA公鑰密碼體制 加法同態(tài)性

0 引 言

傳統(tǒng)選舉在其發(fā)展過程中，發(fā)現(xiàn)其并不能實(shí)現(xiàn)選舉的公正性，而且在實(shí)行傳統(tǒng)選舉過程中，因?yàn)槿藶槭д`的因素，會(huì)導(dǎo)致選舉結(jié)果最后的不可信，甚至導(dǎo)致選舉失敗[6]。在2000年美國大選中，曾因紙質(zhì)選票的樣式設(shè)計(jì)誤導(dǎo)了選民，導(dǎo)致總統(tǒng)候選人對(duì)最后的選票結(jié)果產(chǎn)生爭(zhēng)執(zhí)，最后由最高聯(lián)邦法院裁決選出美國總統(tǒng)。

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

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

1 同態(tài)加密技術(shù)

1.1 同態(tài)加密體制

同態(tài)加密技術(shù)是由Rivest等在1978年首次提出[3]。同態(tài)加密的提出，使得人們可以對(duì)密文直接進(jìn)行計(jì)算，并且計(jì)算后的結(jié)果解密后得出的明文與對(duì)應(yīng)明文進(jìn)行同樣的計(jì)算后得出的結(jié)果一樣[10]。設(shè)R、S是兩個(gè)環(huán)，R表示明文空間，S表示密文空間，定義算法E: R→S。

(1) 加法同態(tài)

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

(2) 乘法同態(tài)

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

(3) 混合乘法同態(tài)

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

1.2 同態(tài)加密在電子選舉中的應(yīng)用

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

2 加密算法介紹

2.1Paillier公鑰密碼體制基礎(chǔ)知識(shí)

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

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

(1) 參數(shù)初始化

(2) 加密過程

對(duì)于明文m(m∈Z_n)，對(duì)應(yīng)的密文c為：

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

(3) 解密過程

對(duì)于密文c，對(duì)應(yīng)的明文為：

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

2.3Paillier算法的同態(tài)性

根據(jù)上一小節(jié)的條件，對(duì)明文m1和m2進(jìn)行加密后，得到對(duì)應(yīng)密文：

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

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

3 基于同態(tài)加密的電子投票方案

3.1 方案概述

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

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

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

生成該方案中的paillier的公私鑰和RSA的公私鑰，并將對(duì)應(yīng)的公鑰廣播出去。負(fù)責(zé)對(duì)投票人的身份進(jìn)行驗(yàn)證，并且存儲(chǔ)在數(shù)據(jù)庫中，確保其真實(shí)可靠，避免不誠信的投票人多次投票，在合法投票人注冊(cè)成功后，向其提供空白選票。選舉結(jié)束后，將投票結(jié)果解密出來。如果最后發(fā)生糾紛，可以將有爭(zhēng)議的選票恢復(fù)成明文。

(2) 計(jì)票中心(Count)

對(duì)來自投票人的選票進(jìn)行驗(yàn)證，判斷選票的有效性，并且通過paillier密碼體制的加法同態(tài)性進(jìn)行選票的數(shù)量累加。

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

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

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

一場(chǎng)選舉中，有多個(gè)候選人，對(duì)應(yīng)的候選人用Ce1,Ce2,Ce3,…,Cej表示。

(5) 可信第三方

負(fù)責(zé)檢查選票的正確性。

3.2 方案流程

(1) 方案初始化階段

構(gòu)造秘鑰：

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

構(gòu)造的選票形式：

假設(shè)認(rèn)證中心計(jì)算能力足夠大，則有j位候選人，投票人的人數(shù)小于10k，為方便最后統(tǒng)計(jì)選票結(jié)果，構(gòu)造投票人Vi(i∈(1,2,…,k))的選票形式如下：

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

圖1 通用選票形式

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

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

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

投票人注冊(cè)階段：

投票人Vi向認(rèn)證中心CA提交個(gè)人身份資料。

認(rèn)證中心CA驗(yàn)證投票人Vi身份信息合法，若投票人身份合法且確實(shí)是第一次投票，則向投票人Vi發(fā)放一個(gè)投票號(hào)(IDVi)，對(duì)該投票號(hào)(IDVi)進(jìn)行paillier加密，獲得密文c1，即為空白選票：

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

對(duì)加密結(jié)果c1，使用注冊(cè)機(jī)構(gòu)的私鑰進(jìn)行RSA簽名：

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

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

(2) 生成選票階段

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

驗(yàn)證選票的合法性：

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

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

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

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

投票人將完整選票(SIGCA(c1),c1,c2)交給計(jì)票機(jī)構(gòu)，并且自己保留一份以防止以后發(fā)生投票內(nèi)容與公示內(nèi)容不一致糾紛。

(3) 計(jì)票階段

計(jì)票初始時(shí)，計(jì)票機(jī)構(gòu)使用paillier的公鑰初始化，投票箱MBallot：

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

=g0×rnmodn2

在選票進(jìn)行計(jì)票之前，引入可信第三方，對(duì)來自選民的選票進(jìn)行檢查，驗(yàn)證其身份的唯一性，以及投票內(nèi)容的唯一性。

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

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

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

cBallot=cBallot×c2

(4) 投票結(jié)果公示階段

認(rèn)證中心CA使用paillier密碼體制的私鑰對(duì)投票結(jié)果進(jìn)行解密：

MBallot=Decrypt(λ,μ,cBallot)

并且對(duì)最后投票結(jié)果MBallot以及各張選票進(jìn)行公示。

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

4.1 方案安全性分析

(1) 合法性

合法投票人才有權(quán)參加選舉活動(dòng)，在認(rèn)證中心會(huì)對(duì)所有的投票人進(jìn)行身份認(rèn)證排除不具備投票權(quán)利的投票人。

(2) 匿名性

在構(gòu)造選票的過程中，使用的是paillier公鑰密碼體制對(duì)選票進(jìn)行加密，除了投票人本身，其他任何人都無法根據(jù)選票追蹤調(diào)查到相應(yīng)的選民身份，無法將選票和選民一一對(duì)應(yīng)。

(3) 公正性

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

(4) 唯一性

合法選民有且只有一次投票機(jī)會(huì)。通過保留選票內(nèi)容以及唯一選票號(hào)IDvi，避免不誠信的投票人多次投票。

(5) 可驗(yàn)證性

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

(6) 正當(dāng)性

(7) 完整性

所有合法的投票都可以通過paillier公鑰密碼體制的加法同態(tài)性累計(jì)，被計(jì)入最后的選票結(jié)果中。

(8) 無爭(zhēng)議性

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

4.2 方案效率分析

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

5 結(jié) 語

本文在paillier公鑰密碼體制的基礎(chǔ)上，提出了一種電子投票的方案。本方案使用paillier加密的同態(tài)性，構(gòu)造特殊的選票以實(shí)現(xiàn)在對(duì)選票不解密的情況下，能對(duì)選票實(shí)現(xiàn)匯總，最后在投票結(jié)束后，將選票結(jié)果恢復(fù)出來。本方案還需進(jìn)一步完善，降低運(yùn)算規(guī)模，能適合更大規(guī)模的選舉。

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

[2] 祁明,肖國鎮(zhèn).一個(gè)適合大規(guī)模電子選舉的秘密投票方案[J].電子與信息學(xué)報(bào),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].微型機(jī)與應(yīng)用,2000,19(9):38-42.

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

[7] 宋春來,殷新春,孟純煜.一種安全實(shí)用的大規(guī)模選舉協(xié)議[J].計(jì)算機(jī)應(yīng)用與軟件,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公鑰密碼體制的零知識(shí)證明方案[J].計(jì)算機(jī)與現(xiàn)代化,2011(4):45-46,49.

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

[12] 李蓓.基于同態(tài)加密策略的電子選舉系統(tǒng)[J].計(jì)算機(jī)應(yīng)用,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。上海市自然科學(xué)

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

TP3

A

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