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

1. 西安電子科技大學ISN 國家重點實驗室, 西安 710071

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

1 引言

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

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

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

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

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

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

2.1 符號定義

R 表示正實數(shù)集合. Z 表示整數(shù)集合. 對于所有正整數(shù)d, [d] :{1,2,··· ,d}. 已知集合S,x ←S表示為:x是均勻隨機從集合S中抽取的樣本. Zp表示商環(huán)Z/pZ.D: ZP[x]/〈xn+1〉,xn+1 是不可約多項式, 其中n是2 的冪,p是素數(shù)且p ≡3 mod 8,D中元素的多項式次數(shù)為n ?1, 系數(shù)在{?(p ?1)/2,··· ,(p ?1)/2}之內. 多項式向量用(a,b,···) 表示(注解:a1,a2,··· ,am ∈D,m是正整數(shù), (a1,a2,··· ,am) 的多項式向量由a表示). 對于一個多項式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) 是可忽略的當且僅當f(n)0, 且n足夠大).

2.2 格

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

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

定義2(SIVPγ問題) 給定一個n維格L,SIVPγ找到n個線性獨立格向量,其長度最大為γ·λn(L).以上, 關于格的計算復雜性問題請讀者參考文獻[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的內積在D中計算.

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

2.4 統(tǒng)計距離

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

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

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

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

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

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

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

以上, 更多關于統(tǒng)計距離的細節(jié)請參考文獻[16].

2.5 消息塊共享

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

2.6 填充排列技術

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

2.7 模型

2.7.1 系統(tǒng)模型

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

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

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

2.7.2 形式化定義

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

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

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

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

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

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

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

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

圖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是一個公共的抗碰撞哈希函數(shù), 將用于驗證消息的完整性.

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

輸出: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中沒有一個是可逆的, 返回步驟(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: 消息生成

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

輸入:P1,μ.

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

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

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

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

步驟4: 簽名

輸入:P1,P2, ski,μ.

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

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

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

步驟5: 簽名驗證

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

步驟6: 可鏈接性驗證

4 安全性分析

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

定理1LTRS 方案是正確的.

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

由于

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

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

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

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

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

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

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

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

(4)B誠實地回答F為用戶i ?=i?提交的任何破壞性詢問, 若F對i?作一個破壞性詢問,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 已被證明. 又因為可鏈接標志是j=H(?,μ[j],y?,r), 每個簽名者的tag 都是不同的, 當兩個簽名具有相同的tag 時, 那么這兩個簽名就是由同一個簽名者所簽.

5 性能分析

5.1 安全特性對比

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

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

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

5.2 計算開銷

定理5參數(shù)設置、密鑰分配、簽名和驗證的運行時間是安全參數(shù)內多項式可計算的.

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

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

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

5.3 通信開銷

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

表3 t = 2 時簽名大小對比(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 方案的簽名大小幾乎不產生影響.

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

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

各方案簽名大小對比:

由表2 和3 可知, LTRS 方案的簽名大小是隨著t和N的大小的改變而改變的, 通過和Bettaieb-CLRS[14]的工作對比, 在N相同的情況下, 我們的簽名大小相對較小. 然而隨著t的增加, LTRS 方案的簽名大小并不會發(fā)生明顯變化. 除此之外, 本方案還同BVLRS 方案[13]進行了簽名大小的對比. BVLRS方案是基于雙線性對的可鏈接環(huán)簽名, LTRS 是基于格的可鏈接環(huán)簽名, 相較于BVLRS 方案, LTRS 方案雖然在計算上的步驟相對復雜一些, 但LTRS 方案是具有抗量子性質的, 并且如表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 可知, 當環(huán)成員的個數(shù)固定時, 門限值的改變并不會對簽名長度大小產生很大影響, 且在門限值相同的條件下, LTRS 方案相對于文獻[14] 的算法的簽名長度較短. 由圖5 可知, 當門限值一定時, 簽名長度會隨著環(huán)成員的增加而增大, 但較文獻[14] 相比簽名長度較短; 當環(huán)成員數(shù)基數(shù)較大時, LTRS 簽名長度的增長速率較BVLRS 簽名較小, 也就是說, 在大規(guī)模成員的簽名場景下, LTRS 簽名的實用性更強, 效率更高.

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

6 電子投票協(xié)議

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

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

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

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

投票人v: 其身份為ID.

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

計票中心: 負責收票, 計算最終的投票結果.

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

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

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

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

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

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

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

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

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

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

(5) 公正性: 管理中心對選票內容是不可見的, 只有投票者本人才能夠驗證選票的內容. 并且只有當計票機構公布了所有合法的選票后, 投票人才投出承諾因子, 解密選票獲得選票的真實內容.

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

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

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

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

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

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

8 結束語

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