基于區(qū)塊鏈的可追蹤匿名電子投票方案

孫萌　王昀飚

摘? ?要：電子投票在為人們提供便利并得到廣泛應(yīng)用的同時(shí)，也存在著數(shù)據(jù)隱私泄露等安全性問(wèn)題。文章提出了一種基于區(qū)塊鏈的可追蹤匿名電子投票方案，實(shí)現(xiàn)了匿名性、可追蹤性、公平性以及普遍可驗(yàn)證性。方案通過(guò)使用K次匿名認(rèn)證協(xié)議，不僅保護(hù)了正常投票人的身份隱私，還能揭露多次投票的惡意投票人身份。采用基于時(shí)間釋放的加密方法，可以保證任何人都不會(huì)在投票結(jié)束前知道實(shí)時(shí)的投票情況。此外，利用區(qū)塊鏈技術(shù)可以保證選票時(shí)不被篡改，并且任何人都能在不依賴可信計(jì)票中心的情況下對(duì)選票進(jìn)行驗(yàn)證。最后，實(shí)驗(yàn)結(jié)果和安全性分析表明了方案是安全可行的。

關(guān)鍵詞：電子投票;區(qū)塊鏈;匿名性;可追蹤性

中圖分類號(hào)：TP309? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： While electronic voting provides convenience for people and is widely used， there are also security problems such as data privacy disclosure. This paper proposed a traceable anonymous electronic voting scheme based on blockchain， which realizes anonymity， traceability， fairness and universal verifiability. By using k-times anonymous authentication protocol， the scheme not only protects the privacy of normal voter identity， but also reveals the identity of the malicious voter who has voted multiple times; Using a time-released encryption method， it can guarantee that no one will know the real-time voting situation before the end of the voting; In addition， the use of blockchain technology can ensure that the vote will not be tampered with， and anyone can verify the votes without relying on a trusted counting center. Finally， experimental results and security analysis show that the scheme is safe and feasible.

Key words： electronic voting; blockchain; anonymity; traceability

1 引言

傳統(tǒng)的紙質(zhì)投票由于計(jì)票成本和不易保存等問(wèn)題發(fā)展受到限制，與傳統(tǒng)的投票相比，電子投票具有不受時(shí)間和空間的限制、投票和計(jì)票過(guò)程簡(jiǎn)單、成本低的優(yōu)勢(shì)，但是同時(shí)投票過(guò)程中也存在隱私數(shù)據(jù)泄露和投票造假的問(wèn)題。密碼學(xué)為電子投票提供了安全的解決辦法[1]，包括使用盲簽名[2]、同態(tài)加密[3]和混合網(wǎng)絡(luò)等技術(shù)[4]構(gòu)造電子投票方案。但是傳統(tǒng)的電子投票往往存在需要可信機(jī)構(gòu)的問(wèn)題，如需要計(jì)票機(jī)構(gòu)統(tǒng)計(jì)投票并公布結(jié)果，需要認(rèn)證機(jī)構(gòu)保護(hù)投票人身份隱私。由于網(wǎng)絡(luò)環(huán)境的復(fù)雜性，選票內(nèi)容容易遭到破壞，投票安全不能得到保證。

區(qū)塊鏈作為比特幣[5]的底層技術(shù)，隨著比特幣的流行而受到廣泛關(guān)注，并逐漸在保證數(shù)據(jù)的安全和可信等方面發(fā)揮著重要作用。通過(guò)將區(qū)塊鏈技術(shù)應(yīng)用到電子投票中[6]，利用其具有不可篡改的功能，可以保護(hù)選票數(shù)據(jù)不被篡改與刪除。此外，區(qū)塊鏈作為一個(gè)公開(kāi)透明的公共賬本，為電子投票提供了一個(gè)可信任的存儲(chǔ)平臺(tái)，使得任何人可以在不依賴可信機(jī)構(gòu)的情況下對(duì)投票進(jìn)行驗(yàn)證。目前，基于區(qū)塊鏈的電子投票方案雖然在一定程度上滿足了選票的完整性和可驗(yàn)證性[7，8]，但是仍存在依賴區(qū)塊鏈平臺(tái)保護(hù)投票人身份隱私以及計(jì)票效率有待提高等問(wèn)題。

