電子投票協(xié)議下的基于格的可鏈接門限環(huán)簽名*

莊立爽, 陳 杰,2, 王啟宇

1. 西安電子科技大學(xué)ISN 國家重點(diǎn)實(shí)驗(yàn)室, 西安 710071

2. 西安電子科技大學(xué) 西電密碼研究中心, 西安 710071

1 引言

在信息安全技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的支撐下, 傳統(tǒng)的投票方式已經(jīng)難以滿足人們的需求, 而日益興起的電子投票逐漸成為各種政治、娛樂活動中用于民意統(tǒng)計(jì)的主要方法, 它以其高效、便捷的特性而為人們所普遍接受. 一般來說, 安全的電子投票必須滿足以下八個(gè)特性: 合法性、匿名性、公正性、完備性、可驗(yàn)證性、正當(dāng)性、唯一性和無爭議性. 當(dāng)今的電子投票大多數(shù)都是建立在密碼學(xué)基礎(chǔ)上的, 大致可以分為以下幾種類型: 混合網(wǎng)模型[1]、盲簽名模型[2]以及同態(tài)加密模型.

Fujioka 等人采用比特承諾和盲簽名技術(shù), 實(shí)現(xiàn)了第一個(gè)實(shí)用的適合于大群體的電子投票方案(FOO)[2], 協(xié)議較混合網(wǎng)模型一類效率提升很大, 但該方案存在選票碰撞、選票可能無法打卡以及管理中心可以冒充投票者進(jìn)行投票等問題. 此后出現(xiàn)大量基于群簽名、盲簽名的電子投票方案[3–5]. 文獻(xiàn)[3]提出一種基于RSA 密碼體制的電子投票協(xié)議, 該方案不允許投票者中途棄權(quán), 難以滿足實(shí)際要求. 2003年, 陳曉峰等利用群簽名協(xié)議和時(shí)限承諾協(xié)議設(shè)計(jì)了一個(gè)電子投票方案[4], 雖然解決了選票碰撞問題, 但只有在注冊機(jī)構(gòu)或計(jì)票機(jī)構(gòu)誠信公正的前提下才能保證投票者身份的匿名性, 否則將會通過選票追蹤到投票人的所有信息. 2013 年, Ghavamipoor 等設(shè)計(jì)了一個(gè)匿名電子投票協(xié)議[5], 該協(xié)議利用投票者無需生成公私鑰對的方法提高了協(xié)議效率, 但投票階段必須依賴于一個(gè)不可追蹤的安全電子郵件系統(tǒng)向認(rèn)證機(jī)構(gòu)發(fā)送選票, 妨礙了其實(shí)際應(yīng)用. 從對目前國內(nèi)外研究的整體分析來看, 如何保證電子投票中的匿名性、不可重用性、公開可驗(yàn)證性和防止管理中心冒充投票人選票這些問題是學(xué)者們一直以來在電子投票安全性上的重點(diǎn)研究方向.

抗量子的電子投票系統(tǒng)直到2016 年才首次提出, Chillotti 提出的基于LWE 算法的電子投票系統(tǒng)[6],該方案基于格密碼, 大大簡化了正確性、隱私性和可驗(yàn)證性的證明. 該方案是基于LWE 的電子投票協(xié)議的第一個(gè)實(shí)例, 也是第一個(gè)真正意義上的、具有完整的系統(tǒng)架構(gòu)和較完備密碼學(xué)性質(zhì)的抗量子電子投票系統(tǒng). 但該方案面臨無法對選票合法性進(jìn)行驗(yàn)證、效率低等問題, 實(shí)踐性不強(qiáng). 2017 年, 文獻(xiàn)[7] 提出的基于混合網(wǎng)的電子投票系統(tǒng), 該方案雖然在基于混合網(wǎng)模型的電子投票類型中實(shí)現(xiàn)了公開驗(yàn)證和效率上的提升, 滿足電子投票的基本安全特性, 但不能防止二次投票. 2018 年, 文獻(xiàn)[8] 提出了一個(gè)安全、實(shí)用的抗量子電子投票系統(tǒng), 并給出了詳細(xì)的證明. 文獻(xiàn)[8] 的系統(tǒng)比Chillotti 方案的效率有所提高, 但該方案僅僅是一個(gè)完備的電子投票系統(tǒng), 不能防止二次投票. 如何應(yīng)對量子計(jì)算機(jī)的攻擊并克服現(xiàn)有方案的不足, 構(gòu)建一個(gè)基于抗量子密碼的高效可驗(yàn)證電子投票的系統(tǒng)正是我們研究的主要問題. 2019 年, Naranjo[9]基于困難問題構(gòu)建的同態(tài)加密系統(tǒng)設(shè)計(jì)了一個(gè)抗量子的電子投票系統(tǒng). 2020 年, 文獻(xiàn)[10] 構(gòu)造了一種基于SEAL 庫的同態(tài)加權(quán)電子投票系統(tǒng), 該同態(tài)加密系統(tǒng)的安全性格上RLWE 困難問題, 該系統(tǒng)可以滿足多個(gè)候選人投票、加權(quán)投票和高效計(jì)票的應(yīng)用需求.

