范洪博 謝華材 張晶

摘 要：電子投票應(yīng)用范圍極廣，其安全性、可信性和公平性具有重要的研究與應(yīng)用價值。在傳統(tǒng)的基于可驗證秘密共享（VSS）等技術(shù)基礎(chǔ)上，提出一種可信電子投票方法，將安全多方計算協(xié)議應(yīng)用于投票和計票。該投票系統(tǒng)具備可驗證性與無收據(jù)性，在存在不誠實投票者和計票機(jī)構(gòu)的前提下，保障投票安全、可信完成。同時，在現(xiàn)有電子投票系統(tǒng)中，廣泛依賴可信第三方完成注冊認(rèn)證階段，注冊中心若不誠實將導(dǎo)致投票失敗。通過將區(qū)塊鏈技術(shù)與電子投票技術(shù)相結(jié)合，利用MIT的Enigma區(qū)塊鏈項目相關(guān)技術(shù)，取消了認(rèn)證注冊中心，剝離了電子投票對可信第三方的依賴，并對投票者和候選者的隱私起到保護(hù)作用。

關(guān)鍵詞：電子投票；VSS協(xié)議；區(qū)塊鏈；可驗證；無收據(jù)性

DOI：10.11907/rjdk.172473

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）005-0034-06

Abstract：Electronic voting has a wide range of application， and its safety， credibility and fairness are attatched with great research and practical significance. Based on the traditional technologies including verifiable secret sharing（VSS）， this paper proposes a credible electronic voting method， which applies the security multi-party computing protocol to voting and counting. The voting system is verifiable and of non-receipt premised on the presence of dishonest voters and counting agencies to ensure the smooth completion of credible voting. Meanwhile the existing electronic voting system has extensive reliance on trusted third parties to complete registration certification， and any cheating from the registration center will lead to the failure of voting. In this paper， the combination of block-chain technology and electronic voting technology ， together with MIT Enigma block chain project-related technology are employed to cancel the certification canter and strip electronic voting off the trusted third parties. Therefore the privacy of voters and candidates is protected.

Key Words：electronic voting； VSS protocol； block chain； verifiability； receipt-freeness

0 引言

投票是獲得民眾共識的基本方法，是民主發(fā)展、社會協(xié)作的基礎(chǔ)。電子投票（E-voting）自1981年被提出以來，以其計票快捷準(zhǔn)確、人力開支較低、投票簡單易用、安全抗攻擊、信息實時公開透明等特點(diǎn)，已在較大程度上取代了傳統(tǒng)投票，應(yīng)用范圍極廣。

電子投票過程包括：由投票發(fā)起者發(fā)起投票，由投票認(rèn)證注冊中心完成選票的發(fā)放與甄別工作，被發(fā)放選票的投票人進(jìn)行投票，投票完成后，由計票中心完成選票的統(tǒng)計和結(jié)果公示工作。

因投票結(jié)果常影響個人利益，電子投票參與者可能因被冒認(rèn)、被脅迫、被賄賂、存在內(nèi)鬼等問題而變得不誠實，這些不誠實的參與者可能對投票數(shù)據(jù)進(jìn)行篡改、偽造、重放、抵賴等，從而影響投票結(jié)果的正確性。特別是由于第三方可能存在內(nèi)鬼，使其可信程度難以得到保障。因投票發(fā)起者必然希望獲得正確的投票結(jié)果，否則將失去投票意義，在整個投票系統(tǒng)中，只有投票發(fā)起者在發(fā)起投票時是可信誠實的。

在存在惡意參與者的前提下，若投票方案滿足下列性質(zhì)，也可保障投票的正確性，并稱其為安全的[1]：

（1）完備性：各合法選票均被正確統(tǒng)計。

（2）健壯性：可抵抗惡意參與者的非法行為。

（3）隱私性：選票通過加密后，除投票者外的任意第三方無法獲知選票內(nèi)容，且無法通過選票推斷投票者個人信息，也稱為匿名性。

