李亞偉,王維瓊,謝 瓊

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

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

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

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

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

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

表1 可能的得票情況

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

1 預(yù)備知識

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

1.2 ElGamal 加密系統(tǒng)

1.3 IsEq 協(xié)議

2 多選多電子投票方案的設(shè)計

2.1 投票場景

2.2 表決方式

2.3 投票方案

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

2.3.1 初始化階段

2.3.2 投票階段

2.3.3 計票階段

3 方案分析與比較

3.1 正確性分析

3.2 全隱私性分析

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

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

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

3.3 其它安全性質(zhì)分析

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

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

3.4 復(fù)雜性分析與比較

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

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

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

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

4 結(jié)語

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