為解決以上問題, 本方案基于格密碼為環(huán)簽名增加抗量子性, 應(yīng)用消息塊共享技術(shù)和填充排列技術(shù)構(gòu)造門限環(huán)簽名以適應(yīng)一種新的電子投票場景, 以及為環(huán)簽名增加可鏈接性質(zhì)使得簽名具有不可重復(fù)性. 本文提出一種基于格的可鏈接門限環(huán)簽名(LTRS) 方案, 給出了LTRS 方案安全性證明和性能分析, 并將LTRS 應(yīng)用到電子投票協(xié)議中, 該協(xié)議滿足合法性、匿名性、公正性、完備性、可驗(yàn)證性、正當(dāng)性、不可重用性、無爭議性、堅(jiān)固性、實(shí)用性和抗量子性.

在最后一部分, 我們將本方案與之前的方案分別從安全特性和簽名大小兩個(gè)方面進(jìn)行了對比. 文獻(xiàn)[11] 的算法是由Choi 和Kim 基于LWE 困難問題提出的, 可以抵抗已知攻擊且使用了消息塊共享的技術(shù), 但此算法效率不高. 文獻(xiàn)[12] 是基于SIS 困難問題提出的算法, 能夠抵抗已知攻擊, 但不具有可鏈接性. 文獻(xiàn)[13] 是基于雙線性對的困難性假設(shè)提出的一種可鏈接環(huán)簽名, 但該方案不具有抗量子性質(zhì). 文獻(xiàn)[14] 是基于格的困難問題SIVP 提出一種門限環(huán)簽名, 其優(yōu)點(diǎn)是由于基于格密碼, 其操作步驟較線性更快且具有門限機(jī)制, 在環(huán)成員為100 個(gè)的情況下, 其簽名大小達(dá)到0.26 Mbytes. 本文提出的LTRS 方案基于理想格, 能夠抵抗已知攻擊, 且具有可鏈接性, 當(dāng)環(huán)成員為100 個(gè)且門限值為2 時(shí), LTRS 簽名大小為0.0351 Mbytes. 在計(jì)算開銷上, 我們證明了LTRS 方案在參數(shù)設(shè)置、密鑰分配、簽名和驗(yàn)證的運(yùn)行時(shí)間是安全參數(shù)內(nèi)多項(xiàng)式可計(jì)算的. 在通信開銷上, 我們給出了LTRS 方案與其它方案在簽名大小上的對比.

2 預(yù)備知識和系統(tǒng)模型

2.1 符號定義

R 表示正實(shí)數(shù)集合. Z 表示整數(shù)集合. 對于所有正整數(shù)d, [d] :{1,2,··· ,d}. 已知集合S,x ←S表示為:x是均勻隨機(jī)從集合S中抽取的樣本. Zp表示商環(huán)Z/pZ.D: ZP[x]/〈xn+1〉,xn+1 是不可約多項(xiàng)式, 其中n是2 的冪,p是素?cái)?shù)且p ≡3 mod 8,D中元素的多項(xiàng)式次數(shù)為n ?1, 系數(shù)在{?(p ?1)/2,··· ,(p ?1)/2}之內(nèi). 多項(xiàng)式向量用(a,b,···) 表示(注解:a1,a2,··· ,am ∈D,m是正整數(shù), (a1,a2,··· ,am) 的多項(xiàng)式向量由a表示). 對于一個(gè)多項(xiàng)式a, 它的無窮范數(shù)l∞:||a||∞=maxi|a(i)|,其中a(i)是a的系數(shù). 相似地,a=(a1,a2,··· ,am) 的最小范數(shù)定義為:||α||∞=maxi||ai||∞,i ∈[m].

令n為系統(tǒng)的安全參數(shù), 其他參數(shù)由n隱式確定. ploy(n) :f(n) =O(nc)(f(n) 是可忽略的當(dāng)且僅當(dāng)f(n)0, 且n足夠大).

2.2 格

定義1(格) 格是Rm一類具有周期性結(jié)構(gòu)離散點(diǎn)的集合. 格是m維歐式空間Rm的n(m ≥n) 個(gè)線性無關(guān)向量組b1,b2,··· ,bn的所有整系數(shù)線性組合, 即

一般情況下,λ1(L(B)) 表示格L(B) 中最短向量.

定義2(SIVPγ問題) 給定一個(gè)n維格L,SIVPγ找到n個(gè)線性獨(dú)立格向量,其長度最大為γ·λn(L).以上, 關(guān)于格的計(jì)算復(fù)雜性問題請讀者參考文獻(xiàn)[15].

2.3 抗碰撞哈希函數(shù)