（4）不可重復(fù)性：不可一票多投。

（5）合法性：無投票資格者不能參與投票。

（6）公平性：計票結(jié)束前，無人能提前知曉投票結(jié)果，也不能利用推斷的中間結(jié)果影響后續(xù)投票過程。

（7）可驗證性：任意投票人可檢驗選票是否被正確計入。若任意第三方（包含未參加投票的人）都可對選票進(jìn)行檢驗，則稱為廣泛可驗證性。

（8）無收據(jù)性：任何人無法向他人提供自身投票證據(jù)，證明自己是按照某種給定投票方案進(jìn)行投票的。

現(xiàn)有電子投票研究方案中，均基于投票認(rèn)證注冊中心是可信第三方的假設(shè)，然而在實際投票過程中，該假設(shè)多不成立，目前尚未見認(rèn)證注冊中心不誠實的相關(guān)研究。在計票中心不誠實的問題方面，現(xiàn)有研究多基于半誠實假設(shè)[2]。半誠實假設(shè)下，不誠實的計票中心可通過各計票中心之間的交叉驗證而被發(fā)現(xiàn)，從而保障計票正確。而投票人的誠實性主要通過無收據(jù)性加以保障，若電子投票能滿足無收據(jù)性，被賄選人無法證明其自身投票符合賄選人需求，從而減少賄賂發(fā)生，使投票更加公正。

本文通過引入?yún)^(qū)塊鏈[3]技術(shù)，實現(xiàn)了注冊認(rèn)證中心的去中心化，剝離了電子投票對可信第三方的依賴，并對投票者和候選者的隱私起到保護(hù)作用。同時，項目基于可驗證秘密共享[4]（VSS）等技術(shù)提供了一種電子投票系統(tǒng)方案，該方案可有效保障電子投票的安全性。

1 國內(nèi)外研究現(xiàn)狀

電子投票已成為目前的研究熱點(diǎn)之一，大量學(xué)者圍繞電子投票的安全問題進(jìn)行了研究。1992年，A Fujioka等[1]使用盲簽名技術(shù)提出著名的FOO電子投票協(xié)議，該協(xié)議真正實現(xiàn)了大規(guī)模選舉投票的安全性和靈活性，為電子投票協(xié)議的實際應(yīng)用提供了理論基礎(chǔ)；文獻(xiàn)[5]中，E Magkos等提出一種基于匿名信道的大規(guī)模投票方案，該方案滿足了電子投票協(xié)議的基本要求，基于PKI技術(shù)有效解決了投票者的隱私保護(hù)問題；2006年，S Canard等[6]發(fā)現(xiàn)惡意的mix server能對電子投票系統(tǒng)進(jìn)行兩種攻擊，從而直接改變投票結(jié)果，因此提出一種基于門限的公平盲簽名技術(shù)和兩個基于門限的MIX-NET方案，以防止惡意的mix server攻擊。該項目被用于歐洲憲法會議的電子投票選舉，但該方案中使用的MIX-NET在半誠實模型下不是廣泛可驗證的。因此，該方案不具有廣泛可驗證性；2006年，仲紅等[7]提出基于安全多方求和的多選多方案，該方案應(yīng)用安全多方求和保護(hù)選票的匿名性，但對于每個選民發(fā)出秘密隨機(jī)數(shù)的合法性需要進(jìn)一步證明，且其除獲勝者外的其他人選票數(shù)也要公開，無法保障落選者選票的隱私性；2013年，X Yi和E Okamoto[8]提出基于同態(tài)加密的面向選民的通信信道電子協(xié)議，但該協(xié)議執(zhí)行過程全部公開，無法保證投票者的隱私性。

