一種基于區塊鏈技術的可信電子投票方法

范洪博 謝華材 張晶

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

關鍵詞：電子投票；VSS協議；區塊鏈；可驗證；無收據性

DOI：10.11907/rjdk.172473

中圖分類號：TP301

文獻標識碼：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 引言

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

電子投票過程包括：由投票發起者發起投票，由投票認證注冊中心完成選票的發放與甄別工作，被發放選票的投票人進行投票，投票完成后，由計票中心完成選票的統計和結果公示工作。

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

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

（1）完備性：各合法選票均被正確統計。

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

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

（4）不可重復性：不可一票多投。

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

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

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

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

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

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

1 國內外研究現狀

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

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

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

Enigma是一個由MIT主導的基于區塊鏈的端到端（end-to-end）分散的計算平臺，使用安全多方計算（SMPC），數據在不同節點之間進行分割計算，不會將信息泄漏給其它節點，沒有單方節點可以全面訪問數據，從而保護了隱私。計算過程和數據存儲不能被每個節點復制到網絡節點中，只有一個小的子集在數據不同部分執行每個計算，存儲和計算中減少的冗余可實現更嚴格的計算[13]。

本文采用Enigma區塊鏈技術作為本投票系統的注冊認證基礎，從而實現了認證注冊階段無需可信第三方，只需保障本系統參與者滿足半誠實假設，即可有效實現安全電子投票功能。

2 方案建立

2.1 方案假設與方案組成

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

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

（5）第三方在接收條目時，統計條目序列號，對序列號重復的條目進行否認，減少重放攻擊的發生。

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

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

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

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

2.2.2 注冊認證階段

與傳統投票方法不同的是，本方法中不采用認證注冊中心，各參與者基于區塊鏈數據和DHT完成注冊認證過程。

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

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

3 安全性分析

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

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

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

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

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

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

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

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

（7）可驗證性。通過設置公告板，任何投票者可以在區塊鏈上跟蹤自己的選票是否被統計，計票中心發送簽名認證，根據計票中心最終公布總票數的子份額，可以驗證其正確性。

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

4 復雜度分析

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

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

5 結語

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

參考文獻：

[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] 袁勇，王飛躍.區塊鏈技術發展現狀與展望[J].自動化學報，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].計算機研究與發展，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].計算機工程與科學，2015，37（9）：1667-1670.

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

（責任編輯：黃 健）