霍珊珊，李艷俊，，劉 健，羅昕銳

(1.中國電子科技集團公司第十五研究所 信息產(chǎn)業(yè)信息安全測評中心，北京 100083；2.北京電子科技學院，北京 100070)

0 引言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)所提供的各種便利服務(wù)也越來越為人們所接受與采用。與傳統(tǒng)的投票方案相比，電子投票方案基于密碼技術(shù)設(shè)計并通過網(wǎng)絡(luò)實現(xiàn)，投票和計票過程速度更快，投票結(jié)果也更準確，同時還能保護投票者的隱私安全，在保護公民的合法權(quán)益方面發(fā)揮著重要作用。21世紀以來，美國、瑞士等西方國家已經(jīng)在國內(nèi)大范圍使用電子投票系統(tǒng)，涉及政治、經(jīng)濟等多個領(lǐng)域。然而，近二十幾年美國發(fā)生多起電子投票系統(tǒng)被黑客入侵的事件，包括將候選人票數(shù)對調(diào)、錯算選票和不計算選票等。2019年，瑞士政府賞重金邀請黑客尋找電子投票系統(tǒng)的漏洞。2022 年7月巴西總統(tǒng)認為當時使用的電子投票系統(tǒng)存在漏洞而要求廢除。除此之外，法國、意大利和澳大利亞等國家的電子投票系統(tǒng)也都曾出現(xiàn)過嚴重漏洞。因此，電子投票的安全性至關(guān)重要。

電子投票方案除了應(yīng)該滿足傳統(tǒng)投票的主要功能外，還應(yīng)保證投票統(tǒng)計速度快、投票結(jié)果真實有效等需求，大致可總結(jié)為以下幾點：

(1)合法性：只有合法投票人才能投票，合法的選票必須保證全部計入總票數(shù)。

(2)不可偽造性：非法用戶不能截獲、篡改或者偽造選票。

(3)匿名性：合法投票人的選票內(nèi)容應(yīng)該保密，由選票判斷不出投票人任何信息。

(4)公平性：每個投票人只能投放一張選票，多張選票無法通過合格性檢驗。

(5)不可篡改性：在保證安全性的前提下，用戶可以驗證其選票是否被篡改。

電子投票系統(tǒng)通?；诿ず灻?、安全多方技術(shù)、秘密共享、同態(tài)加密等密碼技術(shù)設(shè)計。1992年，F(xiàn)ujioka等人[1]基于盲簽名提出了可適用于大規(guī)模投票的 FOO 方案，電子投票開始走向?qū)嵱谩?997年，Cramer等人[2]首次提出多位候選人的電子投票問題，并利用ElGamal加密系統(tǒng)同態(tài)性設(shè)計了多選一的電子投票方案，需要可信的計票中心接收選票并進行計票。2001年，基于Paillier加密系統(tǒng)的同態(tài)性Damgard等人[3]提出了一個多選多的電子投票方案，然而該方案無法避免重復投票現(xiàn)象。2006年，仲紅等人[4]提出一個無需第三方計票機構(gòu)參與的多選多電子投票方案，該方案基于安全多方求和技術(shù)設(shè)計，但投票結(jié)束后會公開所有候選人的票數(shù)。之后，研究人員基于安全多方計算中不經(jīng)意傳輸協(xié)議、求和技術(shù)分別進行了電子投票設(shè)計，然而存在實現(xiàn)效率不高或者應(yīng)用場景受限等問題[5-7]。同時期，基于秘密共享的電子投票方案也成為研究熱點之一[8-14]。2015年，李蓓[15]采用多種密碼體制進行了電子投票方案設(shè)計，由于密碼體制較多使得交互過程步驟增加明顯。2017年，黃仕杰等人[16]基于Paillier公鑰密碼體制的同態(tài)性提出了多對一電子投票的方案，實現(xiàn)了不解密選票的情況下能進行計票，然而計算量大，不能適用于大規(guī)模的投票。2019年，劉霆等人[17]將隨機性分組碼的秘密分享技術(shù)應(yīng)用于多候選人電子投票方案中，秘密交換次數(shù)多以致通信代價高。同年，付偉偉等人[18]基于隨機矩陣提出一個可驗證的多選一電子投票方案，需要計票中心參與，中心計算量大。2021年，邵清等[19]基于ElGamal強盲簽名和區(qū)塊鏈技術(shù)提出一種電子投票方案，由智能合約代替可信第三方進行選票合規(guī)性判斷、計票等工作，但投票人數(shù)增多時容易形成計算瓶頸。同年Lu等人[20]結(jié)合比特幣技術(shù)提出了安全電子投票系統(tǒng)，計算資源消耗仍然不可避免。近兩年，橢圓曲線密碼技術(shù)在越來越多的投票方案中使用[21-22]，2022年高小龍等人[23]推廣了橢圓曲線密碼體制在大規(guī)模場景中的電子投票方案，降低了通信代價，但是增加了計算量。隨著量子時代的來臨，基于后量子技術(shù)的投票方案也開始出現(xiàn)[24-25]，不過大都處于理論研究階段。

