一種適用于大規(guī)模場(chǎng)景的匿名電子投票系統(tǒng)

高小龍 王 玉 安 鵬 唐 波 劉金會(huì),

1(西北工業(yè)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 西安 710129)

2(北京市國(guó)防動(dòng)員委員會(huì)辦公室 北京 100053)

3(北京明朝萬(wàn)達(dá)科技股份有限公司 北京 100142)

4(西北工業(yè)大學(xué)深圳研究院 廣東深圳 518057)

(3325605783@qq.com)

投票是體現(xiàn)民主和公平的一種重要形式，大到如國(guó)家領(lǐng)導(dǎo)人的選舉，小到如班級(jí)內(nèi)部的民主決定，都離不開(kāi)投票.近幾十年來(lái)，隨著社會(huì)的不斷發(fā)展，選民的數(shù)量越來(lái)越多，同時(shí)對(duì)選舉的公平性、匿名性、可驗(yàn)證性等要求也逐步提高.因此，國(guó)內(nèi)外出現(xiàn)了各種各樣的電子投票系統(tǒng).電子投票相較于傳統(tǒng)的紙質(zhì)投票，節(jié)省了人力物力財(cái)力，同時(shí)更加高效、準(zhǔn)確和公平.美國(guó)、巴西、印度、加拿大等國(guó)家已經(jīng)在國(guó)內(nèi)大范圍使用電子投票系統(tǒng)，使用場(chǎng)景涉及政治、經(jīng)濟(jì)等多方面.然而在2022年7月，巴西總統(tǒng)認(rèn)為電子投票系統(tǒng)不安全，要求廢除使用.除巴西外，法國(guó)、意大利、瑞士和澳大利亞等國(guó)家的電子投票系統(tǒng)此前也都曾出現(xiàn)過(guò)嚴(yán)重漏洞.因此，為了電子投票的進(jìn)一步推廣和發(fā)展，解決其安全性問(wèn)題刻不容緩.

電子投票系統(tǒng)是基于密碼學(xué)的綜合性系統(tǒng)，現(xiàn)有的電子投票系統(tǒng)所依賴(lài)的密碼學(xué)技術(shù)大致可以分為4類(lèi)：混合網(wǎng)絡(luò)、盲簽名、同態(tài)加密和秘密共享.其中，秘密共享技術(shù)安全性更強(qiáng)，數(shù)據(jù)處理效率更高.

本文系統(tǒng)是基于秘密共享的電子投票系統(tǒng)，使用2臺(tái)或2臺(tái)以上的投票服務(wù)器完成計(jì)票工作.只要有1臺(tái)投票服務(wù)器是誠(chéng)實(shí)的就可以保證投票的匿名性.除此之外，本文系統(tǒng)還滿(mǎn)足正確性，即完整性和可靠性，既要保證合法有效的投票得到統(tǒng)計(jì)，也要保證非法無(wú)效的投票不會(huì)影響投票結(jié)果.關(guān)于選票的合法有效，首先考慮選民身份的合法性，其次考慮選票格式的合法性.

1 相關(guān)工作

近幾十年來(lái)，隨著科研人員對(duì)秘密共享技術(shù)的研究不斷深入，基于秘密共享技術(shù)的電子投票系統(tǒng)得以快速發(fā)展.

