一個基于格的環簽名方案的改進

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

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

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

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

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

1　預備知識

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

1.1　格(Lattice)

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

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

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

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

對任何r>0,Rn上中心在c,偏差為r的高斯函數定義如下[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　格中困難問題假設

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

1.3　格的基本算法

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

2)A的分布與均勻之間的統計距離可忽略.

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

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

2)T′的分布與離散高斯分布之間的統計距離可忽略.

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

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

2　環簽名

2.1　環簽名的定義

一個環簽名由3個概率多項式時間算法[4]構成:KeyGen,Ringsign,Ringverify.

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

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

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

2.2　環簽名方案的匿名性

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

2.3　環簽名方案的不可偽造性

一般的環簽名方案在內部攻擊下不可偽造證明定義如下:

A在上述游戲中取勝的優勢定義如下：

3　本研究提出的方案

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

是一個安全的Bash函數.安全性分析時將視H(·,·)為一個隨機器.為了方便起見,令其中的可逆矩陣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):給定一個環R,消息M,簽名v,當下述兩個條件滿足時,驗證者接受這個簽名:

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

否則,驗證者不接受．

3.1　全密鑰暴露下的匿名性

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

證明假設存在一個自適應的敵手A攻擊環簽名方案在全密鑰暴露下的匿名性,挑戰者構造一個多項式時間算法C來響應 A的攻擊環境.設A 的詢問次數是qE.為了響應A 的詢問,存儲兩個列表H和K,他們在初始狀態下都是空的.

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

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

(iii) 詢問環Ri中的成員i1對消息Mj的簽名〈i1,Ri,Mj〉:可以假設H(Ri,Mj)已經被A詢問過了,C查詢H列表〈Ri,Mj,yij〉得到yij,執行算法 SampleD得到vij,并將vij返回給A.

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

3.2　內部攻擊下的不可偽造性

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

證明假設存在一個自適應的敵手A攻擊環簽名方案內部攻擊下的不可偽造性,挑戰者構造一個多項式時間算法C來模擬A的攻擊環境,解決SIS問題.設詢問次數是qE,A 和C進行如下游戲.為了響應A的詢問,C存儲兩個列表H和K,他們在初始狀態下都是空的.

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

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

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

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

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

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

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

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

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

4　結　論

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

參考文獻：

[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.