一個基于格的環(huán)簽名方案的改進(jìn)

熱娜·艾合買提,張　娟,李　偉,曾吉文*

(1.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 廈門 361005；2.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆 烏魯木齊 830054)

2001年,Rivest等[1]在群簽名的基礎(chǔ)上提出了環(huán)簽名.它是一種特殊的群簽名,實(shí)現(xiàn)了簽名者的完全匿名性，被廣泛應(yīng)用于網(wǎng)上投票、電子選舉等領(lǐng)域.截止目前,大部分環(huán)簽名方案本質(zhì)上都是基于數(shù)學(xué)中的困難問題假設(shè)[2-4]，安全性很大程度上依賴于安全參數(shù)的選取[5]．并且,基于離散對數(shù)問題的簽名無法抵抗量子攻擊[6].因此,設(shè)計(jì)更加安全的環(huán)簽名方案成為密碼學(xué)發(fā)展的一個重要方向.

一個n維格是Rn上的離散子群,基于格中困難問題(如最短向量問題等)的密碼構(gòu)造可以抵抗量子攻擊.Ajtai等[5，7-9]證明了某些格中困難問題在一般情況和最壞情況下的困難性相當(dāng).因此,在基于格中困難問題的密碼體制中,隨機(jī)挑選實(shí)例[5]與最難實(shí)例的安全性相同.這個重要性質(zhì)是大部分傳統(tǒng)的密碼體制所不具備的.而且,格中涉及的線性運(yùn)算和模運(yùn)算相比傳統(tǒng)密碼的指數(shù)運(yùn)算速度快.

許多人對基于格的環(huán)簽名方案進(jìn)行了研究[10-14].2010年,Cash 等[10]提出了格基派生技術(shù)來為用戶產(chǎn)生公私鑰,并設(shè)計(jì)了第一個基于格的環(huán)簽名方案,但是此方案消息擴(kuò)展較長,不利于實(shí)施.2011 年,Wang 等[11]提出一個新的環(huán)簽名方案,并聲稱他們的方案可以滿足全密鑰暴露下的匿名性和內(nèi)部攻擊下的不可偽造性.然而，該方案在內(nèi)部攻擊條件下不滿足不可偽造性.本研究改進(jìn)了Wang的方案：新方案在隨機(jī)諭言模型下,可以滿足全密鑰暴露下的匿名性和內(nèi)部攻擊下的不可偽造性；并且使用了Micciancio等[15]提出的一種新的陷門生成算法.由于這種新的陷門生成算法在計(jì)算方面簡單、有效、容易實(shí)施,因此本研究的簽名方案和其他方案相比也更高效.

1　預(yù)備知識

本文中系統(tǒng)參數(shù)為n.對任意一個正整數(shù)k,[k] 表示集合{1,2，…，k}.設(shè)矩陣A=[a1，a2，…，am],其中ai表示矩陣A的第i個列向量.‖a‖表示a的歐幾里得范數(shù)，且‖a‖=maxx∈[m]‖ai‖.

1.1　格(Lattice)

一個格是Rn的離散子群,它由Rn中n個線性無關(guān)的向量生成,稱其為基向量.設(shè)B=[b1,b2，…，bn]是n×n矩陣,由n個線性無關(guān)的基(列)向量b1,b2，…，bn組成．那么一個由B生成的n維格Λ定義如下:

Λ=L(B)={Bc:c∈Zn}，

在密碼應(yīng)用中,通常將格(基底)限制到Zn上.

Λ⊥(A)={e∈Zm:Ae=0modq}，

對任何r>0,Rn上中心在c,偏差為r的高斯函數(shù)定義如下[8]:

x∈Rn,ρr,c(x)=exp(-π‖x-c‖2/r2).

對任意c∈Rn,r>0及n維格Λ,Λ上的離散高斯分布定義如下:

x∈Λ,DΛ,r,c=ρr,c(x)/ρr,c(Λ)，

其中ρr,c(Λ)=∑xΛρr,c(x)為固定值.

1.2　格中困難問題假設(shè)

本研究環(huán)簽名方案的安全性依賴于格中SIS問題(small integer solution problem)、ISIS 問題(inhomogeneous small integer solution problem)的困難性,定義如下[5]:

1.3　格的基本算法

本文中使用了Micciancio等[15]在2012年提出的一種新的陷門生成算法:

2)A的分布與均勻之間的統(tǒng)計(jì)距離可忽略.

定義域中取原像算法SampleD(A,T,H,u,s):在給定函數(shù)值時,可以利用陷門信息取樣得到較短的原像[15].

3) SampleD(A,T,u,s)指的是SampleD(A,T,I,u,s).

2)T′的分布與離散高斯分布之間的統(tǒng)計(jì)距離可忽略.

3) 隨機(jī)變換A′的列向量不影響算法的實(shí)施.

4) DelTrap(A′,A,T,s′)指的是DelTrap(A′,A,T,I,s′).

