基于同態(tài)的多對多電子投票方案設(shè)計(jì)*

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

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

0 引言

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

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

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

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

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

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

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

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

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

1 Paillier同態(tài)密碼

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

1.1 初始化

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

(1)選取兩個(gè)大素?cái)?shù)p和q；

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

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

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

1.2 Paillier密碼

Paillier加密過程描述如下：

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

(2)計(jì)算密文：

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

(1)

解密過程如下：

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

m=L(cλmodn2)·umodn

(2)

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

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

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

(3)

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

=En(g，n，m1+m2)

(4)

2 電子投票方案要求

2.1 投票場景

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

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

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

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

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

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

2.2 投票方式

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

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

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

圖1 電子投票方案框架圖

3.1 初始化階段

3.2 投票階段

投票階段按以下步驟進(jìn)行：

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

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

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

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

3.3 計(jì)票階段

計(jì)票階段的步驟如下：

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

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

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

4.1 正確性分析

(1)投票階段的正確性

投票人Pi的選票Ti=[ti，1，ti，2，…，ti，m]合格時(shí)必然會對應(yīng)到1，s，s2這3個(gè)值，因?yàn)椋?/p>

(5)

當(dāng)ci=1時(shí)，式子為：

(6)

當(dāng)ci=0時(shí)，式子為：

(7)

當(dāng)ci=-1時(shí)，式子為：

(8)

當(dāng)ci為其他值時(shí)，投票無效。

(2)計(jì)票階段的正確性

(9)

4.2 安全性分析

(1)合法性

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

(2)不可偽造性

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

(3)匿名性

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

(4)公平性

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

(5)不可篡改性

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

4.3 實(shí)驗(yàn)?zāi)M及效率分析

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

(1)通信需求

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

(2)計(jì)算復(fù)雜度

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

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

(10)

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

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

(11)

這個(gè)結(jié)果遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[16]中的計(jì)算復(fù)雜度。

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

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

圖2 本方案運(yùn)行時(shí)間模擬

5 結(jié)論

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