在無收據(jù)性方面，1994年Benaloh[9]提出無收據(jù)性概念?，F(xiàn)有投票方案中實現(xiàn)無收據(jù)性的方式大致分為3種：利用MIX-NET協(xié)議的、基于盲簽名的，以及基于同態(tài)加密的。在基于MIX-NET的協(xié)議中，高虎明[10]提出一個可驗證的MIX-NET協(xié)議，以滿足電子投票方案的無收據(jù)性。但是該方案處理計票時計算量較大，且需要假設(shè)前提為注冊中心是完全可信的；F Song[11]給出一種利用盲簽名技術(shù)實現(xiàn)電子投票方案的無收據(jù)性，該方案由于投票者的盲化因子可用作選票依據(jù)，因此不能滿足完全無收據(jù)性；A Huszti[12]給出一種在同態(tài)模式下將投票者加密的選票發(fā)送給可信第三方計票機(jī)構(gòu)，利用計票機(jī)構(gòu)保密選票結(jié)果實現(xiàn)方案的無收據(jù)性，但因第三方計票機(jī)構(gòu)是否可信難以保障，此方案仍存在安全問題。

區(qū)塊鏈技術(shù)是目前網(wǎng)絡(luò)安全、金融科技領(lǐng)域的研究熱點(diǎn)之一。其是一種點(diǎn)對點(diǎn)去中心化數(shù)據(jù)共享技術(shù)，其存儲的數(shù)據(jù)無需依賴可信第三方，即具有不可篡改、偽造、抵賴、冒認(rèn)、重放等性質(zhì)，從而有效保障數(shù)據(jù)安全，節(jié)點(diǎn)間可自動形成信用關(guān)系。截至目前，區(qū)塊鏈技術(shù)已成功保護(hù)了如比特幣等超過1 000億美元的數(shù)字資產(chǎn)安全，其安全性得到了充分的驗證。若能有效利用區(qū)塊鏈技術(shù)，將可能無需依賴可信第三方完成安全認(rèn)證。

Enigma是一個由MIT主導(dǎo)的基于區(qū)塊鏈的端到端（end-to-end）分散的計算平臺，使用安全多方計算（SMPC），數(shù)據(jù)在不同節(jié)點(diǎn)之間進(jìn)行分割計算，不會將信息泄漏給其它節(jié)點(diǎn)，沒有單方節(jié)點(diǎn)可以全面訪問數(shù)據(jù)，從而保護(hù)了隱私。計算過程和數(shù)據(jù)存儲不能被每個節(jié)點(diǎn)復(fù)制到網(wǎng)絡(luò)節(jié)點(diǎn)中，只有一個小的子集在數(shù)據(jù)不同部分執(zhí)行每個計算，存儲和計算中減少的冗余可實現(xiàn)更嚴(yán)格的計算[13]。

本文采用Enigma區(qū)塊鏈技術(shù)作為本投票系統(tǒng)的注冊認(rèn)證基礎(chǔ)，從而實現(xiàn)了認(rèn)證注冊階段無需可信第三方，只需保障本系統(tǒng)參與者滿足半誠實假設(shè)，即可有效實現(xiàn)安全電子投票功能。

2 方案建立

2.1 方案假設(shè)與方案組成

（3）在一次完整的投票過程中，公告板上的數(shù)據(jù)只能添加，不能刪除。

（4）條目所有人可對其發(fā)布條目進(jìn)行修改，修改方法為將修改的條目聲明作廢，并提交新條目。其他用戶檢查條目簽名，若簽名無法對應(yīng)，則否認(rèn)公告板上的修改。

（5）第三方在接收條目時，統(tǒng)計條目序列號，對序列號重復(fù)的條目進(jìn)行否認(rèn)，減少重放攻擊的發(fā)生。

（6）所有提交到公告板上的數(shù)據(jù)，同時提交簽名到區(qū)塊鏈指定地址，本系統(tǒng)為所有參與者生成混合區(qū)塊鏈身份addrp，條目提交者pi利用bxi對應(yīng)的區(qū)塊鏈地址addrpi，向addrp發(fā)送附言為Sigbyi的任意交易，實現(xiàn)條目發(fā)送的公證。第三方在獲取條目時，基于bxi檢查簽名Sigbyi的正確性，并查詢區(qū)塊鏈addrp地址中是否存在Sigbyi，若未在區(qū)塊鏈中查詢到該簽名，基于簽名發(fā)現(xiàn)數(shù)據(jù)被篡改，則否認(rèn)對應(yīng)條目。

