張利利,馬艷琴

(黃河科技學(xué)院信息工程學(xué)院,河南鄭州 450063)

0 引 言

1984年,Shamir[1]提出基于身份的公鑰密碼體制,其簡(jiǎn)化了基于證書(shū)的公鑰體制負(fù)擔(dān)最重的密鑰管理過(guò)程.1996年,Mambo等[2]提出代理簽名,利用代理簽名,原始簽名人可以將他(她)的簽名權(quán)委托給代理簽名者,對(duì)任何消息代理人都可以進(jìn)行簽名,任何人只要知道原始簽名人的公鑰就可以對(duì)代理簽名進(jìn)行驗(yàn)證.2001年,Rivest等[3]提出環(huán)簽名,其實(shí)際上是一種簡(jiǎn)化的群簽名,它僅包括環(huán)成員而沒(méi)有管理者,不需要群建立過(guò)程,也無(wú)法撤銷真實(shí)簽名者的匿名性,簽名驗(yàn)證者可以確定簽名來(lái)自某個(gè)環(huán)成員,但無(wú)法確定簽名者的具體身份,因而可以有效地保護(hù)實(shí)際簽名者的隱私權(quán).根據(jù)對(duì)代理人保持匿名的應(yīng)用,2003年,Zhang[4]提出了代理環(huán)簽名的方案,并給出第一個(gè)基于身份的代理環(huán)簽名方案:當(dāng)授權(quán)人將簽名權(quán)利授予很多代理人時(shí),這些代理人組成了一個(gè)代理人集合,每個(gè)代理人都可以代替授權(quán)人執(zhí)行簽名操作,并且可不被任何人(包括授權(quán)人)揭開(kāi)他的身份.2006年,楊少春[5]提出了一種更加高效的代理環(huán)簽名方案,計(jì)算量得到很大的改善.但是,這些代理環(huán)簽名方案大部分都是基于大整數(shù)分解和離散對(duì)數(shù)問(wèn)題的,在量子計(jì)算機(jī)得到應(yīng)用的前提下,大整數(shù)分解問(wèn)題和離散對(duì)數(shù)問(wèn)題都可以利用多項(xiàng)式時(shí)間算法解決.因此,設(shè)計(jì)能抵抗量子攻擊的代理環(huán)簽名方案成為該領(lǐng)域需解決的問(wèn)題.近年來(lái),基于格構(gòu)造的新型密碼系統(tǒng)因具有運(yùn)算簡(jiǎn)單(通常只需要線性運(yùn)算)、能抵抗量子攻擊和存在最壞情況下的隨機(jī)實(shí)例等特點(diǎn),成為公鑰密碼領(lǐng)域的研究熱點(diǎn),并取得了一系列的研究成果[6-9].本研究基于格上的SIS和 ISIS問(wèn)題的困難性,利用原像抽樣函數(shù)[6]和格基代理算法[9]構(gòu)造了一個(gè)格上基于身份的無(wú)可信中心的代理環(huán)簽名方案.

1 基礎(chǔ)知識(shí)

1.1 格

設(shè) b1,b2,…,bn是Rm上一組的量,令B=[b1, b2,…,bn]? Rm×n,則由 B生成的n為格定義為,

Λ(B)的正交格定義為,

設(shè)ω是一個(gè)向量,ω的lp-范數(shù)定義為,

當(dāng)p=2時(shí),稱作歐幾里得范數(shù),簡(jiǎn)記為‖ω‖.

1.2 格上的困難問(wèn)題

(1)SVP問(wèn)題(最短向量問(wèn)題).設(shè)A是格的一組基,SVP問(wèn)題就是在格上尋找一個(gè)非零向量u,滿足任意格上的向量v,有 ‖u‖≤‖v‖成立.其中 ‖·‖為給定的范數(shù).

(2)SIS問(wèn)題(小整數(shù)解問(wèn)題).給定整數(shù) q,實(shí)數(shù)β,矩陣A∈Zn×mq,尋找一個(gè)非零向量 e,滿足Ae= 0modq,且 ‖e‖≤β.

(3)ISIS問(wèn)題(非齊次小整數(shù)解問(wèn)題).給定整數(shù)q,實(shí)數(shù)β,向量y∈Zmq,矩陣A∈Zn×mq,尋找一個(gè)非零向量e,滿足Ae=ymodq,且 ‖e‖≤β.

