葉 青,趙楠楠,趙宗渠,秦攀科,閆璽璽,湯永利
(河南理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,河南焦作 454000)
1991年,CHAUM等人首次提出群簽名的概念[1],其具有匿名性和追蹤性。群簽名允許群中合法成員代表群對消息進(jìn)行簽名,任意驗證者均可利用群公鑰來驗證該簽名的合法性,但無法確定簽名者的真實身份,即匿名性;當(dāng)發(fā)生爭議時,群管理員可以通過追蹤密鑰打開簽名找到真實的簽名者,即追蹤性。群簽名的匿名性和追蹤性使其被廣泛應(yīng)用于多種場景,如電子投票、電子商務(wù)系統(tǒng)和可信計算等。文獻(xiàn)[2]指出,基于經(jīng)典數(shù)論難題的傳統(tǒng)密碼方案[3-5]在多項式時間內(nèi)會被量子計算機(jī)破解,基于格的新型密碼體制將成為后量子密碼時代的研究熱點。
2010年,GORDON等人在Asiacrypt2010會議上提出格上群簽名方案[6],但該方案的密鑰長度和簽名長度都與群成員數(shù)量呈線性關(guān)系。2013年,LANGUILLAUMIE等人在Asiacrypt2013會議上提出一種密鑰長度、簽名長度與群成員數(shù)量呈對數(shù)關(guān)系的群簽名方案[7],雖然縮短了密鑰長度和簽名長度,但由于兩者均依賴于群成員數(shù)量,因此該方案并不適用于大群組的群簽名系統(tǒng)。2015年,NGUYEN等人提出一種簡單高效的群簽名方案[8],該方案的密鑰長度和簽名長度與群成員數(shù)量無關(guān),適用于大群組的群簽名系統(tǒng),但由于群成員私鑰由群管理員產(chǎn)生,因此不能抵抗群管理員對群成員的陷害攻擊??紤]到用戶加入群的動作在任意時間都有可能發(fā)生,并且當(dāng)發(fā)現(xiàn)某些群成員有行為不端的現(xiàn)象時,群管理員應(yīng)有權(quán)撤銷不法成員的簽名權(quán)力,因此,群簽名系統(tǒng)應(yīng)包含支持群成員動態(tài)加入、撤銷的加入機(jī)制和撤銷機(jī)制[9-10]。然而,以上群簽名方案都不支持群成員的加入和撤銷。
2016年,LIBERT等人構(gòu)造了一個包含加入機(jī)制的群簽名方案[11],但仍缺少群成員的動態(tài)撤銷機(jī)制。2017年,LING等人基于Merkle哈希樹構(gòu)造了一個格基完全動態(tài)(同時包含加入和撤銷機(jī)制)的群簽名方案[12],但該方案撤銷成員時需要更新哈希樹,計算較復(fù)雜且耗時較長,并且簽名長度仍與群成員數(shù)量相關(guān)。2018年,LING等人又提出了格上本地撤銷群簽名方案[13],但該方案不支持群成員的動態(tài)加入。2019年,李雪蓮等人提出一種適合大群組的格基完全動態(tài)簽名方案[14],但由于在加入過程中使用變色龍哈希函數(shù)和隨機(jī)采樣技術(shù),并且撤銷過程中增加了與撤銷圖靈機(jī)的交互代價,因此該方案的開銷較大。
為加快群成員的加入和撤銷速度,降低完全動態(tài)群簽名方案加入和撤銷機(jī)制的復(fù)雜性,本文在文獻(xiàn)[8]群簽名方案的基礎(chǔ)上,結(jié)合文獻(xiàn)[11,14]提出的動態(tài)群簽名思想,基于錯誤學(xué)習(xí)(Learning with Error,LWE)問題和非齊次小整數(shù)解(Inhomogeneous Small Integer Solution,ISIS)問題構(gòu)造一個高效的格上完全動態(tài)群簽名方案,對其進(jìn)行安全性證明,并與現(xiàn)有的格上群簽名方案進(jìn)行效率對比。
本文方案中的符號定義如表1所示。
表1 符號定義Table 1 Symbols definition
定義1(格)設(shè)b1,b2,…,bm是n維歐式空間Rm上m個線性無關(guān)的向量,則格L被定義為b1,b2,…,bm上所有整系數(shù)線性組合所構(gòu)成的集合,表示為L={a1b1+a2b2+…+ambm}(a1,a2,…,am∈Zq),而b1,b2,…,bm稱為格L的一組基。
定義3(離散高斯分布)給定實向量c∈Rm,任意實數(shù)s>0,則格L上以c為中心、以s為參數(shù)的離散高斯分布密度函數(shù)表示為:
當(dāng)s=1,c=0時,格L上任意一點x的離散高斯分布表示為:
2013年,LAGUILLAUMIE等人給出一個關(guān)于ISIS問題的零知識證明[7]:
2015年,NGUYEN等人給出一個關(guān)于Split-SIS問題上的零知識證明[8]:
由ISIS和LWE的對偶性可得關(guān)于LWE的零知識證明[18]:
以上零知識證明都可經(jīng)過Fiat-Shamir變換轉(zhuǎn)換為非交互零知識證明(Non-Interactive Zero-Knowledge Proofs,NIZKP)。
2.1.1 群簽名定義
一個動態(tài)群簽名算法[8,13-14,19-20]由以下多項式時間算法組成:
1)GSetup(1n,1N)→pp:輸入群簽名系統(tǒng)的安全參數(shù)n和群成員數(shù)量N,算法產(chǎn)生公共參數(shù)pp。
2)密鑰生成算法:
(1)GKgenGm(pp)→((gmsk,gmpk),(gtpk,gtsk)):該算法由群管理員執(zhí)行,輸入公共參數(shù)pp,生成群管理員的主密鑰對(gmsk,gmpk)和追蹤密鑰對(gtpk,gtsk)。
(2)GKgenUser(pp)→(uski,upki):該算法由群成員執(zhí)行,輸入公共參數(shù)pp,生成群成員的密鑰對(uski,upki)。
3)GUJoin(pp,gpk,gmsk)→(certi,regi):該算法是由群管理員和用戶執(zhí)行的交互式算法,輸入公共參數(shù)pp、群管理員的主私鑰gmpk和群公鑰gpk,gpk=(gmpk,gtpk,upki)。若算法執(zhí)行成功,則群管理員頒發(fā)成員證書certi和計算用戶的撤銷標(biāo)記regi,用戶加入成功。
4)GSig(gpk,uski,certi,m)→Σ:該算法由群成員執(zhí)行,將(gpk,uski,certi,m)作為輸入?yún)?shù),輸出一個由用戶uski在消息m上的簽名。
5)GRevoke →0/1:該算法由群管理員或用戶執(zhí)行,主要是群管理員將撤銷標(biāo)記加入到撤銷列表RL中,并更新和發(fā)布撤銷列表,若算法輸出為1則撤銷成功,否則輸出為0。
6)GVerify(gpk,m,Σ,RL)→0/1:該算法為確定性算法,并由驗證者執(zhí)行,將(gpk,m,Σ,RL)作為輸入?yún)?shù)來判斷該簽名的簽名者是否已被撤銷,若未被撤銷,則判定該簽名是否是消息m上的合法簽名,若是,則輸出為1,否則輸出為0。
7)GOpen(gpk,gtsk,m,Σ)→Idi:該算法為確定性算法,由群管理員執(zhí)行,輸入?yún)?shù)(gpk,gtsk,m,Σ),返回對消息m做簽名的用戶者身份Idi。
2.1.2 群簽名安全模型
一個群簽名方案必須滿足正確性、匿名性和追蹤性這3個安全特性[6-8,13-14],其中,正確性是群簽名中最基本的要求,匿名性和追蹤性是對群簽名的安全性要求。
1)在正確性方面,要求方案滿足簽名驗證正確性和簽名打開正確性[6-8,13-14],其中:簽名驗證正確性是指按算法步驟產(chǎn)生的簽名一定能通過驗證算法的驗證;簽名打開正確性是指按算法步驟產(chǎn)生的簽名一定能被群管理員打開。
2)匿名性是指任何獲得簽名的人都不能通過簽名判斷出真正的簽名者身份(除群管理員外)。匿名性又分為弱匿名性(CPA-匿名)和完全匿名性(CCA-匿名)[6-8]。在CCA-匿名的游戲中,敵手能夠進(jìn)行簽名打開查詢,而在CPA-匿名的游戲中,敵手不能進(jìn)行簽名打開查詢。顯然,CCA-匿名游戲中的敵手比CPA-匿名游戲中的敵手具有更強的攻擊能力,因此,滿足CCA-匿名的群簽名方案比滿足CPA-匿名的群簽名方案更安全。本文的群簽名方案是滿足CCA-匿名的。
3)追蹤性是指群成員產(chǎn)生的合法簽名能夠被群管理員打開,而偽造的簽名,即使是由合謀的群成員共同偽造的簽名,也不能夠被群管理員打開。追蹤性又分為CPA-追蹤和CCA-追蹤,兩者的區(qū)別在于游戲中敵手是否能夠進(jìn)行腐敗查詢。本文方案的追蹤性是滿足CCA-追蹤的。
正確性具體的形式化定義如下:
定義7(正確性)對于任意n、N,所有由GKgenGm(·)、GKgenUser(·)、GUJoin(·) 產(chǎn)生的(gpk,certi,gmsk,gtsk,uski)、消息m、i∈[N],若GSig(gpk,uski,certi,m)→Σ,則GVerify (gpk,m,Σ)=1?regi?RL且GOpen(gpk,gtsk,m,Σ)=Id。i
關(guān)于匿名性,下面給出一個敵手A和挑戰(zhàn)者B之間的游戲:
1)參數(shù)建立。輸入任意正整數(shù)n、N,挑戰(zhàn)者B執(zhí)行算法GSetup(·)、GKgenGm(·)、GKgenUser(·)、GUJoin(·)產(chǎn)生(gpk,certi,gmsk,gtsk,uski),并將群公鑰gpk發(fā)送給敵手A。
2)查詢。敵手A可以做簽名、撤銷、腐敗和簽名打開查詢,查詢過程如下:
(1)簽名查詢:敵手A輸入用戶身份Idi、任意消息m,簽名預(yù)言機(jī)用(certi,uski)產(chǎn)生用戶Idi的簽名,并將簽名返回給敵手A。
(2)腐敗查詢:敵手A輸入用戶身份Idi,腐敗預(yù)言機(jī)返回用戶Idi的私鑰給敵手A,挑戰(zhàn)者B將腐敗的用戶加入到腐敗集合Ua。
(3)撤銷查詢:敵手A可以查詢?nèi)我庥脩舻某蜂N標(biāo)記,挑戰(zhàn)者B將被查詢過的標(biāo)記加入到集合Uc
(4)簽名打開查詢:敵手A輸入(m,Σ),簽名打開預(yù)言機(jī)返回用戶身份Idi。
3)挑戰(zhàn)。敵手A選擇未被查詢的消息m,并同時選擇2個用戶d0,d1?Ua∪Uc,其中,用戶的私鑰和證書分別為,將這些信息發(fā)送給挑戰(zhàn)者B。挑戰(zhàn)者B選擇b←R{ 0,1},用計算挑戰(zhàn)簽名Σ*,將其發(fā)送給敵手A。
4)受限查詢。敵手仍可做一些查詢,但不能對用戶d0、d1做腐敗、撤銷和簽名打開查詢。
5)輸出。敵手A輸出b*。若b*=b,稱敵手獲勝。
定義8(匿名性)對于任意概率多項式時間的敵手A,若則稱群簽名方案具有CCA-匿名性。
關(guān)于追蹤性,下面給出一個敵手A與挑戰(zhàn)者B之間的游戲。在游戲中,敵手A的目標(biāo)是偽造一個簽名,管理員利用簽名打開算法不能打開偽造的簽名。敵手A能夠腐化群管理員,在查詢階段也能腐化用戶,并可利用加入算法產(chǎn)生一些虛擬成員。游戲過程如下:
1)參數(shù)建立。挑戰(zhàn)者B執(zhí)行算法GSetup(·)、GKgenGm(·)、GKgenUser(·),產(chǎn)生(gpk,certi,gmsk,gtsk,uski),將群公鑰發(fā)送給敵手A,并設(shè)置Ua=?。
2)查詢。敵手A可以做簽名和腐敗用戶的查詢,查詢過程如下:
(1)簽名查詢:敵手A輸入任意消息m和用戶身份Idi,簽名預(yù)言機(jī)可以返回對應(yīng)的簽名Σ,并將查詢過的簽名加入到集合Usi(gUsig是由用戶身份Idi、消息m和對應(yīng)消息簽名Σ組成的集合)。
(2)腐敗查詢:敵手A詢問任意用戶的私鑰時,挑戰(zhàn)者B將詢問過的用戶加入到集合Ua,并返回對應(yīng)用戶的私鑰。
3)偽造。敵手A利用其所擁有的信息產(chǎn)生一個消息簽名對(m*,Σ*)和撤銷列表RL*,如果GVerify(gpk,m*,Σ*,RL*)→1,對于Idi?Ua,(Idi,m*,Σ*)?Usig,簽名打開失敗同時GOpen (gpk,gtsk,m*,Σ*)=Idi且Idi∈Ua/RL,則稱敵手A獲勝。
隨著我國的城市化建設(shè)不斷加快,我國城市與鄉(xiāng)村之間的經(jīng)濟(jì)水平存在一定的差距,這也使得越來越多的鄉(xiāng)村勞動力開始向城市轉(zhuǎn)移,鄉(xiāng)村的勞動力大量減少。勞動力的減少使得在山區(qū)玉米種植的過程中,田間管理只能由勞動力較低的人群來進(jìn)行,這在一定程度上影響了田間管理的效果。另外,由于青年勞動力向城市轉(zhuǎn)移,也使得目前山區(qū)田間管理人員的受教育程度不足的問題越來越明顯,使其在管理過程中難以及時的發(fā)現(xiàn)問題和采取科學(xué)的方式來解決問題。這樣的情況經(jīng)常會引起玉米產(chǎn)量難以提升、品質(zhì)也得不到保障。
定義9(追蹤性)若對于任意概率多項式時間的敵手A,則稱群簽名方案具有CCA-追蹤性。
本文將文獻(xiàn)[11,14]提出的動態(tài)群簽名思想引入到文獻(xiàn)[8]的群簽名方案中,提出一個具有加入和撤銷機(jī)制的格上完全動態(tài)群簽名方案。該方案包含2個密鑰生成階段:第1個階段是群管理員的密鑰生成階段,其中使用文獻(xiàn)[8]的GPV陷門生成算法和正交抽樣算法產(chǎn)生群管理員的主密鑰和追蹤密鑰;第2個階段是群成員的密鑰生成階段,其中使用文獻(xiàn)[11]的離散高斯采樣算法,采取滿足一定條件的短向量作為群成員的簽名私鑰。在加入階段,使用GPV的格基擴(kuò)展技術(shù)和原像采樣算法生成群成員證書;在簽名階段,采用和文獻(xiàn)[6-8,14]類似的對偶LWE算法;撤銷階段分為用戶主動撤銷和群管理員撤銷群成員,兩者共同之處是都將撤銷標(biāo)記加入到撤銷列表中。
1)系統(tǒng)建立
GSetup(1n,1N)→pp:n為系統(tǒng)安全參數(shù),N為群成員個數(shù),該算法產(chǎn)生的隨機(jī)預(yù)言機(jī)為H:{0,1}*→{ 0,1}t,其中,t=ω(lbn),A0,,則參數(shù)pp={n,N,m,q,s,p,α,β,η,A0,A1}。
2)密鑰生成算法
由此可知群公鑰gpk=(A,B,F(xiàn),pp,vi)。
用戶先利用PKI中注冊過的密鑰(pusk[i],pupk[i])對vi做普通的數(shù)字簽名:sigi=再將(vi,sigi)發(fā)送給群管理員。群管理員驗證vi是否已被注冊,并且用pupk[i]驗證該簽名的合法性。若該簽名合法或是已被注冊過,則終止加入過程;否則群管理員做以下工作:
4)GSig(gpk,usk,cert,m)→Σ
(4)群成員產(chǎn)生一個關(guān)于zi并滿足(F,vi,β;zi)∈RISIS,的非交互零知識證明π3。
(5)輸出簽名Σ=(c0,c1,x1,π0,π1,π2,π3)。
5)GRevoke →0/1
(1)若是群管理員執(zhí)行該算法,則將撤銷標(biāo)記regi加入到撤銷列表中,即令RL=RL ∪{regi},然后發(fā)布撤銷列表,撤銷成功并返回1;否則返回0。
(2)若是用戶執(zhí)行該算法,則將(vi,certi,regi,sigi)發(fā)送給群管理員,向群管理員提交撤銷申請,群管理員對用戶進(jìn)行身份驗證,若驗證成功,則將用戶的撤銷標(biāo)記regi加入到撤銷列表中,RL=RL ∪{regi},然后發(fā)布撤銷列表,撤銷成功返回1,否則,返回0。
6)GVerify(gpk,m,Σ,RL)→0/1
7)GOpen(gpk,gtsk,m,Σ)→Idi
群管理員使用追蹤密鑰TB對密文c0解密,得到x0,計算y0=A1x1,y1=Ax0+A0x1,若y0≠0,能夠找到一個Idi同時滿足y1+Idi y0=ui則該算法輸出Idi;否則輸出⊥。
對本文方案的驗證正確性和打開正確性進(jìn)行證明。
3.1.1 驗證正確性證明
3.1.2 打開正確性證明
本文方案滿足CCA-匿名性和CCA-追蹤性,并且能夠抵抗陷害攻擊。下文將對其匿名性、追蹤性、安全性和抗陷害攻擊性進(jìn)行證明。
3.2.1 匿名性證明
定理1在隨機(jī)預(yù)言機(jī)模型下,本文方案在LWE假設(shè)下是CCA-匿名的。
證明:通過一系列的游戲G0~G5證明。
G0游戲過程如下:
1)挑戰(zhàn)者B按照本文方案獲得群公鑰gpk=(A,B,F(xiàn),pp,vi)、成員證書certi=(Idi,x0,x1)、群成員的私鑰uski=zi,i∈[N]和追蹤私鑰gtsk=TB,并將群公鑰、成員證書和群成員私鑰發(fā)送給敵手。
2)B初始化撤銷鏈表RL=?、腐敗用戶集合Ua=?和撤銷查詢集合Uc=?。
3)敵手A在查詢階段可以對任意用戶的任意消息m的簽名進(jìn)行查詢,對對應(yīng)消息上的簽名進(jìn)行打開查詢,還可以更新Ua和Uc。
4)敵手A輸出選擇的消息m*和身份標(biāo)識Id0,Id1∈[N],滿足Id0,Id1?Ua∪Uc且
綜上所述,在隨機(jī)預(yù)言機(jī)模型下,本文方案在LWE假設(shè)下是CCA-匿名的。
3.2.2 追蹤性證明
定理2在隨機(jī)預(yù)言機(jī)模型下,本文方案在ISIS假設(shè)下是CCA-追蹤的。
證明:假設(shè)敵手A多項式時間內(nèi)攻破本文方案的追蹤性,則可構(gòu)造一格算法C解決ISIS問題,即給定矩陣尋找一個,滿足‖x‖≤poly(m),Ax=umodq。C下一步工作為:
3)查詢。敵手A先對用戶進(jìn)行腐敗,再做簽名查詢,過程如下:
(1)腐敗。向預(yù)言機(jī)詢問任意用戶i∈[N]的私鑰,將i加入到集合Ua=?中,并返回zi。
(2)簽名詢問。敵手A向預(yù)言機(jī)詢問用戶關(guān)于消息m的簽名,并將簽名發(fā)送給C。若Idi=i,i?[N],則C拒絕接受簽名;若Idi=,C對消息m進(jìn)行簽名并利用NIZKP模擬器產(chǎn)生,否則,將在私鑰詢問階段中用回答的簽名私鑰作為Idi對消息m簽名。
由以上所證得,C解決ISIS問題的概率至少為ε(ε/qh-2-t)/8m2.5N,若ε是不可忽略的,則ε(ε/qh-2-t)/8m2.5N也是不可忽略的。
綜上所述,在隨機(jī)預(yù)言機(jī)模型下,本文方案在ISIS假設(shè)下是CCA-追蹤的。
3.2.3 抗陷害攻擊
在本文方案中,用戶i的私鑰是其通過高斯采樣算法采取的短向量zi∈進(jìn)而選取并計算用戶i的公鑰若群管理員或其他合謀群成員想偽造i的簽名,就必須要產(chǎn)生一個非交互零知識π3,又由于零知識證明π3具有可靠性,不知道zi的群管理員或其他群成員無法產(chǎn)生一個能通過驗證的π3,因此本文方案能夠抵抗陷害攻擊。
選取以下4個方案:文獻(xiàn)[8]格上高效的群簽名方案,文獻(xiàn)[11]格上具有高效協(xié)議和動態(tài)群簽名的簽名方案,文獻(xiàn)[13]格上具有本地撤銷機(jī)制的群簽名方案,文獻(xiàn)[14]適合大群組的格基動態(tài)群簽名方案,從公私鑰大小、簽名大小、加入代價、撤銷代價以及是否為完全動態(tài)群簽名等方面與本文方案進(jìn)行比較,如表2所示。其中,n為安全參數(shù),N為群成員個數(shù),q∈Z為模數(shù),m=6n1+δ,t=ω(lbn)為零知識證明中證明者和驗證者間交互的次數(shù),V為一次簽名運算時間,T1為一次隨機(jī)采樣算法時間,T2為一次數(shù)乘運算時間,T3為一次特殊采樣算法時間(耗時較少的運算如矩陣-矩陣加法、向量-向量加法,運算時間忽略不記)。
表2 不同方案的性能對比Table 2 Performance comparison of different schemes
由表2可知:文獻(xiàn)[8]方案中公私鑰大小均為O(mnlbq),簽名大小為O(tmnlbq)(t=ω(lbn) >1),與群成員數(shù)量N無關(guān),但該方案不具有加入和撤銷機(jī)制,屬于靜態(tài)群簽名;文獻(xiàn)[11]方案為具有加入機(jī)制的部分動態(tài)群簽名方案,但公鑰大小與成員數(shù)量相關(guān),不適合大群組的群簽名系統(tǒng),加入過程與本文方案相比雖然減少了1次特殊采樣運算,但增加了3nm次數(shù)乘運算和2次隨機(jī)采樣運算;文獻(xiàn)[13]方案為具有撤銷機(jī)制的部分動態(tài)群簽名方案,但公私鑰大小、簽名大小均與群成員數(shù)量N有關(guān),不適合大群組的群簽名系統(tǒng);文獻(xiàn)[14]方案是同時具有加入和撤銷機(jī)制的全動態(tài)群簽名方案,其簽名大小雖比本文方案的簽名短,但在加入過程中與本文方案相比增加了4nm次數(shù)乘運算時間、2次隨機(jī)采樣算法的時間以及1次特殊采樣算法時間,在撤銷過程中增加了1mn次的數(shù)乘運算時間;本文方案是具有加入和撤銷機(jī)制的完全動態(tài)群簽名方案,其加入、撤銷代價較小,并且簽名尺寸為O(tmnlbq),公鑰尺寸為O(mnlbq),簽名私鑰尺寸為O(m),均與群成員的數(shù)量N無關(guān),因此,本文方案也是適合大群組的群簽名方案。
群簽名的加入與撤銷機(jī)制及其密鑰與簽名的長度,始終是密碼學(xué)領(lǐng)域研究者所關(guān)注的重點問題。本文將動態(tài)群簽名思想引入文獻(xiàn)[8]群簽名方案,提出一個具有加入和撤銷機(jī)制的格上完全動態(tài)群簽名方案。在安全性方面,隨機(jī)預(yù)言機(jī)模型下該方案基于ISIS和LWE假設(shè)是可證明安全的,能夠抵抗量子攻擊,同時也能避免陷害攻擊;在效率方面,該方案不僅能夠?qū)崿F(xiàn)加入和撤銷功能,而且復(fù)雜度較低。此外,其簽名和密鑰長度均較短且與群成員的數(shù)量無關(guān)。本文方案中群成員的加入需要群管理員頒發(fā)數(shù)字證書,這會增加群成員的加入開銷和數(shù)字證書的存儲開銷,下一步將對此進(jìn)行改進(jìn),設(shè)計無證書的動態(tài)群簽名方案。