（7）若檢查到addrp中存在某用戶對其條目的簽名，但公告板上未發(fā)現(xiàn)對應(yīng)簽名，說明公告板上條目被惡意刪除，則公告所有人當(dāng)前公告板不安全，由投票發(fā)起者提示各參與方更換公告板，并重新投票。

在該保護(hù)方法下，公告板數(shù)據(jù)可避免被惡意篡改、重放、刪除、偽造、抵賴，從而為投票數(shù)據(jù)的安全共享提供保障。

VSS安全共享協(xié)議基于Shamir秘密分享過程[15]實現(xiàn)安全投票，該方案基于門限密鑰進(jìn)行投票信息的安全分享與驗證。在半誠實假設(shè)下，對指定投票人的投票，計算秘密所需的子密鑰數(shù)門限值大于（α-2）/3，各串通計票中心在進(jìn)行計票之前，無法獲得超過門限值的子秘密，從而保障其無法提前獲得投票結(jié)果。

2.2.2 注冊認(rèn)證階段

與傳統(tǒng)投票方法不同的是，本方法中不采用認(rèn)證注冊中心，各參與者基于區(qū)塊鏈數(shù)據(jù)和DHT完成注冊認(rèn)證過程。

投票由投票發(fā)起人p0發(fā)起并規(guī)定每個pi的訪問策略，該訪問策略記錄于表POLICY中，將各參與者的身份混合，混合后的共享身份地址記為addrp，用L表示某區(qū)塊鏈的公共分類賬[16]。該公共分類賬具備OP_RETURN字段，可存儲一定附言信息，ACL表示用戶身份的訪問控制表。

在該方法中，由投票發(fā)起者發(fā)起投票并生成共享身份ShareID，ShareID中保存了各參與者的權(quán)限數(shù)據(jù)，ShareID被上傳至DHT網(wǎng)絡(luò)，并由區(qū)塊鏈存證保障ShareID的不可篡改性。ShareID被秘密分發(fā)給每個參與者。各參與者接收共享身份，并基于共享身份公開個人身份認(rèn)證信息CheckID至公告板上，任何參與者均可根據(jù)被驗證人的CheckID檢查被驗證人是否為合法投票人，從而完成去中心化的認(rèn)證注冊功能。在該認(rèn)證過程中，因數(shù)字簽名的廣泛使用而無法偽造、篡改和抵賴，使每次投票ShareID均不同而無法完成重放攻擊，基于區(qū)塊鏈自身的安全性可抵抗冒認(rèn)攻擊。

3 安全性分析

以下對所提出電子投票方案的安全性進(jìn)行分析：

（1）完備性。方案基于區(qū)塊鏈和公告板保障選票數(shù)據(jù)不會被惡意刪除、偽造、篡改，所有合法數(shù)據(jù)均正確執(zhí)行VSS安全投票協(xié)議。因VSS在半誠實假設(shè)下具備完備性，可有效保障所有合法選票被正確計入。

（2）健壯性。方案采用區(qū)塊鏈技術(shù)進(jìn)行注冊認(rèn)證，因惡意偽裝者無法攻破區(qū)塊鏈安全機(jī)制，無法提供被偽裝者的簽名，從而無法進(jìn)入投票過程。進(jìn)入投票過程的惡意用戶若進(jìn)行數(shù)據(jù)篡改等非法行為，將被基于區(qū)塊鏈保護(hù)的公告板和VSS協(xié)議發(fā)現(xiàn)，投票發(fā)起者可在ACL中否認(rèn)該投票人的投票權(quán)限，將該惡意用戶排除出投票過程，制止其對投票進(jìn)行破壞。