1.3 格上的多項(xiàng)式時(shí)間算法

由于SISq,m,rm是困難的,若 A∈Zn×mq,可得格上的陷門函數(shù)[6],

其中,fA(e)=Aemodq,Dn={z∈Zn|‖e‖≤r m},Rn= Zqn,輸入分布為 DZm,s.

基于原像抽樣函數(shù),文獻(xiàn)[6]給出格上基于原像抽樣的多項(xiàng)式時(shí)間算法:

(1)TrapGen(1n).算法 TrapGen(1n)輸出(A, B),其中,矩陣 A在Znq×m接近均勻分布,矩陣B是Λ⊥(A)的小基.

(2)Sample D(A;r).從分布DZm,r中選取向量e,且fA(e)=Aemodq接近于Rn上均勻分布.

(3)Sample ISIS(A;B;y;r).輸入矩陣 A ∈Zn×m,Λ⊥(A)的小基B,向量y∈Zm和r>0,qqSample ISIS(A;B;y;r)輸出非零向量e,e為接近分布 DΛ⊥(A),r.

1.4 格基代理算法

格基代理算法[10]是一種由較小維數(shù)的格和基向量構(gòu)造更大維數(shù)的格和基向量的算法.令 n,q, m,k為正整數(shù),并且 q≥2,m≥5nlogq,格基代理算法ExtBasis和RandBasis描述如下:

(1)ExtBasis(S,A=A1‖A2).輸入矩陣 A1∈Zqn×m,任意矩陣A2∈Znq×m1,Λ⊥(A1)的基S1,算法⊥～ExtBasis輸出 Λ(A)的基 S,其中,‖S1‖=～‖S‖.

(2)RandBasis(A,S,r).輸入矩陣 A ∈ Znq×m, Λ⊥(A)的基S和參數(shù)r≥‖S‖ω( nlogq),算法RandBasis輸出的Λ⊥(A)的S′,其中,‖～S′‖≤r m,由S′得不到S的任何信息.

2 格上基于身份的代理環(huán)簽名方案

下面主要描述利用格上的難題和格基代理技術(shù)構(gòu)造基于身份的代理環(huán)簽名方案.方案中的參數(shù)設(shè)置如下:令 n,q,m,k為正整數(shù),并且 q≥2,m≥flogn,L～≥O( nlogq),r≥L～ω( logn).設(shè) B1, B2,…,Bl為l個(gè)代理人,H1:{0,1}＊→{0,1}n,H2: {0,1}＊→{0,1}n×m為兩個(gè)安全的Hash函數(shù),m′= (l+1)m.

2.1 系統(tǒng)建立

原始簽名人利用算法 TrapGen(1n)輸出(A0, S0),其中,A0在Znq×m接近均勻分布,S0是Λ⊥(A0)的小基.類似的,代理人Bi利用算法TrapGen(1λ)輸出(Ai,Si),Ai在Znq×m接近均勻分布,Si是Λ⊥(Ai)的小基,A0,S0分別為原始簽名人公鑰和私鑰,Ai, Si分別代理簽名人Bi的公鑰和私鑰.

2.2 代理密鑰的生成與驗(yàn)證

2.2.1 代理密鑰的生成.

原始簽名人利用代理簽名人Bi的身份信息IDi∈{0,1}＊為 Bi生成代理密鑰,

其中,Siδ為Λ⊥(Aiδ)的基.然后,將 Siδ發(fā)給Bi,i=1 ,2,…,l.

2.2.2 代理密鑰的驗(yàn)證.

Bi驗(yàn)證:①Siδ∈ Z2m×kq,k=2m- rank(Aiδ);②AiδSiδ=0modq是否成立,若成立,Bi接受Siδ為代理密鑰,否則,拒絕.

2.3 代理環(huán)簽名的生成

l個(gè)代理簽名人構(gòu)成一個(gè)環(huán),任何代理人Bi利用他的私鑰Si和代理密鑰Siδ均可以為原始簽名人生成代理環(huán)簽名.假設(shè)真正的簽名人為第 k個(gè)代理人Bk,待簽消息M ∈{0,1}＊,簽名步驟如下:

(1)由私鑰Sk,Bk利用算法ExtBasis(Sk,A′δ= Ak‖A1‖‖A2‖…‖Ak-1‖Ak+1‖…‖Al)生成S′,對(duì)矩陣A′做列換,化A′為A=A1‖A2‖…‖Ak+1‖‖…‖Al,S′做相應(yīng)的變換化為S,且 S為Λ⊥(A)的基.