在實際現(xiàn)有的電子投票方案中，同態(tài)技術(shù)允許計票人在不解密的情況下對密文進行操作，更好地保證了選票的隱私性，而Paillier密碼和ElGamal密碼是最常用的選擇。Paillier密碼方便于最終計票，比ElGamal密碼的適應(yīng)性更強。只是基于這種密碼體制一般容易設(shè)計多對一電子投票方案，設(shè)計多對多的電子投票方案并不容易。本文基于Paillier密碼的同態(tài)性進行設(shè)計，可信中心采用預計算三元組的方式對選票合規(guī)性進行快速判斷，計票員從總投票中計算出每個候選人的總票數(shù)，投票人、計票員的計算量小，方案實現(xiàn)效率高，適用于大型電子投票的場合。

1 Paillier同態(tài)密碼

同態(tài)加密方案被分成3種類型：部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。同態(tài)加密方案在分布式計算環(huán)境下的密文數(shù)據(jù)計算方面有著重要的應(yīng)用，包括安全云計算與委托計算、遠程文件存儲、密文檢索等。目前全同態(tài)加密方案的構(gòu)造還處于理論階段，部分同態(tài)技術(shù)應(yīng)用較為廣泛。Paillier密碼是一種成熟的部分同態(tài)技術(shù)，即具有加法同態(tài)性質(zhì)，不具有乘法同態(tài)性質(zhì)，下面對該密碼體制進行描述。

1.1 初始化

Paillier密碼是一種公鑰密碼算法，其密鑰生成的參數(shù)選取以及主要步驟如下：

(1)選取兩個大素數(shù)p和q；

(2)計算n=pq，λ=lcm(p-1，q-1)，這里lcm表示最小公倍數(shù)(least common multiple)；

(4)隨機選取一個小于n2的正整數(shù)g，并且存在u=(L(gλmodn2))-1modn，如果不存在這樣的u，則要重新選擇g，或者從步驟(1)重新開始。

由以上步驟計算得到的公鑰為(n，g)，私鑰為(λ，u)。

1.2 Paillier密碼

Paillier加密過程描述如下：

假設(shè)明文為m，0

(2)計算密文：

En(g，n，m)=c=gmrnmodn2

(1)

解密過程如下：

使用私鑰計算De(g，n，c)=m，即明文：

m=L(cλmodn2)·umodn

(2)

1.3 Paillier密碼的同態(tài)性

Paillier密碼具有加法同態(tài)性質(zhì)，不具有乘法同態(tài)性質(zhì)，具體分析如下：

對于兩個不同明文m1，m2，加密后得到兩個不同的密文：

(3)

這兩個密文滿足以下式子，所以Paillier密碼具有加法同態(tài)性。

=En(g，n，m1+m2)

(4)

2 電子投票方案要求

2.1 投票場景