Schoenmakers[1]提出了一種公開(kāi)可驗(yàn)證秘密共享(publicly verifiable secret sharing, PVSS)協(xié)議，在效率和困難問(wèn)題假設(shè)方面都有所改進(jìn)，可用于電子投票；Iftene[2]基于秘密共享技術(shù)，提出了一種多機(jī)構(gòu)電子投票方案，其中的各個(gè)機(jī)構(gòu)可以具有不同的權(quán)重；Zwierko等人[3]提出了一種基于代理的安全電子投票方案，代理生成過(guò)程中的預(yù)計(jì)算代替了選民的計(jì)算，減小了選民客戶(hù)端的計(jì)算負(fù)擔(dān)；Yuan等人[4]基于Mignotte閾值秘密共享技術(shù)，提出了一種分布式的可驗(yàn)證電子投票方案，滿(mǎn)足匿名性和可追溯性的同時(shí)，提高了計(jì)算速度；Gutub等人[5]提出了一種秘密共享方案，該方案基于共享中的并行技術(shù)生成秘密輸出；Li等人[6]提出了一種具有多級(jí)訪問(wèn)機(jī)構(gòu)的多秘密共享方案，不需要任何權(quán)限中心，由云服務(wù)器進(jìn)行計(jì)票且計(jì)算成本低；Joy等人[7]在量子處理器中實(shí)現(xiàn)了量子秘密共享協(xié)議，應(yīng)用于一種全新的量子二進(jìn)制投票協(xié)議；Shen等人[8]基于多項(xiàng)式承諾，針對(duì)智慧城市應(yīng)用提出了一種高效的云輔助可驗(yàn)證秘密共享方案；Pilaram等人[9]通過(guò)使用基于格的多階段秘密共享(threshold multi-stage secret sharing, TMSSS)方案共享私鑰，提出了一種匿名閾值簽名方案，保證安全性的同時(shí)效率更高；Hao等人[10]對(duì)現(xiàn)有的電子投票方案進(jìn)行了改進(jìn)，用屏蔽值掩蓋選民的選票，實(shí)現(xiàn)了強(qiáng)制抵抗性；Sutradhar等人[11]針對(duì)量子秘密共享協(xié)議中存在的缺少參與者信息的情況下無(wú)法重建秘密的問(wèn)題，提出了一種解決方案；Kiamari等人[12]提出了一種基于錯(cuò)誤學(xué)習(xí)(learning with errors, LWE)問(wèn)題的可驗(yàn)證多秘密共享方案，不需要過(guò)多的通信就能實(shí)現(xiàn)驗(yàn)證性；Tejedor-Romero等人[13]提出了一個(gè)名為DiverSEC的分布式遠(yuǎn)程電子投票系統(tǒng)，確保了投案的匿名性和完整性；Bartolucci等人[14]提出了一種基于區(qū)塊鏈技術(shù)的電子投票方案；Lu等人[15]設(shè)計(jì)了一種基于秘密共享的電子投票協(xié)議，可以防止投票數(shù)提前泄露；Yan等人[16]基于中國(guó)剩余定理，提出了一種可逆圖像的秘密共享算法；Gutub等人[17]提出了一種分配模型，用于多用戶(hù)身份驗(yàn)證；Srinivasan等人[18]提出了一個(gè)編譯器，可以用于生成局部泄露的彈性秘密共享方案；Alkhodaidi等人[19]在基于計(jì)數(shù)的秘密共享方案中引入一種新算法，通過(guò)增加密鑰的長(zhǎng)度，可以生成無(wú)限的共享密鑰；馬英[20]提出了一種基于隱私計(jì)算的數(shù)據(jù)共享模型，并提出了數(shù)據(jù)統(tǒng)計(jì)分析的應(yīng)用流程.

雖然基于秘密共享的電子投票方案系統(tǒng)有安全性和數(shù)據(jù)處理效率方面的優(yōu)勢(shì)，但系統(tǒng)組成復(fù)雜，因此，應(yīng)用于大規(guī)模投票場(chǎng)景時(shí)，系統(tǒng)多方之間的通信復(fù)雜度是此類(lèi)方案的一大挑戰(zhàn).而當(dāng)電子投票系統(tǒng)要求可驗(yàn)證性時(shí)，這個(gè)問(wèn)題就顯得更加突出.

本文主要貢獻(xiàn)如下：

1) 提出了一個(gè)非交互可驗(yàn)證的安全電子投票系統(tǒng)，選舉機(jī)構(gòu)可以根據(jù)需要，生成相應(yīng)的選票類(lèi)型，應(yīng)用場(chǎng)景廣泛.

2) 滿(mǎn)足可靠性、完整性、匿名性、不可重用性、可驗(yàn)證性、公平性、合法性和懲罰性等安全屬性.

3) 使用一種非交互式的零知識(shí)驗(yàn)證方法，在保證安全性的同時(shí)，降低了系統(tǒng)的通信復(fù)雜度.當(dāng)系統(tǒng)應(yīng)用2～6個(gè)投票服務(wù)器時(shí)，對(duì)于1萬(wàn)選民以下的小型投票場(chǎng)景，系統(tǒng)耗時(shí)在5 s以?xún)?nèi)；對(duì)于10萬(wàn)選民以上的大型投票場(chǎng)景，系統(tǒng)耗時(shí)在50 s以?xún)?nèi)，是可以容忍的耗時(shí).

2 預(yù)備知識(shí)

2.1橢圓曲線密碼學(xué)

橢圓曲線密碼學(xué)(ECC)是一種基于橢圓曲線數(shù)學(xué)難題的公鑰算法，在20世紀(jì)80年代首先由Koblitz[21]和Miller[22]分別提出.其最大的優(yōu)勢(shì)在于，相比于RSA加密算法，ECC使用相同長(zhǎng)度的密鑰可以提供更強(qiáng)的安全性.

2.1.1 基于橢圓曲線的加密算法

設(shè)置階段:{p,a,b,G,n}.選取大素?cái)?shù)p，a,b∈Fp，基點(diǎn)G=(x,y)，|G|=n，n也為大素?cái)?shù)，G為n階循環(huán)群.隨機(jī)選取d∈[1,n-1]，計(jì)算P=dG.

私鑰：d∈[1,n-1]；公鑰：{p,a,b,G,n,P}.

加密：

1) 對(duì)消息M，隨機(jī)選取臨時(shí)密鑰k∈[1,n-1]，計(jì)算c1=kG；

2) 計(jì)算kP=(x,y)，c2=mxmodn；

3) 密文為(c1,c2).

解密：

1) 計(jì)算Q=dc1=kdG=kP=(x,y)；