定義3對于整數(shù)m和D×?D,H(D,D×,m) ={ha:a ∈Dm}, 對于任意z ∈Dm×, 等式ha(z)=az=∑aizi成立, 其中a=(a1,a2,··· ,am) 且z=(z1,z2,··· ,zm),aizi的內(nèi)積在D中計(jì)算.

對于任意y,z ∈Dm,c ∈D,H(D,D×,m) 內(nèi)的哈希函數(shù)滿足式(2)和式(3)兩個(gè)條件.

2.4 統(tǒng)計(jì)距離

統(tǒng)計(jì)距離即兩個(gè)概率分布的區(qū)分.

定義5(統(tǒng)計(jì)距離) 令X和X′是一個(gè)集合S的不同變量,X和X′的統(tǒng)計(jì)距離如式(4)定義.

假設(shè)1 表明, 統(tǒng)計(jì)距離不會隨著變量增加而增長.

假設(shè)1[16]令X和X′是一個(gè)集合S的不同變量, 對于?f ∈S,f(X) 和f(X′) 的統(tǒng)計(jì)距離至多為?(f(X),f(X′))≤?(X,X′).

即, 如果兩個(gè)隨機(jī)變量(Xλ) 和(Xλ′) 是可忽略的, 攻擊者在區(qū)分帶樣本的(Xλ) 和(Xλ′) 上只有一個(gè)可忽略的優(yōu)勢, 在假設(shè)1 中, 沒有假設(shè)函數(shù)f的計(jì)算復(fù)雜性, 所以不管攻擊者是有界還是無界的, 它都成立.

但當(dāng)考慮多個(gè)變量時(shí), 統(tǒng)計(jì)距離可能會增加. 可由統(tǒng)計(jì)距離的定義得到一個(gè)結(jié)論, 如果X,Y來自分布φ,X′,Y′來自分布φ′, 可以得到不等式(5).

一個(gè)擁有同一分布的多個(gè)樣本的攻擊者可能比起只擁有一個(gè)樣本的攻擊者更容易區(qū)分, 因此, 如果兩個(gè)隨機(jī)變量的統(tǒng)計(jì)距離有上界ε(k), 已知同一分布的s個(gè)變量, 攻擊者盲目猜想的上界是s·ε(k).

以上, 更多關(guān)于統(tǒng)計(jì)距離的細(xì)節(jié)請參考文獻(xiàn)[16].

2.5 消息塊共享

圖1 消息塊共享Figure 1 Message block sharing

2.6 填充排列技術(shù)

Choi 等人[11]使用一個(gè)參數(shù)提取算法——門限參數(shù)提取算法, 把消息及其長度作為輸入, 輸出(λ,N,t),λ是安全參數(shù),N是環(huán)的大小,t是生成有效簽名的成員數(shù)門限值. 這種方法在簽名方案的實(shí)際應(yīng)用時(shí)存在嚴(yán)重的缺陷. 首先, 門限參數(shù)提取算法要求消息至少有d位, 因此如果消息很短, 門限簽名就不能工作. 其次, 要簽名的消息的位長決定了門限值t和N的大小, 由于生成消息的門限簽名之前, 門限值總是與系統(tǒng)參數(shù)一起設(shè)置的, 因此這在實(shí)踐中不可行. 為了避免這些缺點(diǎn), 本文使用了稱為填充排列的消息預(yù)處理技術(shù), 使門限簽名更實(shí)用.

2.7 模型

2.7.1 系統(tǒng)模型

石怡等人[17]曾提出一個(gè)投票問題: 一個(gè)公司包含兩類董事, 一類任職董事(8 人), 另一類不在公司任職(12 人); 要通過一個(gè)提案時(shí), 需半數(shù)以上董事同意外, 為保證可操作性, 還要求其至少包括6 名任職董事, 同時(shí)保證表決的匿名性.

本文提出的方案的系統(tǒng)模型如圖2 所示, 在這種類型的方案中, 存在多個(gè)地位相同的管理中心, 注冊工作由管理中心完成, 選票的認(rèn)證及計(jì)票工作由計(jì)票中心完成. 通常來說, 電子投票協(xié)議一般包括: 投票人V, 投票管理中心A, 計(jì)票機(jī)構(gòu)C.

圖2 電子投票系統(tǒng)模型Figure 2 E-voting system model

2.7.2 形式化定義

可鏈接門限環(huán)簽名方案由以下五個(gè)多項(xiàng)式時(shí)間內(nèi)的算法組成:

初始化: 輸入安全參數(shù), 輸出公共參數(shù)和門限參數(shù)(λ,N,t).

密鑰提取: 為每位用戶i ∈U生成公私鑰對(pki,ski).

簽名算法(μ,U,S): 此算法是一個(gè)交互式協(xié)議, 將U內(nèi)t個(gè)用戶的一組公鑰,S內(nèi)t個(gè)用戶一組私鑰和消息μ作為輸入, 輸出μ的t/N的門限環(huán)簽名σ.

