基于同態加密的多候選人電子投票方案①

何 倩,沈 煒

(浙江理工大學 信息學院,杭州 310018)

隨著計算機和通信技術的發展,電子投票日益成為當今時代主要的投票方式,已經逐步取代過去的唱票表決、紙質投票,它以其自身高效、方便的特性而為人們所普遍接受.一般來說,安全的電子投票必須滿足以下八個特性: 合法性、匿名性、公正性、完備性、可驗證性、正當性、唯一性和無爭議性.當今的電子投票大多數都是建立在密碼學基礎上的,大致可以分為以下幾種類型: 以Lee[1]和Chaum[2]等設計出的方案為代表的混合網模型、以FOO[3]方案和Radwin[4]的方案為代表的盲簽名模型以及同態加密模型.

基于同態加密的方案又根據其選用算法的不同而出現了以下幾種方案: 基于ELGamal[5,6]和Paillier[7,8]的部分同態加密方案、基于DGHV[9]的全同態加密電子投票方案.其中ELGamal方案和Paillier方案都可以實現多候選人投票,但是都只能獲得最終的獲勝者,不能得到具體每個人的得票數,而且由于兩種算法都是單同態加密,計算電路深度淺,不能大規模應用,實用性不強;DGHV方案支持多候選人,其安全性是基于近似GCD問題,但仍未解決無法公開驗證等問題,而且該方案效率較低.

本文基于數字簽名算法和全同態加密算法提出一種電子投票方案,數字簽名算法用于保證方案各階段的公開可驗證性,全同態加密算法用于實現對加密選票的計算,以此來實現在選票內容保密的情況下計算選票的目的,實現了電子投票方案的全匿名性以及公開可驗證性.

1 預備知識

1.1 數字簽名算法

數字簽名主要是利用公鑰密碼學構造的密碼體制,通常包括兩個部分: 簽名部分和認證部分.通常使用一對密鑰中的私鑰進行簽名,公鑰進行驗簽.本文基于ECDSA(Elliptic Curve Digital Signature Algorithm,橢圓曲線數字簽名算法)來實現方案的公開可驗證性.ECDSA是基于ECC(橢圓曲線加密算法)和DSA(數字簽名算法)實現的一種數字簽名算法(圖1),其安全性是基于橢圓曲線離散對數問題的不可實現性[10].

圖1 ECDSA原理圖

1.2 全同態加密算法

全同態加密是一種可以對加密數據進行任意計算的加密技術,具體來說,就是在無需解密密鑰的情況下,對密文進行某種操作之后進行解密,解密結果等于對明文做相同操作的結果.全同態加密算法的原理圖如圖2所示.

圖2 全同態加密原理圖

2009年Gentry構造出了第一個全同態加密方案[11],隨即掀起了全同態研究的熱潮,大量的跟進工作隨即出現,其中具有代表性的全同態加密方案有: 基于整數上的DGHV方案[12]、基于RLWE的BGV方案[13]以及基于近似特征向量的GSW方案[14].

本文基于GSW方案構造計票方案.GSW方案的同態加法和同態乘法是基于矩陣上的加法和乘法.由于原始的GSW方案只能對單比特進行加密,不能很好的適用于大規模投票,為了對選票進行打包處理,在GSW方案的基礎上采用SIMD(Single-Instruction-MultiPle-Data)打包技術[15],通過該技術能夠對選票進行打包,從而實現多比特數據加密.相較于傳統的密文打包技術,該打包技術可以只對投票人的選票整體進行一次加密,保留一份私鑰,這在候選人數量較多的情況下,能夠極大地減少加密時間及節省密鑰存儲空間.

下面對相關知識進行介紹.

1.2.1 LWE問題

現代密碼學的基石是可證明安全,即密碼學體制本身的安全性可以規約到某個困難性假設上,若該困難性假設是安全的,則原密碼體制安全;反之則原密碼學體制不安全.自2005年,Oded Regev基于格構造出了LWE(Learning With Error)困難性問題[16]以來,對于LWE問題的研究一直是密碼學界的一個熱點.LWE問題分為Decision-LWE和Search-LWE兩個版本.