2　環(huán)簽名

2.1　環(huán)簽名的定義

一個環(huán)簽名由3個概率多項(xiàng)式時間算法[4]構(gòu)成:KeyGen,Ringsign,Ringverify.

1) KeyGen(1n):輸入安全參數(shù)n,該算法為每個成員輸出簽名密鑰ski和驗(yàn)證密鑰vki.

2) Ringsign(ski,R,M):輸入環(huán)R,簽名者的私鑰ski,消息M∈{0,1}*,該算法輸出環(huán)R對消息M的簽名v.

3) Ringverify(R,M,v):輸入環(huán)R,消息M及環(huán)簽名v,如果簽名合理,算法回答接受,否則拒絕.

2.2　環(huán)簽名方案的匿名性

一般的環(huán)簽名方案抗全密鑰暴露下的匿名性證明定義如下:

2.3　環(huán)簽名方案的不可偽造性

一般的環(huán)簽名方案在內(nèi)部攻擊下不可偽造證明定義如下:

A在上述游戲中取勝的優(yōu)勢定義如下：

3　本研究提出的方案

H(·,·):{0,1}*×{0,1}m→{0,1}n.

是一個安全的Bash函數(shù).安全性分析時將視H(·,·)為一個隨機(jī)器.為了方便起見,令其中的可逆矩陣H=I.

(ii) 利用算法 DelTrap(AR,Ai,Ti,s′) 派生出AR的陷門TR.

(iii) 利用算法 SampleD(AR,TR,y) 取樣得到v∈ZLm,顯然滿足ARv=ymodq.

(iv) 最后輸出用戶i對消息M的簽名v.

3) Ringverify(R,v,M):給定一個環(huán)R,消息M,簽名v,當(dāng)下述兩個條件滿足時,驗(yàn)證者接受這個簽名:

(ii)ARv=H(R,M) modq.

否則,驗(yàn)證者不接受．

3.1　全密鑰暴露下的匿名性

定理1若將H(·,·)視為一個隨機(jī)諭言模型,假設(shè)ISISq,lm是困難的,則本研究的環(huán)簽名方案在全密鑰暴露下是匿名的.

證明假設(shè)存在一個自適應(yīng)的敵手A攻擊環(huán)簽名方案在全密鑰暴露下的匿名性,挑戰(zhàn)者構(gòu)造一個多項(xiàng)式時間算法C來響應(yīng) A的攻擊環(huán)境.設(shè)A 的詢問次數(shù)是qE.為了響應(yīng)A 的詢問,存儲兩個列表H和K,他們在初始狀態(tài)下都是空的.

2) 詢問階段:C分別回答A的hash詢問、私鑰詢問及簽名詢問如下:其中Ri表示環(huán)R的含有l(wèi)個成員的任一子環(huán),Mj為任一消息．

(ii)Ri中用戶i1的私鑰詢問階段:C查找列表K,返回Ti1給A.

(iii) 詢問環(huán)Ri中的成員i1對消息Mj的簽名〈i1,Ri,Mj〉:可以假設(shè)H(Ri,Mj)已經(jīng)被A詢問過了,C查詢H列表〈Ri,Mj,yij〉得到y(tǒng)ij,執(zhí)行算法 SampleD得到vij,并將vij返回給A.

A發(fā)出挑戰(zhàn)〈k0,k1,R*,M*〉,使環(huán)R*對消息M*簽名,k0,k1是R*中的兩個成員.C選擇b*←{0,1},檢查列表H中元組〈R*,M*,y*〉,運(yùn)行算法DelTrap得到AR*的陷門TR*,然后計(jì)算挑戰(zhàn)簽名v*← SampleD(AR*,TR*,y*),將v*給A,最終A輸出它的猜測b′←{0,1}.

3.2　內(nèi)部攻擊下的不可偽造性

定理2若將H(·,·)視為一個隨機(jī)諭言模型,假設(shè) SISq,lm是困難的,則本研究的環(huán)簽名方案在內(nèi)部攻擊下是安全的.

證明假設(shè)存在一個自適應(yīng)的敵手A攻擊環(huán)簽名方案內(nèi)部攻擊下的不可偽造性,挑戰(zhàn)者構(gòu)造一個多項(xiàng)式時間算法C來模擬A的攻擊環(huán)境,解決SIS問題.設(shè)詢問次數(shù)是qE,A 和C進(jìn)行如下游戲.為了響應(yīng)A的詢問,C存儲兩個列表H和K,他們在初始狀態(tài)下都是空的.

2) 詢問階段:C分別回答A的Hash詢問、私鑰詢問及簽名詢問如下:其中Ri表示環(huán)R的含有l(wèi)個成員的任一子環(huán),Mj為任一消息．

(i) 對H(Ri,Mj)的Hash詢問:C返回一個隨機(jī)值eij←Zlm,服從高斯分布DZlm,r,返回yij←ARteijmodq給A,然后將(Ri,Mj,eij,yij) 存儲在列表中H.