簽名驗(yàn)證算法(μ,σ,t,U): 此算法是一個(gè)確定性算法, 輸出accept 或者reject.

可鏈接驗(yàn)證算法: 輸入σ和σ′, 輸出Link 或者Unlink.

3 可鏈接門限環(huán)簽名

本文提出一種基于格的可鏈接門限環(huán)簽名(LTRS), 并將此簽名應(yīng)用到電子投票協(xié)議中, 該方案引入了可鏈接的環(huán)簽名, LTRS 協(xié)議交互由管理中心、用戶和驗(yàn)證者共同完成, 交互流程圖如圖3 所示, 該算法由初始化、密鑰提取、消息生成、簽名、簽名驗(yàn)證和可鏈接驗(yàn)證一共6 個(gè)步驟組成.

圖3 LTRS 交互流程圖Figure 3 LTRS’s interactive diagram

3.1 形式描述

步驟1: 初始化

管理中心給定安全參數(shù)λ,N和t, 輸出公共參數(shù)P1={λ,t,N,d,n,m,p,C,H0,H,H′}.

輸入:λ,N和t.

(4) 令C ←D,C ?=0.

(5)H0={0,1}?→Ds,c是一個(gè)公共的抗碰撞哈希函數(shù), 將用于驗(yàn)證消息的完整性.

(6)H′={0,1}?→Ds,c,H={0,1}?→Ds,c是兩個(gè)抗碰撞哈希函數(shù), 在安全性證明中模擬隨機(jī)預(yù)言機(jī).

輸出:P1={λ,t,N,d,n,m,p,C,H0,H,H′}.

步驟2: 密鑰提取

管理中心為用戶Ui生成公私鑰對(pki,ski)=(hi,si).

輸入:P1.

(1) 令si=(si,1,si,2,··· ,si,m)←Dms,c.

(2) 如果si,j中沒有一個(gè)是可逆的, 返回步驟(1).

(3) 令j0∈{1,2,··· ,m}使得si,j0是可逆的.

(4) (ai,1,ai,2,··· ,ai,j?1,ai,j+1,··· ,ai,m)←Dm?1.

(5) 令ai,j0=s?1i,j0(C ?∑j?=j0ai,jsi,j) 且(ai=ai,1,ai,2,··· ,ai,m).

(6) 輸出(pki,ski)=(hi,si),h是由ai定義的哈希函數(shù)族H中的哈希函數(shù).

步驟3: 消息生成

給定消息μ, 管理中心進(jìn)行填充排列操作, 最后把μ分成d個(gè)消息區(qū)塊{μ1,μ2,··· ,μd}.

輸入:P1,μ.

(2) 對μ進(jìn)行填充操作, 將μ用0 bits 從g填充至ω·d, 表示為?μ.

(3) 從ω·dbits 置換集合中隨機(jī)選取一個(gè)置換π.

(4) 計(jì)算并且將π(?μ) 分為d個(gè)消息區(qū)塊{μ1,μ2,··· ,μd}.

注意: 用戶要保證消息區(qū)塊保密.

步驟4: 簽名

輸入:P1,P2, ski,μ.

(4) 一旦收到?, 每個(gè)簽名者確保它的hj(yj) 是在h1(y1),h2(y2),··· ,hN(yN) 之內(nèi)的, 并且檢查?和y?的正確性. 然后, 它令μ[j]=μj1||μj2||···||μjk, 再計(jì)算關(guān)聯(lián)標(biāo)簽j=H(?,μ[j],y?,r)(可得j在Ds,c內(nèi)),zj=sjj+yj.

(5) 如果zj/∈Dmz, 返回步驟(2).

輸出:σ={z?,e?,y?}.

步驟5: 簽名驗(yàn)證

輸出: 如果所有條件都滿足, 驗(yàn)證者輸出1, 否則輸出0.

步驟6: 可鏈接性驗(yàn)證

4 安全性分析

本節(jié)將從LTRS 簽名正確性、不可區(qū)分源匿名性和一定概率的不可偽造性來對LTRS 簽名的安全性進(jìn)行證明.

定理1LTRS 方案是正確的.

證明:假定σ={z?,e?,y?}是對μ的簽名, 消息塊共享技術(shù)使得消息經(jīng)處理后來自環(huán)中至少t個(gè)簽名者, 否則的話消息不能被完整組合而成. 所以一個(gè)合法簽名必須滿足步驟5 的(1). 由于步驟4 的(2)–(5) 保證了簽名只包含Dmz中的元素, 那么步驟5 的(2) 也是成立的. 關(guān)于步驟5 的(3):

由于

因此對于一個(gè)有效簽名來說, 步驟5 的(3) 成立.

定理2假設(shè)Melchor 等人的環(huán)簽名步驟[18]是匿名的, LTRS 在具有統(tǒng)計(jì)上不可區(qū)分源匿名性.