2) 計(jì)算M=c2x-1modn.

2.1.2 基于橢圓曲線的簽名算法

私鑰：d∈[1,n-1]；公鑰：{p,a,b,G,n,P}.

簽名：

1) 隨機(jī)選取臨時(shí)密鑰k∈[1,n-1]，計(jì)算kG=(x,y)；

2) 計(jì)算e=Hash(M),r=xmodn以及s=k-1(e+rd) modn；

3) 簽名即為(r,s).

驗(yàn)證：

1)sk=e+rdmodn；

2)kG=s-1(eG+rp)=(x1,y)；

3) 驗(yàn)證r=x1是否成立.

2.2 Beaver的安全多方計(jì)算協(xié)議

每個(gè)服務(wù)器協(xié)議開(kāi)始時(shí)，有輸入向量x的份額[xi]，服務(wù)器根據(jù)運(yùn)算電路C，想要計(jì)算得到C(x).為了保證匿名性，只有所有服務(wù)器都誠(chéng)實(shí)才能恢復(fù)出電路中所有線路上的值.

算術(shù)電路中有加法門(mén)和乘法門(mén).

加法門(mén)：[y+z]i=[y]i+[z]i.

乘法門(mén)：[Ay]i=A[yi].

利用三元組(a,b,c)，服務(wù)器計(jì)算yz：

1) 計(jì)算[d]i=[y]i-[a]i和[e]i=[z]i-[b]i；

2) 計(jì)算聚合值

de+db+ea+c=

(y-a)(z-b)+(y-a)b+(z-b)a+c=

(y-a)z+(z-b)a+c=

yz-az+az-ab+c=

yz-ab+c=yz.

2.3 分布式點(diǎn)函數(shù)

對(duì)于隱私數(shù)據(jù)xi，有s個(gè)服務(wù)器，分布式點(diǎn)函數(shù)將隱私數(shù)據(jù)分為[xi]1,[xi]2,…,[xi]s∈Fp，要求滿(mǎn)足xi=[xi]1+[xi]2+…+[xi]s∈Fp，且只有當(dāng)所有的服務(wù)器都誠(chéng)實(shí)，才可以恢復(fù)出原始的隱私數(shù)據(jù)xi.

2.4 秘密共享非交互式證明

零知識(shí)證明是一方向另一方證明某個(gè)命題，而除了對(duì)該命題的證明以外，不會(huì)泄露任何其他信息，傳統(tǒng)的零知識(shí)證明算法有非交互式零知識(shí)證明(non-interactive zero-knowledge, NIZK)和簡(jiǎn)短無(wú)交互證明(succinct non-interactive adaptive argument of knowledge, SNARK)等.

秘密共享非交互式證明(secret-shared non-interactive proofs, SNIPs)與傳統(tǒng)零知識(shí)證明的目的基本一致，但相比而言效率高100倍[23].工作流程如下：

1) 客戶(hù)端評(píng)估.

客戶(hù)端將自己的隱私信息用可加性的分布式點(diǎn)函數(shù)進(jìn)行劃分，然后計(jì)算驗(yàn)證函數(shù)中乘法門(mén)的每個(gè)輸出，并使用插值法將其描述為多項(xiàng)式形式，發(fā)送給相應(yīng)的服務(wù)器.

2) 服務(wù)器進(jìn)行一致性檢查.

服務(wù)器除接收到客戶(hù)端發(fā)送的多項(xiàng)式形式的乘法門(mén)輸出外，還持有相應(yīng)的輸入份額.服務(wù)器據(jù)此，利用簡(jiǎn)單的仿射運(yùn)算就可以得出每個(gè)乘法門(mén)的輸出.根據(jù)計(jì)算出的輸出插值計(jì)算出輸出多項(xiàng)式，與客戶(hù)端發(fā)送的輸出多項(xiàng)式進(jìn)行比較.若相同，則一致性檢查通過(guò)，否則不通過(guò).

3) 多項(xiàng)式驗(yàn)證和份額乘法.

主要借助Beaver的安全多方計(jì)算協(xié)議中乘法門(mén)的計(jì)算方法，對(duì)2)中乘法門(mén)的輸出值進(jìn)行計(jì)算.

4) 輸出驗(yàn)證.

如果所有的服務(wù)器都誠(chéng)實(shí)，每個(gè)服務(wù)器公布其輸出端的份額數(shù)據(jù)，所有的服務(wù)器將監(jiān)聽(tīng)到的廣播消息進(jìn)行加和，檢查最后驗(yàn)證函數(shù)的值是否為1，是則符合對(duì)格式的要求，否則不合要求，拋棄該數(shù)據(jù).

3 系統(tǒng)目標(biāo)

3.1 系統(tǒng)模型

本文系統(tǒng)中主要涉及四方實(shí)體：權(quán)威機(jī)構(gòu)、選舉機(jī)構(gòu)、選民和投票服務(wù)器.其各自在系統(tǒng)中的任務(wù)如下：

