基于安全多方計算的多候選人電子投票方案①

李亞偉,王維瓊,謝 瓊

(長安大學 理學院,西安 710064)

電子投票是基于密碼學技術設計并通過網絡實現的一種投票方式.與傳統的唱票表決相比,電子投票的投票和計票過程更高效、選舉結果更準確.隨著互聯網與密碼學技術的發展,電子投票得到大力發展.近年來,電子投票系統在許多西方國家的選舉中得到應用,其中愛沙尼亞首先在國家層面的選舉使用電子投票.目前,美國、加拿大等地的議會和立法中已開始使用電子投票.我國部分領域也在嘗試使用電子投票,其中2005年上海市長寧區某街道進行團支部直選時首次在政治領域使用電子投票.

最早的電子投票方案可追溯到1981年,由 Chaum[1]基于混合網絡和RSA 公鑰加密體制提出.1992年,Fujilka 等人[2]基于盲簽名提出了可適用于大規模選舉的FOO 方案,使電子投票走向實用.1997年,Cramer等人[3]首次提出了多候選人的電子投票問題,并利用ElGamal 加密系統設計了一個多選一的電子選舉方案,該方案需要可信的計票中心參與接收并統計選票.2001年,Damg?rd 等人[4]基于Paillier 加密系統提出了一個多選多的電子投票方案,該方案無法避免重復投票現象且需要可信計票機構參與.2006年,仲紅等人[5]基于安全多方求和提出一個無需第三方計票機構參與的多選多電子投票方案,但選舉結束后會公開所有候選人的得票數.2012年,Pang 等人[6]基于混合網絡和PET 協議提出一個多選多電子選舉方案.2015年,楊婷婷等人[7]基于安全多方排序協議設計了一個多選多電子投票方案,但方案使用的排序協議要求參與者兩兩之間有安全信道,對通信環境要求較高.2018年,婁宇等人[8]基于全同態加密算法提出一個多候選人的電子投票方案,其計票工作由第三方計票中心完成且公開所有候選人得票數.2019年,劉霆等人[9]將隨機線性分組碼的秘密分享應用于多候選人電子投票方案中,解決了防投票記錄篡改、關鍵信息存儲的安全性等問題.同年,付偉偉等人[10]基于隨機矩陣提出一個多選一電子投票方案,該方案滿足可驗證性,但需要計票中心參與.2021年,邵清等人[11]基于ElGamal 強盲簽名和區塊鏈技術提出了電子投票方案,此方案沒有明確選舉場景、選票形式等,重點關注選票的可驗證性、不可篡改性等問題,且用智能合約取代可信第三方完成計票.文獻[12-16]等結合區塊鏈、同態加密等技術提出了完整的安全電子投票系統.

保密選票內容是安全電子投票方案的一個基本要求.但在計票階段,候選者得票數同樣屬于關鍵信息.因為破壞者可能根據候選人之間得票數的差異,在下次選舉時通過拉攏選票的手段,破壞選舉的公平性.因此,文獻[6]首次提出了投票方案中“全隱私”的概念,是指既保護選民選票內容又保護候選人得票數.上述文獻[6,7]提出的方案保護了落選者得票數.

為保密選票內容,可以用加密技術對選票信息進行加密.同時為方便后續計票,加密后的信息需要滿足一定的同態性質.而同態加密[17]滿足上述需求,能夠在不解密密文的前提下,通過對密文的操作實現對相應明文的計算.姚期智[18]提出的安全多方計算主要解決互不信任的數據擁有者之間的安全協同計算問題,基于此思想設計電子投票方案可解決計票時第三方機構參與的問題.

盡我們所知,已有的電子投票方案僅統計候選人的贊成票數.然而在實際的選舉場景中,時常會遇到以下情況:某些候選人贊成票數名列前茅,但選民對其反對聲音也很高.例如,在有50 位合法選民的選舉活動中,有兩位候選人得票情況如表1.根據已有的電子投票方案候選人2 獲勝,但是候選人1 當選更能反映選民的意愿.

表1 可能的得票情況

為了避免上述有爭議的選舉結果出現,本文在綜合考慮候選人贊成票數和反對票數的前提下,基于安全多方計算,結合ElGamal 同態加密系統提出一個無需第三方計票機構參與、全隱私的多選多電子投票方案.

1 預備知識

1.1 半誠實模型及其安全性定義

1.2 ElGamal 加密系統

1.3 IsEq 協議

2 多選多電子投票方案的設計

2.1 投票場景

2.2 表決方式

2.3 投票方案

本文設計的投票方案分為初始化階段、投票階段和計票階段,具體過程如下:

2.3.1 初始化階段

2.3.2 投票階段

2.3.3 計票階段

3 方案分析與比較

3.1 正確性分析

3.2 全隱私性分析

定理2 得證,即本方案滿足對選民選票信息的隱私保護.

由于本方案僅輸出獲勝候選人的名單,且即使在計票階段每位候選人保存了獲勝候選者對應的獲勝票數,但其無法將票數與候選人對應起來,則方案滿足對獲勝者得票數的隱私保護.同時,由于門限ElGamal 加密系統的特性,任何人都無法解密式(4)中的wj,sj,因此無法得到落選者的得票數,即方案滿足對落選者得票數的隱私保護.

綜上,本方案滿足全隱私性,并且保護了所有落選者的得票數.

3.3 其它安全性質分析

(1)無收據性是指任何選民都無法向他人證明自己的選票.本方案中每位選民將加密選票發送給所有候選人,由于門限ElGamal 加密系統的特性,選民靠自己不能解密任何密文,則無法向候選人證明自己的選票.

(2)公平性是指所有選民同時得到選舉結果.該方案的選舉結果在計票階段結束之后輸出,任何人都無法提前獲知選舉結果.因此,本方案滿足公平性.

3.4 復雜性分析與比較

本文設計的方案使用了門限ElGamal 加密系統,分析時只考慮費時的模指數運算,每次加密操作需要2 次模指數運算,每次解密操作需要n+m+1次模指數運算.

投票階段,所有選民需要3nm次加密.計票階段,所有選民和候選人最多執行m(n+2+k)次加密和m+k次解密.因此投票階段和階段最多需要模指數運算2[3nm+m(n+2+k)]+(m+k)(n+m+1)次.計票階段,最多需要調用m(3n+2k+t+1)次IsEq 協議,根據文獻[23],本文執行IsEq協議所需模指數運算復雜度綜上所述,本方案的計算復雜度為.

將本文設計的方案與文獻[6,7]中提出的全隱私多候選人電子投票方案進行對比,如表2所示.本方案考慮了候選者所得反對票數,且其全隱私性實現了對所有候選者得票數的保護.

表2 全隱私電子投票方案的對比

4 結語

為使選舉結果更符合選民的意愿,本文首次考慮了候選人反對票數.在此基礎上提出了一個滿足全隱私性、無需第三方參與的多選多電子投票方案,并且本方案的全隱形實現了對所有候選人得票數的保護.此外,分析表明方案同時滿足公平性和無收據性.下一步工作將研究符合實際應用場景需求、滿足更多安全性質且高效的電子投票方案.