本文通過(guò)結(jié)合K次匿名認(rèn)證協(xié)議和基于時(shí)間釋放的加密方法，充分利用了區(qū)塊鏈的不可篡改和公開(kāi)透明等特點(diǎn)，提出了一種可追蹤的匿名電子投票方案。該方案滿足了電子投票的基本安全性需求，可以在不依賴可信計(jì)票中心的情況下對(duì)選票進(jìn)行驗(yàn)證，還能夠在保護(hù)正常投票人身份隱私的同時(shí)追蹤惡意投票人。

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

2.1 K 次匿名認(rèn)證

Nguyen等人[9]基于雙線性映射 提出了一種K次匿名認(rèn)證協(xié)議（k-Times Anonymous Authentication），該協(xié)議可以在不泄露合法用戶身份隱私的同時(shí)，對(duì)惡意用戶進(jìn)行追蹤。服務(wù)提供者為用戶提供有限次（k次）服務(wù)的匿名使用權(quán)，用戶在限制次數(shù)內(nèi)使用服務(wù)時(shí)，他的身份將不會(huì)泄露給包括認(rèn)證機(jī)構(gòu)在內(nèi)的任何人。但是只要用戶使用服務(wù)的次數(shù)超過(guò)限制時(shí)，他的身份將被追蹤并公布。K次匿名認(rèn)證協(xié)議可以用在電子現(xiàn)金和電子投票等場(chǎng)景，以保證合法用戶的匿名并追蹤惡意用戶。該協(xié)議主要包含七種算法。

（1）群管理員初始化算法：群管理員輸入安全參數(shù)，輸出群管理員公私鑰對(duì)，生成一個(gè)用戶身份信息表。

（2）服務(wù)提供者初始化算法：服務(wù)提供者輸入身份、訪問(wèn)限制次數(shù)，輸出公共信息，包括用戶認(rèn)證記錄和個(gè)訪問(wèn)標(biāo)簽。

（3）注冊(cè)算法：輸入用戶身份和群管理員公私鑰對(duì)，輸出用戶公私鑰對(duì)，并記錄到身份信息表中。

（4）創(chuàng)建標(biāo)識(shí)算法：輸入服務(wù)提供者公共信息、隨機(jī)數(shù)、用戶私鑰以及群管理員公鑰，輸出標(biāo)識(shí)。

（5）創(chuàng)建零知識(shí)證明算法：用戶輸入群管理員公鑰、服務(wù)提供者公共信息、隨機(jī)數(shù) 以及用戶公私鑰對(duì)，輸出零知識(shí)證明。

（6）認(rèn)證算法：服務(wù)提供者輸入公共信息、零知識(shí)證明、標(biāo)識(shí)以及隨機(jī)數(shù)，輸出認(rèn)證通過(guò)或認(rèn)證失敗，并記錄到用戶認(rèn)證記錄中。

（7）追蹤算法：輸入服務(wù)提供者身份、公共信息以及身份信息表，輸出沒(méi)有惡意用戶、惡意用戶身份以及群管理員有不誠(chéng)實(shí)行為 三種情況之一。

2.2 基于時(shí)間釋放的加密方法

Cathalo等人[11]改進(jìn)了Blake的方案[12]，構(gòu)造了一種基于時(shí)間釋放的加密方法（Time-Release Encryption，TRE），該方法使得加密消息只有在規(guī)定時(shí)間T才能被解密，時(shí)間T之前不能被解密。消息發(fā)送者加密消息并發(fā)送，到達(dá)規(guī)定時(shí)間T時(shí)，消息接收者才能獲得時(shí)間服務(wù)器發(fā)送的特定時(shí)間陷門(mén)，并且使用密鑰解密密文恢復(fù)消息。在規(guī)定時(shí)間T之前，接收者不能從時(shí)間服務(wù)器獲得時(shí)間陷門(mén)，因而不能解密。該方法可以用在電子拍賣和電子彩票等現(xiàn)實(shí)場(chǎng)景，以保護(hù)敏感數(shù)據(jù)的隱私。時(shí)間釋放加密由五個(gè)算法組成。

（1）初始化算法：時(shí)間服務(wù)器輸入安全參數(shù)，輸出時(shí)間服務(wù)器公私鑰對(duì) 和公共參數(shù)。