假設(shè)有N位投票人和m位候選人取得了合法身份標識P1，P2，…，PN和C1，C2，…，Cm，有資格進入投票系統(tǒng)參與投票和計票。投票人將從m位候選人中選出t位獲勝者，每個投票人可投贊成票不超過t個，也可以棄權(quán)。

投票系統(tǒng)主要角色：

(1)投票人：有資格參與投票的人，表示為P1，P2，…，PN；

(2)候選人：有資格被投票的人，表示為C1，C2，…，Cm；

(3)可信中心：檢驗投票人的身份信息，收集并公布合格投票的密文；

(4)計票中心：產(chǎn)生最終的投票密文，并將其解密，公布勝出的候選人。

2.2 投票方式

投票人Pi(i=1，2，…，N)對候選人(C1，C2，…，Cm)進行投票得到一個m元數(shù)組，每個分量tj(j=1，2，…，m)是選票計算得到的值；然后將這個m元數(shù)組交給可信中心，可信中心通過驗證公布合格票；最后計票中心計算總票數(shù)并公布排名前t的t個候選人。

3 基于同態(tài)的電子投票方案設(shè)計

本文設(shè)計的投票方案框架如圖1所示，具體分為三個階段：初始化階段、投票階段、計票階段。主要角色中的投票人、可信中心和計票員分別在不同階段行使自己的計算、核對、申訴等權(quán)利。公布欄公布相應(yīng)公開信息，不能泄露任何一個角色的秘密信息。

圖1 電子投票方案框架圖

3.1 初始化階段

3.2 投票階段

投票階段按以下步驟進行：

(1)每個投票人進行注冊。投票人與可信中心互相發(fā)送數(shù)字證書，雙方進行身份認證，并協(xié)商出共享密鑰Ki，可信中心預存標識h(IDi，Ki)。

投票人將[ti，1，ti，2，…，ti，m]、h(IDi，Ki)、時間戳T以及h([ti，1，ti，2，…，ti，m]‖IDi，Ki‖T)傳輸發(fā)送給可信中心。

若計算結(jié)果為1，則候選人Cj對應(yīng)的計數(shù)器增加1；若為s，則對應(yīng)計數(shù)器值不變；若為s2，則對應(yīng)計數(shù)器減去1。若三個值都不滿足，則該票無效，直接拋棄。

(4)可信中心將通過檢驗的合格投票在公開欄中公布，投票人通過計算h(IDi，Ki)確認自己的投票是否合格，未通過的投票可以由投票人提起申訴。

3.3 計票階段

計票階段的步驟如下：

(2)計票中心解密得到每個候選人Cj的票數(shù)并進行排序，然后根據(jù)要求公布排名前t位的候選人。

若有相同票數(shù)產(chǎn)生，則對后面幾位相同票數(shù)的候選人進行下一輪投票，直至選出t位候選人。

4 系統(tǒng)性能分析

4.1 正確性分析

(1)投票階段的正確性

投票人Pi的選票Ti=[ti，1，ti，2，…，ti，m]合格時必然會對應(yīng)到1，s，s2這3個值，因為：

(5)

當ci=1時，式子為：

(6)

當ci=0時，式子為：

(7)

當ci=-1時，式子為：

(8)

當ci為其他值時，投票無效。

(2)計票階段的正確性

(9)

4.2 安全性分析

(1)合法性

只有合法投票人才有權(quán)參加投票活動，在身份認證階段會對所有的投票人進行身份驗證，這一步可以確定投票權(quán)利的投票人；具有正確標識的投票才能被接收，保證合法的投票必然是由合法投票人提交的。

(2)不可偽造性

投票人傳輸給可信中心的信息包括[ti，1，ti，2，…，ti，m]、h(IDi，Ki)、時間戳T以及h([ti，1，ti，2，…，ti，m]‖IDi，Ki‖T)，其他人偽造相關(guān)信息的難度相當于破解hash函數(shù)。這樣保證了投票信息的不可偽造性。

(3)匿名性

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

(4)公平性