1) 權(quán)威機(jī)構(gòu).為選民生成公私鑰對(duì)，用以確定合法的選民群體和認(rèn)證選民身份.

2) 選舉機(jī)構(gòu).主要負(fù)責(zé)發(fā)起投票，涉及確定候選者名單、合法的選民名單以及其他相關(guān)參數(shù)等內(nèi)容.

3) 選民.對(duì)選舉機(jī)構(gòu)發(fā)起的投票內(nèi)容進(jìn)行合法投票.

4) 投票服務(wù)器.最少有2臺(tái)，主要負(fù)責(zé)接收選民發(fā)來(lái)的選票，將合法的選票計(jì)入投票結(jié)果.

如圖1所示，本文系統(tǒng)的基本應(yīng)用流程如下：

1) 選民注冊(cè)及發(fā)起投票(①②).首先，選民在權(quán)威機(jī)構(gòu)進(jìn)行注冊(cè)用于表征身份；然后，由選舉機(jī)構(gòu)確定合法的選民群體，并發(fā)起投票，將投票和選民的相關(guān)信息發(fā)送給投票服務(wù)器，將投票相關(guān)信息和對(duì)應(yīng)的選民序號(hào)發(fā)送給選民.

2) 選民上傳選票(③).大量合法的選民在各自客戶(hù)端將選票數(shù)據(jù)及其驗(yàn)證信息發(fā)送到少量的幾個(gè)投票服務(wù)器中.

3) 驗(yàn)證及累加選票(④).由投票服務(wù)器對(duì)選民進(jìn)行身份驗(yàn)證，對(duì)選票進(jìn)行格式驗(yàn)證，驗(yàn)證通過(guò)后，將選票信息存儲(chǔ)在本地聚合器中.

4) 廣播投票數(shù)據(jù)(⑤).當(dāng)各個(gè)投票服務(wù)器的聚合器中新選票數(shù)目達(dá)到一定值，將聚合器中的信息進(jìn)行廣播.所有投票服務(wù)器收到彼此的廣播后，將廣播的信息進(jìn)行加和操作，得到這些選票的統(tǒng)計(jì)數(shù)據(jù).在整個(gè)投票過(guò)程中，系統(tǒng)各方不知道任何一位選民的選票內(nèi)容，保證了系統(tǒng)匿名性.

圖1 電子投票系統(tǒng)工作模型

3.2 安全要求

本文系統(tǒng)要求實(shí)現(xiàn)以下安全屬性：

1) 可靠性.非法無(wú)效的選票極大的概率不會(huì)被計(jì)入投票系統(tǒng)的聚合器.

2) 完整性.合法有效的選票應(yīng)該以極大的概率被計(jì)入投票系統(tǒng)的聚合器.

3) 匿名性.選民的投票內(nèi)容保密，本文系統(tǒng)中，可以有2臺(tái)或2臺(tái)以上的投票服務(wù)器，只要有1臺(tái)投票服務(wù)器是誠(chéng)實(shí)的，就可以保證選票和選民之間對(duì)應(yīng)關(guān)系的不可知.

4) 不可重用性.任何選票，不能被多次計(jì)入投票統(tǒng)計(jì)結(jié)果，任何人都只能投1次票.

5) 可驗(yàn)證性.沒(méi)有人能偽造投票結(jié)果，選民可以驗(yàn)證自己的投票是否被統(tǒng)計(jì).

6) 公平性.投票參與的各方都無(wú)法在投票未結(jié)束前知道選票消息，直到所有投票服務(wù)器廣播了其聚合器中的數(shù)據(jù).

7) 合法性.只有經(jīng)過(guò)授權(quán)的選民，其所投出的選票才合法有效，可以被計(jì)入投票統(tǒng)計(jì)結(jié)果.

8) 懲罰性.如果某選民具有選票多次重用、多次選票格式錯(cuò)誤等惡意行為，系統(tǒng)能夠?qū)υ撨x民進(jìn)行懲罰.

4 具體方案構(gòu)造

本節(jié)將對(duì)投票系統(tǒng)中運(yùn)行的完整細(xì)節(jié)進(jìn)行描述，涉及劃分選票的分布式點(diǎn)函數(shù)和投票服務(wù)器間驗(yàn)證選票有效性的安全多方計(jì)算等實(shí)現(xiàn)細(xì)節(jié).

1) 選民注冊(cè).

在投票開(kāi)始之前，每個(gè)潛在的選民和候選人都應(yīng)該在選舉機(jī)構(gòu)認(rèn)可的權(quán)威機(jī)構(gòu)進(jìn)行注冊(cè)，權(quán)威機(jī)構(gòu)為每個(gè)選民i分發(fā)公私鑰對(duì)(PKi,SKi).公鑰PKi可以用作選民i的郵箱地址或者標(biāo)識(shí)，類(lèi)似于選民的名字，可以由選舉機(jī)構(gòu)進(jìn)行公開(kāi).

2) 投票發(fā)起.