（2）用戶密鑰生成算法：用戶輸入公共參數(shù)，輸出用戶公私鑰對(duì)。

（3）時(shí)間陷門(mén)釋放算法：時(shí)間服務(wù)器輸入私鑰和規(guī)定的時(shí)間T，輸出對(duì)應(yīng)的時(shí)間陷門(mén)。

（4）加密算法：消息發(fā)送者輸入公共參數(shù)、消息接收者公鑰以及只能在規(guī)定時(shí)間T解密的消息m，輸出密文。

（5）解密算法：消息接收者輸入密文、公共參數(shù)、消息接收者私鑰以及特定時(shí)間陷門(mén)，輸出消息明文m。

3 可追蹤的匿名電子投票方案

3.1 系統(tǒng)模型

系統(tǒng)模型如圖1所示，包括四個(gè)實(shí)體：管理員、發(fā)起人、投票人和時(shí)間服務(wù)器。管理員負(fù)責(zé)認(rèn)證投票人身份，并且管理一個(gè)記錄合法投票人身份的身份信息表。發(fā)起人負(fù)責(zé)將投票活動(dòng)相關(guān)信息寫(xiě)入智能合約并部署到區(qū)塊鏈上公開(kāi)，發(fā)起投票活動(dòng)。投票人從智能合約中獲得投票活動(dòng)相關(guān)信息，生成選票密文和選票標(biāo)識(shí)合法性、投票人身份合法性的零知識(shí)證明，使用一次性以太坊賬戶向智能合約發(fā)送交易完成投票。時(shí)間服務(wù)器負(fù)責(zé)生成用于解密選票的時(shí)間陷門(mén)，并在特定時(shí)間進(jìn)行廣播。

投票人在管理員處認(rèn)證，發(fā)起人發(fā)布投票活動(dòng)到區(qū)塊鏈上，投票人根據(jù)智能合約中的投票活動(dòng)相關(guān)信息進(jìn)行投票。到達(dá)活動(dòng)截止時(shí)間時(shí)，任何想要知道投票結(jié)果的實(shí)體，根據(jù)智能合約中的投票記錄進(jìn)行合法性驗(yàn)證，并在解密時(shí)間接收時(shí)間服務(wù)器廣播的時(shí)間陷門(mén)解密選票以及統(tǒng)計(jì)投票結(jié)果。

3.2 方案介紹

方案由初始化、投票人注冊(cè)、發(fā)起投票、投票、統(tǒng)計(jì)投票和追蹤惡意用戶六個(gè)階段組成。

3.2.1 初始化階段

管理員、發(fā)起人和時(shí)間服務(wù)器分別進(jìn)行初始化操作，生成各自的公私鑰對(duì)。產(chǎn)生一個(gè)雙線性映射，其中和是p循環(huán)群， g是G的生成元。哈希函數(shù)，，，明文空間和密文空間，其中。

（1）管理員選擇，計(jì)算，輸出公私鑰對(duì)，其中公鑰，私鑰。同時(shí)創(chuàng)建一個(gè)投票人身份信息表，本階段將其初始化為空表。

（2）發(fā)起人選擇，計(jì)算，生成公私鑰對(duì)，其中公鑰，私鑰。

（3）時(shí)間服務(wù)器選擇隨機(jī)數(shù)，計(jì)算，輸出公私鑰對(duì)。

3.2.2 投票人注冊(cè)階段

投票人向管理員注冊(cè)后獲得自身公私鑰對(duì)，成為合法投票人參與投票。在開(kāi)始注冊(cè)前，管理員首先設(shè)置投票人注冊(cè)截止時(shí)間。

（1）投票人選擇隨機(jī)數(shù)，計(jì)算發(fā)送給管理員。

（2）管理員選擇隨機(jī)數(shù)發(fā)送給投票人。

（3）投票人計(jì)算，和，并將身份信息加入身份信息表，其中i是投票人身份。然后將，和零知識(shí)證明發(fā)送給管理員。

（4）管理員首先確認(rèn)在身份信息表中，且投票人身份信息i滿足注冊(cè)要求;檢查和等式的正確性;驗(yàn)證的正確性;所有條件驗(yàn)證通過(guò)后，管理員選擇隨機(jī)數(shù)，計(jì)算，將發(fā)送給投票人。