(2)由代理密鑰 Siδ,Bk利用算法 ExtBasis(Siδ, A′δ=A0‖H2(IDk)‖…‖H2(IDk-1‖H2(IDk+1)‖…‖H2(IDl))生成 S′δ,將A′δ化為Aδ=A0‖(H2(ID1)‖…‖H2(IDk-1)‖H2(IDk)‖H2(IDk+1)‖…‖H2(IDl)),S′δ做相應(yīng)的變換化為 Sδ,Sδ為Λ⊥(Aδ)的基.

(3)計(jì)算y= H1(M);

(4)利用SampleISIS(A;S;y;r)生成的向量 e,若 ‖e‖≥s m′或e=0,重新生成e.

(5)利用SampleISIS(Aδ;Sδ;y;r)生成的向量eδ,若 ‖eδ‖≥s m′-1或eδ=0,重新生成eδ.

(6)Bk輸出環(huán)簽名(M,eδ,e,L),其中,L = {B1,B2,…,Bl}.

2.4 簽名驗(yàn)證

驗(yàn)證者收到代理環(huán)簽名(M,eδ,e,L)后,驗(yàn)證下列條件是否成立:

(1)e≠0,eδ≠0,‖eδ‖≤s m′-1,‖e‖≤s m′,

(2)(A1‖A2‖…‖Al)e=0modq,

(3)A0‖H2‖(ID1)‖H2(ID2)‖…‖H2(IDl)eδ=0modq.

若成立,驗(yàn)證者接受(M,eδ,e,L)為有效的代理環(huán)簽名,否則,拒絕.

3 方案分析

3.1 安全性分析

3.1.1 匿名性.

簽名(M,eδ,e,L)是代理環(huán)中的某個(gè)代理人利用格上一個(gè)小基和算法SampleISIS得到的向量.其中,簽名過(guò)程中一個(gè)小基是代理人利用私鑰通過(guò)基擴(kuò)展算法生成的,具有很好的隨機(jī)性,故該小基不會(huì)泄露簽名人任何信息.另外,算法的構(gòu)造是利用抽樣算法SampleISIS得的,所得的結(jié)果(eδ,e)近似服從高斯分布,并沒(méi)有泄露該小基的相關(guān)信息.由于簽名結(jié)果和簽名過(guò)程中小基的這兩個(gè)主要信息都不會(huì)泄露簽名人的任何信息,所以簽名方案滿足匿名性.

3.1.2 不可偽造性.

定理1 基于格上的SIS難題,本研究的代理環(huán)簽名方案滿足存在性不可偽造性

定理的證明分兩部分,一部分是代理環(huán)簽名中eδ的不可偽造性,一部分是代理環(huán)簽名中 e的不可偽造性.下面僅給出第二部分證明,第一部分證明類似.

對(duì)于任意的矩陣,

其中,A1,…,Al∈Zqn×m,0

(1)1≤i≤l,令A(yù)i為代理環(huán)中第i人的公鑰;

(2)l+1≤i≤Q,利用算法TrapGen(1n)輸出(Ai,Si),令A(yù)i為代理環(huán)中第i人的公鑰,Si為代理環(huán)中第i人的私鑰.

將環(huán)成員的公鑰聯(lián)立所得矩陣A1‖A2‖…‖AQ發(fā)給 F.

Hash詢問(wèn).對(duì)于任意的消息 mi,S隨機(jī)選擇ei←Sample D(AR;r),將 yi=AReimodq發(fā)送給F,并將(mi,ei,yi)存儲(chǔ)于列表L1.

簽名詢問(wèn).收到 F的簽名詢問(wèn)(j,mi,Ri),(mi, ei,Ri)若Ri=R,S在列表L1查找(mi,ei,yi),將ei返回給 F,并將(mi,ei,Ri)存儲(chǔ)于列表L2;若 Ri≠R且l+1≤j≤Q,則S在列表L1查找(mi,ei,yi),將δi←Sample ISIS(ARi,ExtBasis(Sj,ARi),yj,r)返回給 F,并將(mi,δi,Ri)存儲(chǔ)于列表L2;若 Ri≠R且1≤j≤l,則S在列表L1查找(mi,ei,yi),任選k∈Ri,將δi←Sample ISIS(ARi,ExtBasis(Sk,ARi), yj,r)返回給 F,并將(mi,δi,Ri)存儲(chǔ)于列表L2.

若 F以ε的概率輸出一個(gè)偽造代理環(huán)簽名(j＊, m＊,R＊,δ＊),若R＊≠R,S放棄;若R＊=R,S在列表L1查找(m＊,e＊,y＊),顯然,y＊= ARe＊= ARδ＊modq,若e＊≠δ＊,則AR(e＊-δ＊)=0modq,‖e＊-δ＊‖≤2r lm,即,e＊-δ＊為SISAR,lm,2r的一個(gè)解.又因?yàn)?R＊=R的概率為,