證明:在不可區(qū)分的源匿名游戲中, 敵手可依賴一個(gè)隨機(jī)比特b和系統(tǒng)公共參數(shù)P1獲得一個(gè)簽名,兩個(gè)不同的私鑰集合sk0={ski1,0,ski2,0,··· ,skit,0},sk1={ski1,1,ski1,1,··· ,skit,1}, 和消息μ. 除了{(lán)ski1,0,ski2,0,··· ,skit,0}和隨機(jī)比特b, 其余參數(shù)對敵手已知. 令Xb,P,skbμ是隨機(jī)變量, 代表敵手通過一系列已知參數(shù)獲得的簽名. 相似于Melchor 簽名[18]的匿名性證明, 可以將本方案的skb與其環(huán)簽名方案的skib對照來看. 本方案和Melchor 方案[18]的不同之處在于: 在Melchor 方案中, 本方案中的?z是由?zi ←?si·ei+ ?yi生成的分量, 其中?si是私鑰, ?yi是從Dmy中隨機(jī)選擇的,ei是通過哈希函數(shù)H計(jì)算的, 其他元素是從Dmz中隨機(jī)選擇的. 但是在本方案中,z?有t個(gè)部分是由?zi ←?si·ei+ ?yi產(chǎn)生的, ?yi是從Dmy中隨機(jī)選擇的,ei是通過哈希函數(shù)H計(jì)算的, 其他N ?t個(gè)元素是從Dmz中隨機(jī)選擇的.

在Lyubashevsky 方案[19]中的定理6.5 闡述, 對于任意由哈希函數(shù)族H選擇的h, 消息μ, 和任意兩個(gè)私鑰?s,?s′∈Dms, 使得對于隨機(jī)變量?z(?z′) 和e(e′)(其中e(e′) 分別是簽名算法的輸出結(jié)果),h(?s)=h(?s′), ?((?z,e),(?z′,e′))=n?ω(1)成立. 令Xb,P,skib,μ,R是描述Ring-sign(P,skib,μ,R) 輸出結(jié)果的隨機(jī)變量.P1={λ,t,N,d,n,m,p,C,H0,H,H′},P2={π,r},skib,μ和R是算法的輸入. 在Melchor的方案中, 如果這些變量的域都不是則failed, 當(dāng)b ∈{0,1},?(X0,P,ski0,μ,R,X1,P,ski1,μ,R) =n?ω(1). 在本方案中, 迭代此結(jié)果t ?1 次, 可得出結(jié)論?(X0,P,ski0,μ,R,X1,P,ski1,μ,R)=n?ω(1).

定理3假定存在一個(gè)多項(xiàng)式時(shí)間的偽造者F, 至多可進(jìn)行t ?1 次破壞性詢問, 可以對提出的可鏈接門限環(huán)簽名以概率ε輸出一個(gè)有效偽造結(jié)果. 通過利用F, 可構(gòu)造一個(gè)算法B以至少(N ?t+1)tε/N2的概率輸出一個(gè)偽造結(jié)果.

證明:假定存在偽造者F, 可以對提出的可鏈接門限環(huán)簽名以不可忽略的概率ε輸出一個(gè)有效偽造結(jié)果. 通過應(yīng)用F, 構(gòu)造一個(gè)多項(xiàng)式時(shí)間算法B, 算法B為Lyubashevsky 方案以不可忽略的優(yōu)勢輸出偽造結(jié)果[20].

B收到作為輸入的一個(gè)公鑰pk?,B應(yīng)用帶有輸入公鑰pk={pk1,pk2,··· ,pkN}的F.B選擇一個(gè)指引i?←{1,2,··· ,N}和集合pki?=pk?. 其他公鑰由密鑰生成算法生成.B模擬F的預(yù)言查詢?nèi)缦?

(1) 當(dāng)F對消息μ作簽名詢問,B通過運(yùn)行簽名算法生成響應(yīng), 其中有t個(gè)簽名者, 其身份指引i ?=i?.

(4)B誠實(shí)地回答F為用戶i ?=i?提交的任何破壞性詢問, 若F對i?作一個(gè)破壞性詢問,B簡單地中止. 那么F完全可以作t ?1 次破壞性詢問.

定理4LTRS 方案是可鏈接的.

證明:根據(jù)定理3 可知非環(huán)成員是不能夠偽造合法的環(huán)簽名的. 我們只需要考慮敵手F偽造與其它環(huán)成員簽名鏈接的簽名. 假定敵手F能夠成功, 即σ={z?,e?,y?}是合法偽造. 根據(jù)定義, 我們知道tag ==H(?,μ[j],y?,r), 且知道SIVPγ問題是困難的, 且定理3 已被證明. 又因?yàn)榭涉溄訕?biāo)志是j=H(?,μ[j],y?,r), 每個(gè)簽名者的tag 都是不同的, 當(dāng)兩個(gè)簽名具有相同的tag 時(shí), 那么這兩個(gè)簽名就是由同一個(gè)簽名者所簽.