由選舉機(jī)構(gòu)根據(jù)需求發(fā)起投票.

首先，選舉機(jī)構(gòu)確定選民群體L，將合法選民的公鑰列表(由權(quán)威機(jī)構(gòu)或選民提供)整理，得到L={PK1,PK2,…,PKn}，并為每個(gè)選民生成1個(gè)應(yīng)用于此場(chǎng)景下的序號(hào)Vi，要求序號(hào)空間2λ遠(yuǎn)遠(yuǎn)大于實(shí)際的選民數(shù)量n，借助該序號(hào)系統(tǒng)可以快速識(shí)別非法用戶(hù)，這里的空間長(zhǎng)度λ暫定為128 b.

然后，選舉機(jī)構(gòu)確定候選人信息和投票格式.選舉機(jī)構(gòu)將合法的選民公鑰列表L={PK1,PK2,…,PKn}、與之對(duì)應(yīng)的選民序號(hào)V={V1,V2,…,Vn}和生成的投票格式T發(fā)送給投票服務(wù)器.投票服務(wù)器將依據(jù)(L,V,T)對(duì)選民選票進(jìn)行驗(yàn)證.

最后，選舉機(jī)構(gòu)將選民序號(hào)用選民i投票使用的公鑰進(jìn)行加密EncPKi(Vi)并發(fā)送給選民i，將投票格式T公開(kāi).至此，投票的前期準(zhǔn)備工作結(jié)束，計(jì)票正式開(kāi)始.

3) 選票上傳.

如圖2所示，選民i首先根據(jù)投票格式T填寫(xiě)合法的選票內(nèi)容，然后使用仿射可聚合編碼方法(affine aggregatable encodings, AFEs)[23]編碼生成選票Ticketi，然后將選票使用可加性的分布式點(diǎn)函數(shù)進(jìn)行劃分，劃分的個(gè)數(shù)和投票服務(wù)器的個(gè)數(shù)s相同.

圖2 投票上傳

圖3 選票信息聚合

選民客戶(hù)端首先根據(jù)分布式點(diǎn)函數(shù)fv,m:[2λ]→{0,1}|m|，將自己的選票Ticketi分為s份{Ticketi1,Ticketi2,…,Ticketis}.

此外，選民使用SNIPs[23]方法生成關(guān)于選票的證明πi={πi1,πi2,…,πis}，在不泄露選票內(nèi)容的前提下，證明自己的選票Ticketi是有效的.

然后，將劃分后的選票用選民自己的私鑰SKi進(jìn)行ECDSA簽名，和對(duì)應(yīng)的證明、選民的序號(hào)Vi一起，用投票服務(wù)器j的公鑰PKserverj進(jìn)行加密，發(fā)送到相應(yīng)的投票服務(wù)器j，j∈(1,s)，如

EncPKserverj(SignSKi(Ticketij),πij,Vi).

4) 選票信息聚合.

投票服務(wù)器j收到選民i的選票EncPKserverj(SignSKi(Ticketij),πij,Vi)后，首先用自己的私鑰SKserverj解密提取出選民序號(hào)Vi，驗(yàn)證Vi在本次投票中是否有意義.如果沒(méi)意義，丟棄該選票，如果Vi已經(jīng)被標(biāo)記，將Vi對(duì)應(yīng)的PKi提交給選舉機(jī)構(gòu)進(jìn)行懲罰；否則，進(jìn)一步用Vi對(duì)應(yīng)的公鑰PKi對(duì)SignSKi(Ticketij)進(jìn)行驗(yàn)證，驗(yàn)證失敗則丟棄；驗(yàn)證成功則利用πij驗(yàn)證Ticketij的有效性.若上述驗(yàn)證通過(guò)，將Ticketij的信息壓入投票服務(wù)器j的聚合器中，同時(shí)將Vi進(jìn)行標(biāo)記.如圖3所示:

5) 公布投票結(jié)果.

當(dāng)聚合器中聚合了一定數(shù)目的選票時(shí)，各個(gè)投票服務(wù)器將自己的聚合器數(shù)據(jù)進(jìn)行廣播，系統(tǒng)各方通過(guò)監(jiān)聽(tīng)廣播，都可以獲取投票統(tǒng)計(jì)數(shù)據(jù)和投票成功選民序號(hào).與此同時(shí)，選舉機(jī)構(gòu)公示投票結(jié)果和投票成功的選民序號(hào)，可供選民不用監(jiān)聽(tīng)廣播直接請(qǐng)求獲得.

5 安全性和性能分析

5.1 安全性分析

本文系統(tǒng)中，可以有2臺(tái)或2臺(tái)以上的投票服務(wù)器，本文的安全性分析是以2臺(tái)投票服務(wù)器、選票形式為多選1、無(wú)特權(quán)選民的情況為例進(jìn)行分析.

1) 正確性.

