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

李亞偉,王維瓊,謝 瓊

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

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

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

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

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

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

表1 可能的得票情況

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

1 預(yù)備知識

1.1 半誠實(shí)模型及其安全性定義

1.2 ElGamal 加密系統(tǒng)

1.3 IsEq 協(xié)議

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

2.1 投票場景

2.2 表決方式

2.3 投票方案

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

2.3.1 初始化階段

2.3.2 投票階段

2.3.3 計(jì)票階段

3 方案分析與比較

3.1 正確性分析

3.2 全隱私性分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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