（5）投票人檢查等式是否成立，成立則接受公私鑰對(duì)，其中公鑰，私鑰。至此，投票人獲得合法投票資格。

（6）到達(dá)投票人注冊(cè)截止時(shí)間時(shí)，注冊(cè)結(jié)束，管理員將注冊(cè)成功的投票人身份信息表寫(xiě)入智能合約并在區(qū)塊鏈上公開(kāi)。

其中，用來(lái)證明投票人提供的x滿足，零知識(shí)證明過(guò)程為：投票人計(jì)算發(fā)送給管理員，其中，，;管理員計(jì)算，驗(yàn)證等式是否成立，成立則驗(yàn)證通過(guò)。

3.2.3 發(fā)起投票階段

發(fā)起人將投票活動(dòng)的相關(guān)信息寫(xiě)入智能合約并部署到區(qū)塊鏈上公開(kāi)，發(fā)起投票。投票活動(dòng)相關(guān)信息包括：投票問(wèn)題與候選項(xiàng)、時(shí)間服務(wù)器公鑰、投票記錄表、發(fā)起人公私鑰對(duì)、投票截止時(shí)間、統(tǒng)計(jì)投票時(shí)間和標(biāo)簽。

其中，投票記錄表由發(fā)起人管理，記錄并公開(kāi)投票人的投票記錄。發(fā)起人私鑰在此階段初始化為空值，統(tǒng)計(jì)投票階段再賦值。另外，標(biāo)簽由發(fā)起人計(jì)算，，是發(fā)起人的身份，數(shù)字1是允許投票人投票的次數(shù)，本方案中投票人只能進(jìn)行一次合法的投票。

3.2.4 投票階段

投票人從發(fā)起人編寫(xiě)的智能合約中獲得投票問(wèn)題與候選項(xiàng)等信息，利用其中的標(biāo)簽生成選票標(biāo)識(shí)，將選票標(biāo)識(shí)合法性、投票人身份合法性的零知識(shí)證明同選票密文一起，以交易的形式發(fā)送給智能合約進(jìn)行投票。

（1）發(fā)起人選擇隨機(jī)數(shù)，發(fā)送給投票人。

（2）投票人查找到智能合約中的標(biāo)簽，計(jì)算選票標(biāo)識(shí)，并生成零知識(shí)證明。

（3）投票人讀取智能合約中的發(fā)起人公鑰，想要投票的選項(xiàng)m和統(tǒng)計(jì)投票時(shí)間。選擇隨機(jī)數(shù)，設(shè)置選票的解密時(shí)間為，計(jì)算選票密文將選票密文和零知識(shí)證明等信息的集合以交易的形式發(fā)送到智能合約的投票記錄表中記錄。

（4）智能合約對(duì)于接收到的每一個(gè)選票，檢查投票記錄表中是否存在該選票包含的，如果不存在則接收該選票，存在則拒絕選票。

其中，用于證明選票標(biāo)識(shí)合法性和投票人身份合法性，即證明投票人注冊(cè)成功具有投票資格，并且選票標(biāo)識(shí)計(jì)算過(guò)程正確。，的證明使用與類似的離散對(duì)數(shù)零知識(shí)證明，等式的零知識(shí)證明過(guò)程為：

3.2.5 統(tǒng)計(jì)投票階段

投票結(jié)束后，發(fā)起人對(duì)投票記錄表中的選票進(jìn)行篩選與標(biāo)記，統(tǒng)計(jì)投票結(jié)果。到達(dá)投票截止時(shí)間時(shí)，發(fā)起人向智能合約發(fā)送消息通知，并在智能合約中公布發(fā)起人私鑰，智能合約停止接收投票人發(fā)送的選票，沒(méi)有投票的用戶視為棄權(quán)。