這里的正確性直接依賴(lài)于分布式點(diǎn)函數(shù)和秘密共享非交互式證明方法的正確性，本文系統(tǒng)可以大概率地分辨出針對(duì)格式的有效和無(wú)效選票.采用有效的選票，丟棄無(wú)效的選票，從而保證系統(tǒng)的可靠性和完整性.

聲明：2臺(tái)投票服務(wù)器A和B，在驗(yàn)證選票合法性的秘密共享非交互式證明協(xié)議開(kāi)始時(shí)，分別持有份額向量wA∈Fn和wB∈Fn，并且滿(mǎn)足w=wA+wB∈Fn，若協(xié)議驗(yàn)證w的漢明重量為1，則認(rèn)為該選票正確，協(xié)議出錯(cuò)的可能性為ε=O(1/|F|).

取F的大小為2λ，其中改變安全參數(shù)λ的取值，可以使錯(cuò)誤概率ε足夠小.

該聲明的正確是因?yàn)槊孛芄蚕矸墙换ナ阶C明協(xié)議只有當(dāng)滿(mǎn)足以下條件時(shí)才會(huì)接收錯(cuò)誤的選票：

① 秘密共享非交互式證明的魯棒性要求，只有當(dāng)輸入滿(mǎn)足投票內(nèi)容對(duì)應(yīng)的關(guān)系式時(shí)才接受選票；

② 不止1種非零選票w，可以使得等式c2-mC=0成立.其中C為選票對(duì)應(yīng)的運(yùn)算電路，該等式成立意味著2個(gè)內(nèi)容不同的選票生成的運(yùn)算電路C是相同的.

這2種錯(cuò)誤發(fā)生的可能性ε在域F中可以忽略不計(jì).

2) 匿名性.

選民的投票內(nèi)容保密，本文系統(tǒng)中，只要有1臺(tái)投票服務(wù)器是誠(chéng)實(shí)的，就可以保證選票與選民對(duì)應(yīng)關(guān)系的不可知.

這里的匿名性包括分布式點(diǎn)函數(shù)和秘密共享非交互式證明協(xié)議的零知識(shí)性.

對(duì)于分布式點(diǎn)函數(shù)，假定一個(gè)仿真算法Sim可以產(chǎn)生輸出.當(dāng)w=wA+wB∈Fn只能對(duì)應(yīng)1個(gè)漢明重量為1的向量，這些輸出的分布與正常工作的投票服務(wù)器所看到的分布在計(jì)算上無(wú)法區(qū)分.因此，敵手運(yùn)行Sim程序和在正常工作中獲得的信息一樣多，因此證明了分布式點(diǎn)函數(shù)的零知識(shí)性.

對(duì)于秘密共享非交互式證明的安全性證明，在文獻(xiàn)[23]中有完整的證明步驟，適用于此處.

3) 不可重用性.

任何1張選票，不能被多次計(jì)入投票統(tǒng)計(jì)結(jié)果.本文系統(tǒng)中.成功進(jìn)行過(guò)投票的選民，其選民序號(hào)會(huì)被標(biāo)記，因此，任何一位選民都無(wú)法進(jìn)行2次及以上的成功投票.

該安全屬性的保證間接依賴(lài)于分布式點(diǎn)函數(shù)和秘密共享非交互式證明的正確性.

假設(shè)當(dāng)所有服務(wù)器對(duì)某條選票w都認(rèn)證通過(guò)了，此時(shí)，所有服務(wù)器中的對(duì)應(yīng)選民序號(hào)Vi都會(huì)被打上標(biāo)記.聚合器累計(jì)一定數(shù)目的選票后，服務(wù)器開(kāi)始廣播，僅當(dāng)所有服務(wù)器廣播，認(rèn)定某序號(hào)Vi被打上標(biāo)記后，才認(rèn)為投票成功.

此時(shí)，假設(shè)序號(hào)為Vi的選民再次投票，根據(jù)系統(tǒng)的安全性假設(shè)：至少有1個(gè)服務(wù)器是誠(chéng)實(shí)的.那么，誠(chéng)實(shí)的投票服務(wù)器將選票份額及其證明丟棄，缺少1份選票份額及其份額，分布式點(diǎn)函數(shù)就無(wú)法計(jì)算出w=wA+wB∈Fn，此時(shí)秘密共享非交互式證明協(xié)議的驗(yàn)證函數(shù)Vaild(·)≠1，這2項(xiàng)的保證在正確性部分中已經(jīng)得到討論，只有可以忽略的錯(cuò)誤概率.

4) 可驗(yàn)證性.

系統(tǒng)各方都無(wú)法偽造投票結(jié)果，選民可以驗(yàn)證自己的投票是否被統(tǒng)計(jì).投票成功的選民序號(hào)Vi會(huì)被選舉機(jī)構(gòu)公開(kāi)，選民知道自己投票的時(shí)間段，只要找到這個(gè)時(shí)間段成功投票的選民序號(hào){Vi}，查看其中的選民序號(hào)就可以驗(yàn)證自己投票是否成功.