5 性能分析

5.1 安全特性對比

在這一節(jié), 我們將LTRS 方案與文獻(xiàn)[11–14] 四個(gè)方案在安全特性上進(jìn)行對比. 由表1可知, 五個(gè)方案都可抵抗已知攻擊, 在可鏈接性質(zhì)上, 只有文獻(xiàn)[13] 和LTRS 方案具備可鏈接性質(zhì), 但文獻(xiàn)[13] 是基于雙線性對的困難問題構(gòu)造的可鏈接環(huán)簽名, 不可抵抗量子攻擊. 在門限性上, 文獻(xiàn)[14] 的方案和LTRS 都具備門限性質(zhì), 但文獻(xiàn)[14] 不具備可連接性.

由表1 可知, LTRS 既具備可鏈接性質(zhì)和門限性, 也具備抗量子特性. 以上三個(gè)性質(zhì)為簽名應(yīng)用的場景提供了更多可能.

表1 安全特性對比Table 1 Comparison of security features

5.2 計(jì)算開銷

定理5參數(shù)設(shè)置、密鑰分配、簽名和驗(yàn)證的運(yùn)行時(shí)間是安全參數(shù)內(nèi)多項(xiàng)式可計(jì)算的.

證明:顯然, 參數(shù)設(shè)置和驗(yàn)證算法是在多項(xiàng)式時(shí)間內(nèi)執(zhí)行的, 只需考慮密鑰分配和簽名兩個(gè)算法的迭代.

定理3 顯示, 步驟2 中的(1) 中選擇的每個(gè)多項(xiàng)式都是可逆的概率以指數(shù)形式接近于1, 因此預(yù)期的迭代大約是1. 所以密鑰分配算法的運(yùn)行時(shí)間是多項(xiàng)式時(shí)間的.

以上, 本方案的計(jì)算開銷很小. 步驟1 的計(jì)算開銷主要包括一些參數(shù)的采樣和哈希函數(shù)的選擇. 步驟2 中只需要一個(gè)向量的選擇以及向量內(nèi)積. 步驟3 的計(jì)算包括比特值填充和一個(gè)隨機(jī)置換. 步驟4 的計(jì)算主要包括兩個(gè)哈希函數(shù)計(jì)算、幾個(gè)向量的采樣和計(jì)算. 步驟5 也包含幾個(gè)哈希函數(shù)和向量的運(yùn)算. 步驟6只需要一個(gè)向量的選擇以及向量內(nèi)積. LTRS 簽名的參數(shù)設(shè)置、密鑰分配、簽名和驗(yàn)證的運(yùn)行時(shí)間是安全參數(shù)內(nèi)多項(xiàng)式可計(jì)算的.

5.3 通信開銷

表2 和表3 給出了本文提出的LTRS 方案與其它方案在簽名大小上的對比. 其中包含王啟宇等人提出的BVLRS 方案[13], Cayrel 等人提出的CLRS 方案和T-CLRS 方案[21], 與Bettaieb 等人提出的改進(jìn)的基于格的門限環(huán)簽名方案[14].

表3 t = 2 時(shí)簽名大小對比(Mbytes)Table 3 Comparison of signature’s size with t = 2 (Mbytes)

相較于BVLRS 方案, LTRS 方案具有抗量子性和門限性以及簽名長度較短的優(yōu)勢. 相較于T-CLRS方案, 在N相同的情況下, LTRS 方案的簽名大小相對較短, 除此之外, 由表2也可看出, 同T-CLRS 方案類似的是,t大小的改變對LTRS 方案的簽名大小幾乎不產(chǎn)生影響.

表2 N = 100 時(shí)簽名大小對比(Mbytes)Table 2 Comparison of signature’s size with N = 100 (Mbytes)

令參數(shù)設(shè)置為n=64,m=2048,q=257, 承諾長度224 比特將提供111 的安全級別. LTRS 方案的構(gòu)造中, 簽名由兩個(gè)部分組成, 第一部分的每個(gè)元素屬于Dmz, 第二部分的每個(gè)元素屬于Ds,c(具體參考步驟5(1)).

各方案簽名大小對比:

由表2 和3 可知, LTRS 方案的簽名大小是隨著t和N的大小的改變而改變的, 通過和Bettaieb-CLRS[14]的工作對比, 在N相同的情況下, 我們的簽名大小相對較小. 然而隨著t的增加, LTRS 方案的簽名大小并不會發(fā)生明顯變化. 除此之外, 本方案還同BVLRS 方案[13]進(jìn)行了簽名大小的對比. BVLRS方案是基于雙線性對的可鏈接環(huán)簽名, LTRS 是基于格的可鏈接環(huán)簽名, 相較于BVLRS 方案, LTRS 方案雖然在計(jì)算上的步驟相對復(fù)雜一些, 但LTRS 方案是具有抗量子性質(zhì)的, 并且如表3 所示, LTRS 方案在簽名長度上也相對BVLRS 方案較短, 通信開銷較小.