所以,算法 S解決SISq,lm,2rlm的難題的概率至少為,

3.2 效率分析

令m=cnlogq,其中,c為常數(shù),l為代理環(huán)成員個(gè)數(shù),則本研究所提出的代理環(huán)簽名方案的公鑰長(zhǎng)度、代理成員的私鑰長(zhǎng)度、代理環(huán)簽名長(zhǎng)度如表1所示.

表1 本文代理環(huán)簽名方案的效率分析

由表1可見(jiàn):(1)與一般基于數(shù)論的代理環(huán)簽名相比,本研究提出的方案設(shè)計(jì)中僅僅使用到了小整數(shù)的模加和模乘運(yùn)算,所以方案計(jì)算效率較高;(2)一般的基于身份的簽名方案,需要有可信中心為簽名人生成簽名私鑰,但在本研究的簽名方案中,任何簽名人均可以利用格上基于原像抽樣函數(shù)的算法TrapGen為自己生成簽名密鑰,不需要可信中心;(3)和文獻(xiàn)[10]環(huán)簽名相比,本方案的公鑰長(zhǎng)度、代理成員的私鑰長(zhǎng)度、代理環(huán)簽名長(zhǎng)度更短,整體運(yùn)算效率更高.

4 結(jié) 論

本文利用格上的格基代理算法和原像抽樣函數(shù),在格上構(gòu)造了一個(gè)基于身份的無(wú)可信中心的代理環(huán)簽名方案.基于格上SIS問(wèn)題的困難性,本方案滿足匿名性和不可偽造性,與其他代理環(huán)簽名方案相比,本方案具有在量子計(jì)算環(huán)境下依然安全的優(yōu)點(diǎn).

[1]Shamir A.Identity Based Cryptosystems and Signature Schemes [C]//Advances in Cryptology-Crypto’84.Santa Barbara,USA: Springer-Verlag,1984:48-54.

[2]Mambo M,Usuda K,Okamoto,E.Proxy Signatures for Delegating Signing Operation[C]//Proceedings of the3rd ACM Conference on Computer and Communications Security.New Y ork:ACM Press,1996:48-57.

[3]Rivest R,Shamir A,Tauman Y.How to Leak a Secret Advances in Cryptology[M].Heidelberg:Springer-Verlag,2001.

[4]Zhang F,Naini R S,Lin C Y.New Proxy Signature,Proxy Blind Signature and Proxy Ring Signature Scheme from Bilinear Pairings[C]//Cryptology ePrint Archive Report2003/117.http:// eprint.iacr.org/2003/104/.

[5]楊少春,郎為民.基于身份和雙線性對(duì)的代理環(huán)簽名方案[J].微計(jì)算機(jī)信息,2006,14(12):79-81.

[6]Gentry C,Peikert C,Vaikuntanathan V.Trapdoors for Hard Lattices and New Cryptographic Constructions[C]//STOC’2008. Victoria,Canada:IEEE Press,2008:197-206.

[7]Alwen J,Peikert C.Generating Shorter Bases for Hard Random Lattices[C]//STACS’2009.Freiburg,Germany:IEEE Press, 2009:75-86.

[8]Wang Jin,Sun Bo.Ring Signature Cchemes from Lattice Basis Delegation[J].Information and Communications Security,Lecture,2011,7043(1):15-28.

[9]Peikert C.Bonsai Trees[EB/OL].[2009-07-19].http:// eprint.iacr.org.2009.

[10]王鳳和,胡予濮,王春曉.格上基于盆景樹(shù)模型的環(huán)簽名[J].電子與信息學(xué)報(bào),2010,32(10):2400-2403.