DLWE問題定義: 安全參數 λ ,參數n:=n(λ)∈Z,模q:=q(λ)≥2∈Z ,錯誤分布χ :=χ(λ)∈Z .DLWEn,q,χ問題是區分如下兩種分布: 第一種分布,LWE樣本(ai,bi)是從Znq×Zq中隨機取樣得到;第二種分布,樣本(ai,bi)是通過以下方式得到: 均勻采樣

1.2.2 RAO-GSW算法

RAO-GSW全同態加密算法[15]由五個算法組成,分別為: Setup、KeyGen、Encrypt、Decrypt和Evaluate.

1)Setup(λ): 安全參數λ ,格維n:=n(λ)∈Z,模q:=q(λ)≥2∈Z ,錯誤分布χ :=χ(λ)∈Z,參數? =「logq?,m:=O(n+r)logq,N:=(n+r)·? ,其中r為要加密的比特數,定義明文空間為 {0,1}r×r,密文空間為.gT=(1,2,···,2?-1),G =gT?In+r,?代表張量積.

2)KeyGen(1λ,r): 隨機均勻采樣矩陣私鑰矩陣噪聲矩陣,設設

其中,Ir為r階單位矩陣. 令S第i行為sTi. 設:

使M(i,j)∈{0,1}r×r(i,j=1,···,r)是這樣一個矩陣:位置(i,j)處為1,其余位置全為0.對于所有的i,j=1,···,r,樣本并且有如下集合:

3)Encpk(M∈{0,1}r×r),隨機均勻采樣矩陣輸出密文如下:

4)Decsk(C):

則,根據上式輸出明文矩陣

5)Evaluate算法包括兩種: 同態加法和同態乘法.

① Add: 設輸入兩個密文C1和C2,則有:

② Mult: 設輸入兩個密文C1和C2,則有:

6)方案安全性

循環安全:k是由安全參數λ 決定的密鑰空間.f是k到c的函數.一個全同態加密方案HE={KeyGen,Enc,Dec,Eval} 對于函數f是循環安全的[15].

該方案的安全性直接依賴于DLWEn,q,χ以及循環安全.在目前的技術情況下,DLWE問題以及循環安全假設都無法在有限的計算資源下被攻破,故該方案安全.

2 同態計票器

2.1 進位溢出問題

電子投票方案中的計票操作是在正整數Z+上進行的,然而,上述GSW方案的明文空間卻是{ 0,1}r×r.為了實現二進制上的加法與乘法和十進制上加法與乘法的對應,需要設計出一種合理可行的編解碼方案,這樣在最終的解密結果中可以得到每個人的具體票數.

直觀上看,直接將Z 通過進制轉換成二進制數{ 0,1}r,再將 { 0,1}r轉變成一個對角矩陣{ 0,1}r×r即可.然而,這種方式并不直接適用于本文電子投票中的計票問題.

文獻[17]中設計了一種半加器,可以解決單比特加法計票.但是對于本文打包的多比特選票,該方法并不適用.如果直接借用半加器或全加器,由于進位次數是不可知的,一旦發生進位就會溢出,則會導致解碼的失敗,不能有效處理該問題.基于此,本文借助半加器和全加器的思想設計了一種密文加法器,以解決進位溢出導致的解碼失敗問題.

2.2 同態計票器原理與設計

由于全同態加密算法可以對加密數據做任意功能的運算,運算的結果解密后相當于對明文做同樣運算的結果.因此,以下以對明文做的運算為例說明該算法,該算法同樣適用于密文計算.首先以最簡單的兩個比特的加法為例:

設a1,a2∈{0,1},記⊕ 為模二加法,?為模二乘法.令s=a1⊕a2,c=a1?a2,則sum=a1+a2=2c+s.

類似地,對于n個比特a1,a2,···,an相加,則可以通過如下方式計算:

最終可得如下結果:

圖3 多比特計票器

為了效率的提升,使用打包技術,具體來說,即將第i個選民的選票重塑為一個矩陣,該矩陣如下:

其中,下標u表明候選人數目.對于v個投票人的選票,通過如下方式統計最終選票:

其中:

其中,C(j)表示是否發生了溢出,C(j)的總個數表明溢出發生的次數.

3 全同態加密多候選人電子投票方案

3.1 方案描述

在滿足電子選舉公平性、唯一性、匿名性等八個基本特性的基礎上,本方案根據上述數字簽名算法進行身份驗證;采用上述同態加密算法,對選票進行打包,同時對加密的選票進行計算,最后通過解密得到最終投票結果.方案實體交互圖如圖4.

圖4 方案實體交互圖

3.2 系統初始化

方案中的實體: 注冊中心、投票中心、計票中心使用ECDSA簽名算法生成簽名所需的密鑰對,這些實體用自己生成的公鑰請求認證中心(CA)生成證書,認證中心(CA)根據業務準則對這些實體的身份進行認證,確認收到的公鑰確實為這些實體本身所有,認證中心用自己的私鑰對實體的公鑰施加數字簽名并生成證書,認證中心公布這些實體的數字證書,數字證書中包含這些實體的身份信息以及自己的公鑰.

其中簽名所需密鑰對的生成過程為: 設ECDSA數字簽名算法的域參數為(Fq,E,G,q,a,b,n,h),其中Fq是有限域,E是Fq上的橢圓曲線,G是E上的一個有理點,G稱為基點,G的 階為q(q為 素數),n是G在Fq中規定的序號(一個質數),a,b是橢圓曲線E的系數,h是一單向安全的哈希函數.隨機從 [ 1,n-1]中 隨機選取一個數d,計算Q=dG.其中d為私鑰,Q為公鑰.

簽名算法SIG(M):

① 選擇一個隨機數k,k∈[1,n-1];

② 計算kG=(x1,y1);

③ 計算r=x1modn,如果r=0,則跳轉到第一步;

④ 計算e=H(m);

⑤ 計算s=k-1(e+dr)modn,如果s=0,則跳轉到第一步;

⑥ 對消息m的 簽名為(r,s).

驗證算法VER(r,s):

① 檢驗r,s∈[1,n-1],若不成立,返回拒絕簽名;

② 計算e=H(m);

③ 計算u1=es-1modn,u2=rs-1modn;

④ 計算X=u1G+u2Q=(x1,y1),如果X=零點,則驗證改簽名無效;

⑤ 計算v=x1modn;

⑥ 如果v=r,則簽名有效,否則簽名無效.

各個實體的密鑰對如下:

注冊中心:pkR=QR,skR=dR

投票中心:pkV=QV,skV=dV

計票中心:pkS=QS,skS=dS

由于投票人的身份信息不需要對外公布,故投票人采用ECDSA算法生成自己的密鑰對,由自己保留,不需要到認證中心進行認證.投票人的密鑰對為:pkO=QO,skO=dO.

此外,認證中心需要根據描述的同態加密算法中的密鑰生成算法以及候選人的數量來生成投票密鑰對,投票密鑰對如下: 公鑰私鑰sk:=S,其中r為候選人的數量.認證中心需要以安全的途徑將公鑰發送給注冊中心,將私鑰發送給計票中心.

3.3 注冊階段

投票人需要使用自己的身份材料在注冊中心進行注冊,注冊中心會根據投票人遞交的身份信息驗證該投票人是否具有投票權以及是否為首次投票,一旦驗證通過,則投票中心向該投票人發放與身份信息無關的唯一身份標識IDVi、 唯一投票標識BVi、 空白選票以及投票公鑰pk,并使用自己的私鑰對IDVi||BVi進行簽名發送給投票人.

投票人對收到的簽名進行驗證,若驗證通過,確實為來自注冊中心的合法簽名,則投票人保存IDVi||BVi||SIGR(IDVi||BVi).同時注冊中心需要將IDVi||SIGR(IDVi||BVi)發送到公示中心,投票人可以到公示中心查看自己是否已經被公布為合法的投票人.

3.4 投票階段

假設投票人需要對r個候選人進行投票,則一個投票人對多位候選人的投票表示為以下形式,其中對角線存放的是對每個候選人的投票信息,贊成即為1,反對為0,即mi∈{0,1},i=1,2,···,r,則選票的形式如下:

通過以下方式實現對選票的加密:

投票人用自己的公鑰對身份標識IDVi以及投票標識BVi進行簽名,并將身份標識IDVi、投票標識BVi、自己的簽名公鑰pkO、加密后的選票Ci以及簽名一同發送到投票中心.

投票中心收到上述信息后,首先根據投票人發送的簽名信息和公鑰驗證投票人的簽名是否合法,若合法,則使用注冊中心的公鑰驗證SIGR(IDVi||BVi)中的IDVi||BVi是否和SIGO(IDVi||BVi)中 的IDVi||BVi相一致,若一致,則可確定該投票人是注冊中心認證過的合法投票人;其次,再根據BVi驗證選票的唯一性,若通過驗證,則可將選票納入統計中,如果沒有通過上述任何一項驗證,則丟棄該選票,不納入統計.投票中心將通過驗證的選票進行簽名發送到公示機構進行公示.

3.5 計票階段

待投票截止后,計票中心從公示中心獲得所有選票,并根據投票中心的公鑰驗證SIGV(IDVi||BVi||Ci)的合法性,若驗證通過,則開始計票,使用上述構造的同態計票器中的算法對加密選票進行計算得到最終結果S,C(j).并對S,C(j)進行簽 名,將S||C(j)||SIGS(S||C(j))發送到公示中心.

計票中心使用投票私鑰對投票結果S,C(j)進行解密,得到最終投票結果,將該結果發送到公示中心以待監督.

4 安全性分析

(1)合法性.在注冊階段每位投票人都會使用自己的身份材料去注冊中心進行注冊,注冊中心會對投票人的身份信息進行審核,只有通過審核的投票人才能參與投票.

(2)匿名性.首先在投票人通過注冊中心的審核后,注冊中心會給投票人發放一個和自己身份信息無關的身份標識,這樣很好的隱藏了投票人的真實身份信息;其次,在投票階段,投票人利用同態加密方案中的公鑰對選票進行加密,因此,除了投票人本身,其他任何人都不能通過加密的選票獲得選票的真實內容,也不能將選票和投票人的身份對應起來.

(3)唯一性.首先在注冊階段,通過注冊中心認證的合法投票人會獲得唯一投票標識,因此,每位投票人只擁有一次投票機會.

(4)公正性.在本方案中,投票私鑰由計票中心持有,計票中心在計算選票之后,使用該私鑰進行解密,得到最終結果.由于同態加密算法是對于密文進行計算,因此該計算可交給任何一個可信第三方,因此保證了方案的公正性.

(5)完備性.在投票階段,投票中心首先會根據注冊中心的信息對投票人的身份進行認證,保證投票人身份合法,其次會根據投票人的投票編號來檢查選票的唯一性,而且通過使用數字簽名技術可以對選票內容的完整性進行驗證,只有全部通過上述認證的選票才會被投票中心正確的統計,如若有一項沒有通過驗證,則會被丟棄,最終的計票結果只會統計合法選票.

(6)可驗證性.在投票階段,投票中心將收集到的選票公布在了公示中心,每位投票人都可以根據公告欄上的信息和自己持有的信息進行比對,以確認自己的選票是否有被正確統計.

(7)正當性.方案的每個階段都會進行身份認證來防止惡意的投票者破壞投票.

(8)無爭議性.由于本方案是基于ECDSA和全同態加密,因此方案的安全性是可證明的,方案中的各方的公鑰都是公開的,任何投票人或第三方都可驗證方案過程的正確性.

5 結束語

本文基于ECDSA數字簽名算法和基于LWE的同態加密方案提出了一種多候選人電子投票方案.在該方案中,利用安全性較高,密鑰長度短的簽名算法進行身份認證,從而提高了認證效率.而且還使用SIMD技術對選票進行打包,節省了計算成本;設計了一種同態計票器解決計票中存在的編解碼問題;在計票階段直接對密文進行計算,確保了選票的完全保密,本方案是一個匿名的可公開驗證的安全可行的電子投票方案.