若惡意攻擊者通過其它方式獲得原投票人區(qū)塊鏈私鑰而偽裝進(jìn)入投票階段，進(jìn)行滿足攻擊者意愿的正確投票，這等價于獲得原投票人的銀行賬戶，原投票人將損失巨大。但在投票時，區(qū)塊鏈上會出現(xiàn)大量存證（原投票人發(fā)現(xiàn)自己賬戶出現(xiàn)大量不是由本人發(fā)出的交易），原投票人可及時發(fā)現(xiàn)，并舉報自身區(qū)塊鏈私鑰被泄漏（被泄漏者通過被泄漏私鑰簽名本賬戶已泄漏信息，實現(xiàn)可信舉報），投票發(fā)起者認(rèn)證該區(qū)塊鏈地址存在入侵，可將該區(qū)塊鏈地址對應(yīng)用戶排除出投票過程。

（3）隱私性。項目基于區(qū)塊鏈進(jìn)行身份隱藏，投票者區(qū)塊鏈地址和其個人信息無法建立對應(yīng)關(guān)系，從而保障投票者個人信息的隱私性。同時，在半誠實假設(shè)的VSS協(xié)議中，投票者pi采用秘密分享方案分享選票，在小于t個計票中心勾結(jié)下，pi的投票內(nèi)容是全隱私的。

（4）不可重復(fù)性。本方案中，在注冊認(rèn)證階段會為投票者產(chǎn)生一個對應(yīng)的唯一隨機(jī)數(shù)作為身份標(biāo)識碼，一旦隨機(jī)數(shù)出現(xiàn)重復(fù)計算，則可判定投票人是重復(fù)投票。并且投出的加密選票在公告板中會以時間順序保留最后一張，后來的重復(fù)選票將會覆蓋之前選票，使投票內(nèi)容在計票開始前可修改，且滿足選票的不可重復(fù)性。

（5）合法性。見健壯性，該性質(zhì)已滿足。

（6）公平性。VSS采用門限密鑰方案進(jìn)行秘密共享，在獲得足夠的子密鑰前，無法解密投票結(jié)果，因各誠實計票中心在進(jìn)行計票時才分享自己持有的子秘密，不誠實計票中心在計票前無法獲得足夠的子秘密，因而無法提前知曉投票結(jié)果。

（7）可驗證性。通過設(shè)置公告板，任何投票者可以在區(qū)塊鏈上跟蹤自己的選票是否被統(tǒng)計，計票中心發(fā)送簽名認(rèn)證，根據(jù)計票中心最終公布總票數(shù)的子份額，可以驗證其正確性。

（8）無收據(jù)性。在計票階段，投票人pi對OPj，k進(jìn)行分享，向計票中心Ai發(fā)送子秘密并對這些子秘密簽名。在協(xié)議沒有錯誤的前提下，協(xié)議攻擊者最多獲得t個pi分享的子秘密，根據(jù)Shamir秘密共享機(jī)制，這些子秘密無法恢復(fù)OPj，k，不誠實參與者無法讓投票者pi證明自己的選票即OPj，k （k=1，…，c）。在協(xié)議進(jìn)行過程中，可能有不誠實參與者的不誠實行為使某些投票者pi的意愿OPj，k在協(xié)議檢查步驟中被重構(gòu)。方案通過保證不誠實參與者的不誠實行為一定可以被發(fā)現(xiàn)，并在檢查步驟中找出不誠實參與者，以保證每個參與者的正確行為。

4 復(fù)雜度分析

以下對所提出電子投票方案的復(fù)雜性進(jìn)行分析，并與典型的電子投票方案進(jìn)行比較。用安全多方計算協(xié)議分享一個隨機(jī)數(shù)需要傳送的消息復(fù)雜度為O（a2logF），共執(zhí)行a次協(xié)議，消息復(fù)雜度為O（a3logF），產(chǎn)生l個隨機(jī)數(shù)。因此，在投票階段的消息復(fù)雜度為O（la3logF）。

本文提出方案與典型的電子投票方案對比如表1所示。