通過圖4 和5 也可直觀看出本方案與其它方案在簽名長度上的對比.

圖4 與T-CLRS [21] 和Bettaieb-CLRS [14] 簽名長度對比圖Figure 4 Comparison of signature’s size with T-CLRS [21] and Bettaieb-CLRS [14]

由圖4 可知, 當(dāng)環(huán)成員的個(gè)數(shù)固定時(shí), 門限值的改變并不會對簽名長度大小產(chǎn)生很大影響, 且在門限值相同的條件下, LTRS 方案相對于文獻(xiàn)[14] 的算法的簽名長度較短. 由圖5 可知, 當(dāng)門限值一定時(shí), 簽名長度會隨著環(huán)成員的增加而增大, 但較文獻(xiàn)[14] 相比簽名長度較短; 當(dāng)環(huán)成員數(shù)基數(shù)較大時(shí), LTRS 簽名長度的增長速率較BVLRS 簽名較小, 也就是說, 在大規(guī)模成員的簽名場景下, LTRS 簽名的實(shí)用性更強(qiáng), 效率更高.

圖5 與BVLRS [13] 和Bettaieb-CLRS [14] 簽名長度對比圖Figure 5 Comparison of signature’s size with BVLRS [13] and Bettaieb-CLRS [14]

6 電子投票協(xié)議

LTRS 交互流程是由管理中心A初始化整個(gè)系統(tǒng), 生成公私鑰和公共參數(shù), 投票時(shí), 投票人通過比特承諾技術(shù)來隱匿自己的選擇, 將自己所屬的類別信息嵌入到選票中, 隨后發(fā)送選票給n個(gè)管理中心申請簽名, 簽名采用LTRS 方案. 管理中心檢驗(yàn)投票人的身份和類別信息, 為合法投票人的選票進(jìn)行簽名, 并將投票人所屬類別標(biāo)識嵌入到簽名信息中, 用來區(qū)分不同的類別, 最后將簽名返還給投票人, 投票人計(jì)算出最后的有效簽名. 最后, 計(jì)票中心驗(yàn)證簽名并進(jìn)行計(jì)票. 整個(gè)投票過程中的數(shù)據(jù)均可公開公布, 根據(jù)這些數(shù)據(jù), 任何人都可以驗(yàn)證投票結(jié)果是否正確. 交互流程圖如圖6 所示, 共由以下6 個(gè)步驟組成.

圖6 電子投票協(xié)議交互圖Figure 6 E-voting protocol’s interactive diagram

協(xié)議的具體步驟如下:

(1) 本方案參與人員及其擔(dān)任角色:

投票人v: 其身份為ID.

管理中心A:{A1,A2,··· ,An}, 檢驗(yàn)投票人的身份和類別信息, 為合法投票人的選票進(jìn)行簽名.

計(jì)票中心: 負(fù)責(zé)收票, 計(jì)算最終的投票結(jié)果.

(2) 管理機(jī)構(gòu)運(yùn)行初始化算法, 系統(tǒng)的公私鑰為(pki,ski) = (hi,si), 設(shè)Sub1,Sub2,··· ,SubI是I個(gè)類別的標(biāo)識信息.且y?=H′(h1(y1),h2(y2),··· ,hN(yN),?), 然后L將h1(y1),h2(y2),··· ,hN(yN) 和? 以及y?分享給剩下t ?1 個(gè)簽名者. 投票人隨機(jī)選擇q, 對選票v進(jìn)行比特承諾x=f(v,q). 計(jì)算令x[j]=xj1||xj2||···||xjk. (ID,h,Subi,?) 發(fā)送給每個(gè)管理中心Ai.

(4) 每個(gè)簽證中心Aj檢驗(yàn)投票人的身份ID 和他所屬類別標(biāo)識Subi, 若二者都合法則一旦收到?,每個(gè)簽名者確保它的hj(yj) 是在h1(y1),h2(y2),··· ,hN(yN) 之內(nèi)的, 并且檢查? 和y?的正確性. 再計(jì)算關(guān)聯(lián)標(biāo)簽j=H(?,x[j],y?,r),zj=sjj+yj. 發(fā)送σ={z?,e?,y?}給投票人.

(6) 計(jì)票中心收到簽名后, 運(yùn)行可鏈接驗(yàn)證算法. 若可鏈接則舍棄簽名, 否則接受.

(7) 投票人看到自己的選票被公布出來以后, 發(fā)送t,q給計(jì)票中心, 計(jì)票中心利用q打開比特承諾,計(jì)票并公布結(jié)果. 利用Subi信息, 計(jì)票中心可以很方便地統(tǒng)計(jì)每類投票人的投票情況.

7 電子投票協(xié)議安全性分析