只要有1個(gè)服務(wù)器是誠(chéng)實(shí)的，就可以保證可驗(yàn)證性，這條性質(zhì)的保證間接依賴(lài)于分布式點(diǎn)函數(shù)和秘密共享非交互式證明的正確性.

首先討論驗(yàn)證投票是否成功.只要有1個(gè)投票服務(wù)器是誠(chéng)實(shí)的，投票不論成功與否，投票是否成功和驗(yàn)證是否存在一定保持一致.

再假設(shè)投票成功，討論驗(yàn)證過(guò)的真實(shí)投票和選民原始投票不一樣的可能性.根據(jù)前面對(duì)系統(tǒng)正確性的分析，這種可能性是可以忽略的.對(duì)于秘密共享非交互式證明來(lái)說(shuō)，和系統(tǒng)正確性中的討論結(jié)果一致.

5) 公平性.

對(duì)于該電子投票系統(tǒng)模型中的四方實(shí)體：選民、投票服務(wù)器，選舉機(jī)構(gòu)和權(quán)威結(jié)構(gòu)，沒(méi)有任何一方可以在投票未完成前，知道投票的階段性狀態(tài).直到所有投票服務(wù)器廣播了其聚合器中的數(shù)據(jù)，選舉機(jī)構(gòu)宣布投票結(jié)束后，各方才能知道投票結(jié)果.

這里的公平性直接依賴(lài)于系統(tǒng)的匿名性.在匿名性得到滿(mǎn)足的情況下，投票未結(jié)束前，所有的選票信息都分布在各個(gè)投票服務(wù)器的聚合器數(shù)據(jù)VoteDataj中，只有投票最后階段，所有投票服務(wù)器的VoteDataj按照分布式點(diǎn)函數(shù)算法進(jìn)行恢復(fù)，才能最后得到投票結(jié)果VoteData.

對(duì)于系統(tǒng)匿名性的討論分析這里不再累述.

6) 合法性.

只有經(jīng)過(guò)授權(quán)的選民，其所投出的選票才合法有效，可以被計(jì)入投票統(tǒng)計(jì)結(jié)果.本文系統(tǒng)首先使用選民序號(hào)機(jī)制快速判斷選民身份的合法性，然后再用選民序號(hào)Vi對(duì)應(yīng)的公鑰PKi進(jìn)一步驗(yàn)證其簽名的正確性.

合法性依賴(lài)于對(duì)用戶(hù)序號(hào)的查驗(yàn)和對(duì)用戶(hù)簽名的驗(yàn)證.

首先，序號(hào)空間的大小為2λ，這里λ暫定取128 b，遠(yuǎn)遠(yuǎn)大于幾乎所有的投票場(chǎng)景下的選民數(shù)量，因此，敵手難以對(duì)選民序號(hào)進(jìn)行碰撞攻擊.對(duì)于有n名選民的投票場(chǎng)景，碰撞發(fā)生的可能性ε=O(n/2λ).

除此之外，對(duì)用戶(hù)私鑰簽名的驗(yàn)證進(jìn)一步確保即使發(fā)生碰撞，也可以依賴(lài)簽名的合法性驗(yàn)證選民的合法性.而使用用戶(hù)序號(hào)進(jìn)行先驗(yàn)的方法簡(jiǎn)單有效，可以快速篩去大多數(shù)惡意的選票，增強(qiáng)系統(tǒng)對(duì)拒絕服務(wù)攻擊的抵抗.

7) 可懲罰性.

因?yàn)橥镀狈?wù)器可以簡(jiǎn)單地將選民序號(hào)進(jìn)行標(biāo)記，如果某選民存在選票重用、投票格式多次錯(cuò)誤等惡意行為，那么，投票服務(wù)器就可以將該選民序號(hào)發(fā)送給選舉機(jī)構(gòu)，由機(jī)構(gòu)對(duì)該序號(hào)Vi對(duì)應(yīng)的選民i，根據(jù)實(shí)際情況和影響進(jìn)行處罰.

可懲罰性的實(shí)現(xiàn)間接依賴(lài)于系統(tǒng)的正確性，因?yàn)檎_性保證，所有投票服務(wù)器都認(rèn)定的惡意選民會(huì)被懲罰，同時(shí)只要有1臺(tái)誠(chéng)實(shí)的投票服務(wù)器，行為合法的選民就不會(huì)被懲罰.

本文與部分文獻(xiàn)安全性比較如表1所示：

表1 電子投票系統(tǒng)安全性比較

5.2 性能分析

為了對(duì)系統(tǒng)性能進(jìn)行評(píng)估分析，使用1臺(tái)戴爾筆記本進(jìn)行實(shí)驗(yàn)，具體配置為Intel?CoreTMi7-8750H CPU，2.20 GHz，8 GB RAM.