5 結(jié)語

本文利用區(qū)塊鏈技術(shù)，成功使電子投票中的注冊認(rèn)證中心去中心化，擺脫了現(xiàn)有電子投票系統(tǒng)需要依賴可信第三方的現(xiàn)狀，有效規(guī)避了注冊認(rèn)證中心不誠實對投票的影響。在該去中心化認(rèn)證注冊中心基礎(chǔ)上，通過可驗證秘密共享協(xié)議（VSS）實現(xiàn)了一種半誠實模型下的電子投票系統(tǒng)，可抵抗主動敵手攻擊，從而較好地保障了電子投票的安全性。

參考文獻(xiàn)：

[1] FUJIOKA A， OKAMOTO T， OHTA K. A practical secret voting scheme for large scale elections[J]. Proc Auscrypt92 Gold Coast Queensland Australia Dec，1992，718：244-251.

[2] BRICKELL J， SHMATIKOV V. Privacy-preserving graph algorithms in the semi-honest model[C].International Conference on the Theory and Application of Cryptology and Information Security， Chennai， India， DBLP，2015：236-252.

[3] 袁勇，王飛躍.區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望[J].自動化學(xué)報，2016，42（4）：481-494.

[4] GENNARO R， RABIN M O， RABIN T. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography[C].Seventeenth ACM Symposium on Principles of Distributed Computing. ACM， 1998：101-111.

[5] MAGKOS E， BURMESTER M， CHRISSIKOPOULOS V. Receipt-freeness in large-scale elections without untappable channels[C].IFIP Conference on Towards the E-Society： E-Commerce， E-Business， E-Government. Kluwer，2001：683-694.

[6] CANARD S， GAUD M， TRAORé J. Defeating malicious servers in a blind signatures based voting system[M].Financial Cryptography and Data Security. Springer Berlin Heidelberg，2006：148-153.

[7] 仲紅，黃劉生，羅永龍.基于安全多方求和的多候選人電子選舉方案[J].計算機(jī)研究與發(fā)展，2006，43（8）：1405-1410.

[8] YI X， OKAMOTO E. Practical internet voting system[J]. Journal of Network & Computer Applications，2013，36（1）：378-387.

[9] BENALOH J， TUINSTRA D. Receipt-free secret-ballot elections[J]. Proceedings of Symposium on Theory of Computing，1994：544-553.

[10] GAO H M， WANG J L， WANG Y M. Electronic voting scheme based on a new mix net[J]. Acta Electronica Sinica，2004，32（6）：1047-1049.

[11] SONG F， CUI Z. Electronic voting scheme about elgamal blind-signatures based on XML[J]. Procedia Engineering，2012，29：2721-2725.

[12] HUSZTI A. A homomorphic encryption-based secure electronic voting scheme[J]. Publicationes Mathematicae，2015，79（3）：479-496.

[13] ZYSKIND G， NATHAN O， PENTLAND A. Enigma： decentralized computation platform with guaranteed privacy[J]. Computer Science，2015.

[14] ZYSKIND G， NATHAN O， PENTLAND A. Decentralizing privacy： using blockchain to protect personal data[C].Security and Privacy Workshops，2015：180-184.

[15] CHUN-PONG LAI， CUNSHENG DING. Several generalizations of shamirs secret sharing scheme[J]. International Journal of Foundations of Computer Science，2004，15（2）：445-458.

[16] HEGADEKATTI K. Democracy 3.0： voting through the blockchain[J]. Social Science Electronic Publishing，2017.

[17] 劉高，劉憶寧，王東.一種可驗證的多候選人電子投票方案[J].計算機(jī)工程與科學(xué)，2015，37（9）：1667-1670.

[18] 楊婷婷，林昌露，劉憶寧，等.基于多方排序協(xié)議的安全電子投票方案[J].計算機(jī)系統(tǒng)應(yīng)用，2015，24（8）：25-32.

（責(zé)任編輯：黃 健）