新的電子投票協(xié)議滿足合法性、匿名性、公正性、完備性、可驗(yàn)證性、正當(dāng)性、不可重用性、無爭議性、堅(jiān)固性、實(shí)用性和抗量子性.

(1) 完備性: 在協(xié)議中, 當(dāng)誠實(shí)管理中心的個(gè)數(shù)≥t時(shí), 合法的投票人必然能夠獲得簽名. 當(dāng)他發(fā)現(xiàn)自己的選票沒有被計(jì)票機(jī)構(gòu)公布時(shí), 可以提出抗議. 計(jì)票時(shí), 投票人發(fā)送解密選票的承諾因子q, 所有能正確解密的選票即為合法的選票, 而所有不能解密的選票則為不合法的選票. 因此所有有效的選票必然會被正確統(tǒng)計(jì), 滿足完備性.

(2) 合法性: 簽證中心會檢驗(yàn)投票人的身份ID 及其所屬的類別Subi, 只有合乎條件的人, 才能獲得簽證中心的簽名.

(3) 不可重用(唯一) 性: 計(jì)票中心收到簽名后, 運(yùn)行可鏈接驗(yàn)證算法. 如果是可鏈接的, 則計(jì)票機(jī)構(gòu)認(rèn)為這是兩張相同的選票, 只保留一張, 投票人不可能投出多張選票, 因此方案滿足不可重用性.

(4) 匿名性: 投票人將選票進(jìn)行比特承諾之后, 依據(jù)消息共享技術(shù)令x[j]=xj1||xj2||···||xjk, 然后對其使用環(huán)簽名進(jìn)行加密. 而通過匿名通訊信道發(fā)送選票和承諾因子, 也不會暴露投票人的身份.

(5) 公正性: 管理中心對選票內(nèi)容是不可見的, 只有投票者本人才能夠驗(yàn)證選票的內(nèi)容. 并且只有當(dāng)計(jì)票機(jī)構(gòu)公布了所有合法的選票后, 投票人才投出承諾因子, 解密選票獲得選票的真實(shí)內(nèi)容.

(6) 可驗(yàn)證性: 利用公告牌上公布的簽名和t、q, 任何人都可以利用管理中心的公鑰及參數(shù)驗(yàn)證選票的合法性, 同時(shí)可以利用承諾因子q檢驗(yàn)計(jì)票中心解密的正確性.

(7) 正當(dāng)性: 方案的注冊部分可以防止惡意的投票者進(jìn)行投票.

(8) 無爭議性: 由于本方案是基于LTRS 和比特承諾技術(shù), 因此方案的安全性是可證明的, 方案中的各方的公鑰都是公開的, 任何投票人或第三方都可驗(yàn)證方案過程的正確性.

(9) 堅(jiān)固性: 本方案采用了門限簽名方案, 能夠容忍部分管理中心的作弊行為. 一張合法的選票只需要經(jīng)過t個(gè)管理中心的簽名就可以了. 而且消息塊共享保證了當(dāng)有投票人棄權(quán)時(shí), 可以有效地防止簽證中心冒名投票的現(xiàn)象.

(10) 抗量子性: 本協(xié)議的LTRS 簽名是基于格的環(huán)簽名, 具有抗量子特性.

(11) 實(shí)用性: 本協(xié)議可將投票人劃分為若干個(gè)不相交的類別, 可以分別統(tǒng)計(jì)每個(gè)類別中投票人的觀點(diǎn),也可以像一般的投票方案一樣, 統(tǒng)計(jì)所有人的觀點(diǎn), 這只需要將最后的投票結(jié)果匯總起來就可以了. 無論劃分的類別個(gè)數(shù)是多少, 本協(xié)議所需進(jìn)行的投票輪數(shù)都固定不變. 因而本協(xié)議滿足實(shí)用性.

8 結(jié)束語

電子投票系統(tǒng)雖然日益完善, 但由于量子計(jì)算機(jī)的快速發(fā)展, 提出一種抗量子的電子投票系統(tǒng)對于電子投票的安全性的保證具有重要意義. 本文提出的LTRS 方案使用消息塊共享技術(shù), 在實(shí)現(xiàn)中央權(quán)力分散的同時(shí)滿足簽名的匿名性, LTRS 方案的可鏈接性保證簽名可被公共驗(yàn)證是否由同一用戶生成. 通過安全性分析證明了方案在標(biāo)準(zhǔn)模型下的正確性、不可區(qū)分源匿名性、不可偽造性和可鏈接性. 通過性能分析可知簽名算法是多項(xiàng)式時(shí)間內(nèi)可計(jì)算的, 并且給出了與其它方案的數(shù)據(jù)對比結(jié)果分析. 本文提出的基于LTRS 簽名的電子投票協(xié)議可解決多類別投票問題, 該協(xié)議滿足電子投票協(xié)議的八個(gè)安全特性和堅(jiān)固性、實(shí)用性和抗量子性, 除此之外, 方案可滿足大規(guī)模的電子投票需求.