為了保證電子投票系統(tǒng)的匿名性，驗(yàn)證過(guò)程需要保證零知識(shí)性，與使用其他零知識(shí)證明算法的電子投票系統(tǒng)相比，本文系統(tǒng)中選民客戶(hù)端和投票服務(wù)器的計(jì)算復(fù)雜度都更低.尤其是計(jì)算最為耗時(shí)的指數(shù)運(yùn)算，NIZK和SNARK都無(wú)法避免，而本文系統(tǒng)不涉及指數(shù)運(yùn)算，因而為實(shí)現(xiàn)零知識(shí)所付出的計(jì)算成本較低，具體分析如表2所示：

表2 電子投票系統(tǒng)客戶(hù)端與服務(wù)器的計(jì)算復(fù)雜度對(duì)比

注：M為驗(yàn)證函數(shù)中乘法門(mén)的數(shù)量.

本文系統(tǒng)可以應(yīng)用于多種投票類(lèi)型，尤其是復(fù)雜的投票場(chǎng)景.現(xiàn)在以5臺(tái)投票服務(wù)器的場(chǎng)景為例，研究選票內(nèi)容長(zhǎng)度和選民的客戶(hù)端耗時(shí)之間的關(guān)系.數(shù)據(jù)來(lái)自1 000條相同長(zhǎng)度的選票取均值，如圖4所示：

圖4 選票長(zhǎng)度和客戶(hù)端耗時(shí)的關(guān)系

由圖4可以看出，選票內(nèi)容長(zhǎng)度在29b以下時(shí)，平均耗時(shí)在10 ms以?xún)?nèi)，長(zhǎng)度達(dá)到212b時(shí)，每張選票的平均耗時(shí)也在80 ms以?xún)?nèi).長(zhǎng)度為212b的選票足以應(yīng)付絕大多數(shù)應(yīng)用場(chǎng)景.

本文系統(tǒng)可以使用多個(gè)投票服務(wù)器，此處以2個(gè)候選人、2選1的選票種類(lèi)的場(chǎng)景為例，對(duì)投票系統(tǒng)耗時(shí)和投票服務(wù)器數(shù)量、選民數(shù)量之間的關(guān)系進(jìn)行分析，每種情況下的數(shù)據(jù)為8次重復(fù)測(cè)試取平均值的結(jié)果.如圖5所示：

圖5 投票耗時(shí)與投票服務(wù)器和選民數(shù)量的關(guān)系

圖5顯示，當(dāng)選民數(shù)量在1萬(wàn)人以下時(shí)，投票耗時(shí)與服務(wù)器數(shù)量關(guān)系不明顯，從2臺(tái)投票服務(wù)器到6臺(tái)投票服務(wù)器，投票耗時(shí)都在5 s以?xún)?nèi).當(dāng)選民數(shù)量達(dá)到5萬(wàn)及以上時(shí)，系統(tǒng)投票耗時(shí)大大增加，同時(shí)受投票服務(wù)器數(shù)量影響明顯.當(dāng)投票服務(wù)器的數(shù)量達(dá)到6臺(tái)時(shí)，系統(tǒng)耗時(shí)達(dá)到了25 s.當(dāng)在10萬(wàn)選民、2臺(tái)投票服務(wù)器時(shí)，投票時(shí)間少于20 s，當(dāng)投票服務(wù)器的數(shù)量為6，系統(tǒng)耗時(shí)依然在50 s內(nèi).

由圖5可知，對(duì)于1萬(wàn)人以?xún)?nèi)的小型投票應(yīng)用場(chǎng)景，該電子投票系統(tǒng)的系統(tǒng)耗時(shí)都在5 s以?xún)?nèi)，即使在10萬(wàn)人的大型投票應(yīng)用中，也可以把投票耗時(shí)維持在50 s以?xún)?nèi)，適用于大多數(shù)投票場(chǎng)景.

6 結(jié) 論

本文設(shè)計(jì)了一種適用于大規(guī)模場(chǎng)景的匿名電子投票系統(tǒng)，使用1組投票服務(wù)器對(duì)一定數(shù)量的投票結(jié)果進(jìn)行聚合統(tǒng)計(jì)，保護(hù)了選民的隱私，同時(shí)防御了惡意投票行為.一方面，通過(guò)非交互式驗(yàn)證的方式滿(mǎn)足了電子投票系統(tǒng)對(duì)惡意選票的抵抗能力，也沒(méi)有顯著增加系統(tǒng)各方之間的通信復(fù)雜度和計(jì)算復(fù)雜度；另一方面，秘密共享非交互式證明的零知識(shí)性保證了系統(tǒng)匿名性.對(duì)于絕大多數(shù)的投票場(chǎng)景，本文系統(tǒng)在時(shí)間開(kāi)銷(xiāo)方面都表現(xiàn)優(yōu)秀，尤其是在10萬(wàn)人的大型投票場(chǎng)景中，系統(tǒng)耗時(shí)也可以滿(mǎn)足多數(shù)應(yīng)用要求.這些投票是在各選民平等投票的假定下進(jìn)行的，未來(lái)將進(jìn)一步考慮存在特權(quán)選民的投票場(chǎng)景.