任何人及任何事情都不應(yīng)該影響到投票的最終結(jié)果，每位合法的投票人都可以獲得自己的唯一標識h(IDi，Ki)，并從公布欄查詢是否通過，如果發(fā)現(xiàn)中心未公布合法投票，則可以申訴。合法投票人有且只有一次投票機會，可信中心通過保留唯一標識h(IDi，Ki)確認投票次數(shù)，避免不誠信的投票人多次投票。

(5)不可篡改性

投票人可以通過公布欄確認自己的投票信息是否被篡改，同樣也可以根據(jù)公布欄中合格的投票驗證總投票是否被篡改，由此保證合格的投票不被篡改。

4.3 實驗?zāi)M及效率分析

本文在通信需求和計算復雜度兩方面與已存在的方案(文獻[4]、文獻[15]、文獻[16])進行了分析。

(1)通信需求

由于每種方案都有投票人注冊階段，因此通信代價比較中不考慮該部分。本方案中N個投票人在投票階段進行了N次傳輸，方案的通信復雜度為O(N)。消息包含[ti，1，ti，2，…，ti，m]、h(IDi，Ki)、時間戳T以及h([ti，1，ti，2，…，ti，m]‖IDi，Ki‖T)，時間戳T和hash值的長度各為256 bit，[ti，1，ti，2，…，ti，m]的長度為O(2m(log2n))，所以通信的位復雜度為O(2Nm(log2n))，優(yōu)于文獻[4]的通信代價O(N2m(log2n))。文獻[15]未給出通信代價，但是采用了AES、RSA和ElGamal三種主要密碼技術(shù)，投票階段通信代價為ElGamal算法的素數(shù)域q的長度，計票階段通信代價為RSA模n的長度，高于本方案的通信帶寬需求。

(2)計算復雜度

由于初始化階段的計算不影響投票速度，因此只考慮投票階段投票人、可信中心以及計票員的計算代價。每個投票人計算m次Paillier加密，等于m次模冪(n次冪)運算，復雜度約為O(m(log2n)2)，hash函數(shù)計算速度快可以忽略，N個投票人總計O(2Nm(log2n)2)?？尚胖行膶γ繌堖x票平均計算m次模冪(λ次冪)運算，并進行m次比對，總計計算復雜度：

O(2Nm(log2λ)(log2n))≈O(2Nm(log2n)2)

(10)

計票中心進行(N-1)次模乘運算，復雜度總計約為：

O(2(N-1)m(log2n)2)

(11)

這個結(jié)果遠遠小于文獻[16]中的計算復雜度。

綜上討論，本文投票方案與類似方案的通信需求和計算復雜度比較見表1。本方案模擬實現(xiàn)選取的實驗環(huán)境為：系統(tǒng)硬件為MateBook14 AMD Ryzen 5 4600H with Radeon Graphics 3 GHz、16 GB RAM，操作系統(tǒng)為X64，用C語言實現(xiàn)。當n=2 048 bit時，模冪運算為3 703次/s。假設(shè)候選人為10個，投票人數(shù)分別選取1千、5千、1萬、5萬、10萬人時，不同的運行用時模擬如圖2所示。容易看出，在10萬人參與投票的情形下模擬時間不超過30 s，實際情形下完全可以接受。當投票人數(shù)繼續(xù)增長超過10萬人后，可信中心的計算時間會呈近似線性增長，例如達到100萬人時，需要約300 s，這時增加多個服務(wù)器實現(xiàn)并行計算可以節(jié)省計算時間。

表1 類似電子投票方案比較

圖2 本方案運行時間模擬

5 結(jié)論

本文提出一種基于Paillier密碼設(shè)計的同態(tài)多選多電子投票方案，可以從m個候選人中選出t個勝出者，投票人、可信中心以及計票員的計算量小，方案實現(xiàn)效率高，適用于大型電子投票的場合。與已有方案相比，本文方案有更高的實際應(yīng)用價值。然而，隨著量子計算機的成熟，Paillier密碼基于的因子分解難題容易被量子Shor算法破解，所以研究后量子時代電子投票方案將是下一步工作的重點。