(ii) 對k私鑰詢問:如果k?Rt,C在列表K中尋找〈k,Ak,Tk〉,然后將Tk返回給A.否則中止.

(iii)詢問環(huán)Ri中的成員i1對消息Mj的簽名〈i1,Ri,Mj〉:可以假設(shè)H(Ri,Mj)已經(jīng)被A詢問,如果Ri=Rt,C查找列表H(Ri,Mj,eij,yij),將eij返回給A.若Ri≠Rt,分兩種情況:

情況1:i1∈Ri-Rt,此時〈i1,Ai1,Ti1〉包含在列表K中,那么C運(yùn)行DelTrap算法獲得ARi的陷門TRi←DelTrap(ARi,Ai1,Ti1),檢查H列表中的(Ri,Mj,eij,yij),計(jì)算挑戰(zhàn)簽名vij←SampleD(ARi,TRi,yij),并將vij返回給A.

情況2:i1∈Ri∩Rt,C尋找一個i2∈Ri-Rt,使得〈i2,Ai2,Ti2〉包含在列表K中,運(yùn)行DelTrap算法獲得ARi的陷門TRi←DelTrap(ARi,Ai2,Ti2),C重新在列表H中獲得(Ri,Mj,eij,yij),然后計(jì)算挑戰(zhàn)簽名vij←SampleD(ARi,TRi,yij) 并將vij返回給A.

3) 挑戰(zhàn)階段,A輸出一個偽造〈i*,R*,M*,σ*〉,如果R*≠Rt,C失敗,否則C尋找列表H中的〈R*,M*,e*,y*〉,然后輸出v=σ*-e*,即為 SIS問題實(shí)例fARt的解.

分析:設(shè)敵手A輸出一個合理的偽造的概率是ε,挑戰(zhàn)者C成功解決SIS問題實(shí)例主要取決于私鑰詢問階段和挑戰(zhàn)階段.

(i)在私鑰詢問階段,R中有l(wèi)個成員的私鑰是未知的,被詢問到的概率為1/qE,因此詢問成功即i?Rt,C詢問成功的概率是1-1/qE.

4　結(jié)　論

本文中提出的新的環(huán)簽名方案在隨機(jī)諭言模型下是可以滿足全密鑰暴露下的匿名性和內(nèi)部攻擊下的不可偽造性.而且使用一種強(qiáng)陷門生成算法,保證了新的簽名方案簡單、高效且容易實(shí)施.

參考文獻(xiàn)：

[1]RIVEST R,SHAMIR A,TAUMAN Y.How to leak a sercret[C]∥Proceedings of the ASIACRYPT 2001.Berlin:Springer-Verlag,2001:552-565.

[2]ZENG S,JIANG S,QIN Z.An efficient conditionally anonymous ring signature in the random oracle model[J].Theoretical Computer Science,2012,461:106-114.

[3]SHIM K A.An efficient ring signature scheme from pai-rings[J].Information Sciences,2015,300:63-69.

[4]BENDER A,KATZ J,MORSELLI R.Ring signatures:stronger definitions,and construction without random oracles[J].Journal of Cryptology,2009,22(1):114-138.

[5]AJTAI M.Generating hard instances of lattice problems (extended abstract)[C]∥STOC.Philadelphia:ACM,1996:99-108

[6]SHOR P W.Polynomial-time algorithms from prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal on Computing,1997,26(5):1484-1509.

[7]DWORK C.A public-key cryptosystem with worst-case and/average-case equivalence[C]∥Proceeding of Twenty-ninth ACM Symposium on Theory of Computing.[S.l.]:ACM,1997:284-293.

[8]MICCIANCIO D,ROSEN O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM Journal on Computing,2007,37:267-302.

[9]ALWEN J,PEIKERT C.Generating shorter bases for hard random lattices[J].Theory of Computing Systems,2011,48 (3):535-553.

[10]CASH D,HOFHEINZ D,KILTZ D,et al.Bonsai trees,or how to delegate a lattices basis[J].Eurocrypt,2010,6110:523-552.

[11]WANG J,SUN B.Ring signature schemes from lattice basis delegation[J].Lecture Notes in Computer Science,2011,7043:15-28.

[12]NOH G,CHUNJ Y,JEONG I R.Strongly unforgeable ring signature scheme from lattices in the standard model[J].Journal of Applied Mathematics,2014(2014):1-12.

[13]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C]∥Proceedings of the 40th Annual ACM Symposium on the Theory of computing(STOC′08).[S.l.]:ACM,2008:197-206.

[14]MELCHOR C A,BETTAIEB S,BOYEN X,et al.Adapting Lyubashevsky′s signature schemes to ring signature setting[J].Progress in Cryptology,2013,7918:1-25.

[15]MICCIANCIO D,PEIKERT C.Trapdoors for lattices:simpler,tighter,faster,smaller[J].Lecture Notes in Computer Science,2012,7237:700-718.