（1）發(fā)起人驗(yàn)證智能合約接收到的所有選票的合法性。對(duì)每個(gè)選票的，首先驗(yàn)證的正確性，驗(yàn)證通過(guò)再計(jì)算，然后計(jì)算選票的解密時(shí)間，驗(yàn)證T是否與統(tǒng)計(jì)投票時(shí)間相同。驗(yàn)證不通過(guò)則為非法選票，發(fā)起人在投票記錄表中標(biāo)記該選票為“非法選票”。接下來(lái)檢查任意兩個(gè)通過(guò)驗(yàn)證的選票的和是否出現(xiàn)的情況，出現(xiàn)則說(shuō)明有投票人重復(fù)投票，發(fā)起人將投票記錄表中對(duì)應(yīng)的選票標(biāo)記為“重復(fù)選票”，然后標(biāo)記所有剩余選票為“合法選票”。

（2）發(fā)起人統(tǒng)計(jì)合法選票的投票結(jié)果。首先，匯總投票記錄表中所有具有“合法選票”標(biāo)記的選票，到達(dá)時(shí)，接收時(shí)間服務(wù)器廣播的時(shí)間陷門(mén)。然后，計(jì)算，進(jìn)而得到選票，最后統(tǒng)計(jì)投票結(jié)果。

任何對(duì)投票結(jié)果有異議的實(shí)體都可以驗(yàn)證選票合法性以及統(tǒng)計(jì)投票結(jié)果，但只有發(fā)起人才能標(biāo)記選票。

3.2.6 追蹤惡意用戶階段

任何實(shí)體都可以對(duì)投票記錄表中的重復(fù)選票進(jìn)行追蹤，揭露重復(fù)投票的惡意用戶身份。對(duì)于出現(xiàn)情況的兩張選票，計(jì)算，然后在身份信息表中查找惡意投票人的身份 。

4 安全性分析

本節(jié)對(duì)本文提出的電子投票方案的安全性進(jìn)行分析。

（1）匿名性。投票人使用一次性以太坊賬戶投票，且選票內(nèi)容只含有證明投票人合法身份的零知識(shí)證明，不包含投票人身份。由零知識(shí)證明的性質(zhì)可知，證明過(guò)程不會(huì)泄露投票人身份。另外，使用K次匿名認(rèn)證協(xié)議，保證方案的匿名性。

（2）可追蹤性。投票人進(jìn)行重復(fù)投票時(shí)，發(fā)起人會(huì)標(biāo)記這些重復(fù)的選票為“重復(fù)選票”。任何人都可以對(duì)這些選票進(jìn)行計(jì)算，然后在身份信息表中查找惡意投票人的身份，如果找不到則說(shuō)明管理員有不誠(chéng)實(shí)的行為。

（3）普遍可驗(yàn)證性。智能合約中的投票記錄是公開(kāi)透明的，任何人都可以查看選票并通過(guò)零知識(shí)證明驗(yàn)證選票標(biāo)識(shí)計(jì)算的正確性和投票人身份的合法性。另外，任何人都能利用時(shí)間陷門(mén)解密選票，并對(duì)投票結(jié)果進(jìn)行統(tǒng)計(jì)驗(yàn)證。

（4）公平性。使用時(shí)間釋放加密方法，在到達(dá)統(tǒng)計(jì)投票時(shí)間之前，任何實(shí)體都無(wú)法獲得時(shí)間陷門(mén)以解密選票內(nèi)容。此外，比較選票解密時(shí)間與統(tǒng)計(jì)投票時(shí)間是否相同，不同則將選票視為非法選票，不計(jì)入投票結(jié)果，滿足了公平性。

（5）完整性。由于區(qū)塊鏈具有不可篡改的特性，在所有選票發(fā)送到智能合約后，任何人都不能修改和刪除，保證了方案的完整性。

5 實(shí)驗(yàn)與分析

本文根據(jù)所提出的電子投票方案，實(shí)現(xiàn)了一個(gè)基于Ethereum區(qū)塊鏈平臺(tái)的電子投票系統(tǒng)，并在以太坊本地網(wǎng)絡(luò)中對(duì)系統(tǒng)進(jìn)行測(cè)試。為了驗(yàn)證投票方案的正確性與可用性，對(duì)核心算法運(yùn)行所需要的平均時(shí)間進(jìn)行統(tǒng)計(jì)，如表1所示。

智能合約中相關(guān)方法的Gas消耗如表2所示，其中投票人數(shù)為n，選票數(shù)為m。實(shí)驗(yàn)證明，測(cè)試過(guò)程中的所有步驟都沒(méi)有超過(guò)以太坊單筆交易的最大Gas限制，可以正常部署運(yùn)行在以太坊主鏈上。

為了驗(yàn)證方案的實(shí)用性，對(duì)不同規(guī)模、不同候選項(xiàng)的投票場(chǎng)景下計(jì)票所需時(shí)間進(jìn)行統(tǒng)計(jì)，如圖2所示。實(shí)驗(yàn)證明了統(tǒng)計(jì)選票的時(shí)間與投票規(guī)模基本呈線性相關(guān)。在較小的規(guī)模投票中，候選項(xiàng)數(shù)目對(duì)統(tǒng)計(jì)選票時(shí)間無(wú)較大影響，基本滿足現(xiàn)實(shí)中投票場(chǎng)景的需求。

6 結(jié)束語(yǔ)

根據(jù)電子投票的發(fā)展現(xiàn)狀，本文基于區(qū)塊鏈技術(shù)，結(jié)合K次匿名認(rèn)證和時(shí)間釋放加密方法，提出了一種可追蹤匿名電子投票方案。不僅保證了電子投票的基本安全性需求，還實(shí)現(xiàn)了普遍可驗(yàn)證性和可追蹤性。通過(guò)分析實(shí)驗(yàn)中核心算法的時(shí)間開(kāi)銷與Gas消耗證明了方案的正確性;通過(guò)分析不同規(guī)模選票的統(tǒng)計(jì)時(shí)間開(kāi)銷證明了方案的實(shí)用性。方案可以應(yīng)用到真實(shí)投票場(chǎng)景中，很好地保護(hù)了用戶的隱私，保證了電子投票的安全性。

參考文獻(xiàn)

[1] Schneier B. Applied Cryptography： protocols， algorithms， and source code in C[M]. 北京： 機(jī)械工業(yè)出版社， 2000.

[2] Ibrahim S， Kamat M， Salleh M， et al. Secure E-voting with blind signature[C]//4th National Conference of Telecommunication Technology， 2003. NCTT 2003 Proceedings. IEEE， 2003： 193-197.

[3] Peng K， Bao F. Efficient multiplicative homomorphic e-voting[C]//International Conference on Information Security. Springer， Berlin， Heidelberg， 2010： 381-393.

[4] Furukawa J， Mori K， Sako K. An implementation of a mix-net based network voting scheme and its use in a private organization[M]//Towards trustworthy elections. Springer， Berlin， Heidelberg， 2010： 141-154.

[5] Nakamoto S. Bitcoin： A peer-to-peer electronic cash system[J]. 2008.

[6] Hjalmarsson F P， Hreioarsson G K， Hamdaqa M， et al. Blockchain-Based E-Voting System[C]. 2018 IEEE 11th International Conference on Cloud Computing （CLOUD）. IEEE， 2018： 983-986.

[7] Aradhya P. The Online Voting Platform of The Future [EB/OL]. https：//followmyvote.com.

[8] Wire B. Now you can vote online with a selfie [EB/OL]. http：//www.businesswire.com/news/home/20161017005354/en/Vote-Online-Selfie.

[9] Nguyen L， Safavi-Naini R. Dynamic k-times anonymous authentication[C]. International Conference on Applied Cryptography and Network Security. Springer， Berlin， Heidelberg， 2005： 318-333.

[10] Boneh D， Franklin M. Identity-based encryption from the Weil pairing[J]. SIAM journal on computing， 2003， 32（3）： 586-615.

[11] Cathalo J， Libert B， Quisquater J J. Efficient and non-interactive timed-release encryption[C]. International Conference on Information and Communications Security. Springer， Berlin， Heidelberg， 2005： 291-303.

[12] Blake I F， Chan A C F. Scalable， Server-Passive， User-Anonymous Timed Release Public Key Encryption from Bilinear Pairing[J]. IACR Cryptology ePrint Archive， 2004， 2004： 211.

作者簡(jiǎn)介：

孫萌（1996-），女，漢族，山東煙臺(tái)人，暨南大學(xué)，碩士;主要研究方向和關(guān)注領(lǐng)域：信息安全。

王昀飚（1994-），男，漢族，廣東深圳人，暨南大學(xué)，碩士;主要研究方向和關(guān)注領(lǐng)域：信息安全。