理想格上基于身份的代理重簽名方案

商玉芳，梁向前，孫意如

山東科技大學 數學與系統科學學院，山東 青島 266590

理想格上基于身份的代理重簽名方案

商玉芳，梁向前，孫意如

山東科技大學 數學與系統科學學院，山東 青島 266590

代理重簽名作為密鑰管理的一個重要工具，它不僅能夠簡化密鑰管理、簡化證書管理，還能夠提供路徑證明等功能。目前，針對基于大整數分解與離散對數的困難問題，在量子環境下代理重簽名方案的不安全性，有人提出了一種能夠抵抗量子攻擊的代理重簽名。利用理想格，以及基于理想格上的小整數解的困難性，構造了理想格上基于身份的代理重簽名方案，該方案與其他的具有相同性質的基于身份的代理重簽名方案相比，具有較短的簽名和公鑰、運算復雜度降低的優點。

代理重簽名；理想格；小整數解問題

1 引言

代理重簽名的概念最早于1998年在歐密會上由Blaze，Bleumer等人[1]提出。在代理重簽名方案中，Alice和Bob之間存在著一個半可信的代理者，作為他們兩者之間的轉換者，即代理者能夠把一個消息m在Alice下的簽名轉換為Bob在同一消息m上的簽名，同時，代理者擁有一個重簽名秘鑰，并且由Alice和Bob的私鑰生成，但是，代理者不能代理Alice或Bob在任一消息上進行簽名，因為代理重簽名相當于一個變換函數，它具有很多的應用場景，如簡化秘鑰管理、提供路徑證明、透明認證等。

自 2005 年以來，Ateniese[2]，Libert[3]，Schnorr[4]，Shao[5]等人對文獻[1]方案進行了深入分析之后，分別給出了代理重簽名的新的形式化定義和安全模型，在標準模型下可證明安全的代理重簽名方案，以及構造了第一個基于身份的單項代理重簽名方案等。近幾年來隨著量子計算機的出現，對于傳統一些基于有限域上的困難假設的密碼學方案，證實了他們不能夠有效地抵抗量子計算機的攻擊，由于格密碼是一類抗量子計算機的密碼體制，因此，在格上構造簽名方案成為一個新的研究熱門方向。2010年，Ruckert等人[6]在隨機預言機模型和標準模型下分別構造了基于格困難問題的基于身份的方案，2012年，Daniele Micciancio和Chris Peikert[7]提出了新的格陷門生成算法，而且提出了一個基于格的強不可偽造的簽名方案。2014年，Ducas等人[8]根據文獻[9]提出了格陷門生成算法，利用理想格，提出了一個相對較短的簽名方案。2015年楊丹婷等人[10]提出了一個理想格上基于身份的簽名方案。

本文利用文獻[7]理想格上特殊的代數結構，構造了具有不可偽造性的基于身份的代理重簽名方案，該方案的安全性是基于小整數解的困難問題，與其他基于身份的簽名方案相比，具有強不可偽造性、相對較短的公鑰和簽名長度。

2 預備知識

2.1 格

定義1[11]格是Rm中一類具有周期性結構離散點的集合。嚴格的說格是m維歐式空間Rm的n(m＞n)個線性無關的向量組b1,b2,…,bn∈Rn的所有整系數的線性組合，即

這里b1,b2,…,bn∈Rn構成了格Λ的一組基。

注：同一個格可以用不同的格基來表示，在上面的定義中，m為格的維數，n為格的秩，若滿足m=n，則稱為滿秩格。該文主要關注的是整數格，即Λ∈Zm。

定義2[11]設q是一個素數，A∈Zqn×m，u∈Zqn，兩個整數格 Λ⊥q(A )和 Λuq(A)分別定義為：

有定義知Λuq(A )=Λ⊥q(A )+s，其中 s∈Λuq(A)。

2.2 理想格

定義3[7]環Zn的理想I又是格Zn的子格，稱這個子格為格Zn的理想格。具體定義如下：多項式環若滿足以下三條性質：

（1）f(x)的首項（最高次的項）系數為1。

（2）在Z上是不可約的。

（3）對環 Z[x]上的任意多項式 f(x)和g(x )，都有

||g(x)h(x)modf(x)||＜ poly(n)||g(n)||?||f(x)||成立，則稱環的理想為 f()x-理想格，有時也簡寫為I。

本文所考慮的格問題都局限于理想格，而且所研究的結論適應于任意分圓環的理想格，所使用環的形式為?=Z[x]/(Φ2n(x))或 ?q=(?/q?)，其中 q=3k∈Z ，n是2的冪次方，Φ2n=Xn+1是分圓多項式。

2.3 格上的困難問題及離散高斯分布

定義4[12]（SISq,n,m,β小整數解問題）給定一個矩陣A∈Zn×mq，q為整數，β為大于零的實數，求解一個非零向量v，滿足 Av=0modq且||v||≤β，其中v∈Λ⊥q()A。

定義5[9]（RingSISq,n,m,β環上小整數解問題）給定行向量 A∈?l×mq、q為整數、β為大于零的實數，求解一個非零向量v，使得v∈Λ⊥q()A ，并且滿足||v||≤β。

定義6[13]（高斯函數）對任意的n維格Λ、向量c∈Rn和實數s＞0，定義Rn上的高斯函數為：

其中，對任意的x∈Rn，c為中心，s為標準差。如果下標c，s為0時，可省略不寫。

定義7[13]（高斯分布）格Λ上的離散高斯分布為：對任意的n維格Λ、向量c∈Rn和實數s＞0，有

同高斯函數的定義下標s，c也可省略不寫。

定義8[12]（格陷門）設A∈Zn×mq，G∈Zn×wq，可逆矩陣 H∈，其中，m＞w＞n，若滿足則稱R∈為A的一個G-陷門。

2.4 相關定理

定理1[14]存在一個概率多項式時間算法TrapGen(q,n)，設 q≥3是一個奇數，且 m=6nlbq，則輸出兩個矩陣 A∈和T∈，A在上是接近于均勻的，T是格Λ⊥q(A)的一組基，除了一個可忽略的概率外，且和 ||T||≤Ο((nlbq))同時成立，其中，‖‖?表示為歐幾里德范數。

定理2[8]設q≥2，矩陣 A∈Zn×mq，m＞n，T 是格ΛΛq(A)的一組基，，那么對于c∈Rm,u∈Znq有：

（2）存在一個概率多項式時間算法Samplepre(A,T,u,σ)，抽取一個Λuq(A)中的向量 x，使得 x的分布統計接近于 DΛuq(A),σ,c。

定理3[11]存在一個有效的多項式算法SampleD(A,u,R,s)，輸入矩陣 A∈，u∈?q，可逆標記H∈?對應 A的一個G-陷門R∈和參數s1(R )，輸出一個與分布統計上相近的抽樣。

定理4[11]設，且，則s1()R ≤s?以壓倒性優勢的概率成立。

定理5[10]存在一個陷門委托算法DelTrap(A′=[A |A1],H ′,s′)，輸入矩陣逆矩陣，參數 s′≥η(Λ)，其中 Λ=Λ⊥(A)，輸出矩陣 A′的陷門

定理 6[12]設是 [A ,A]的G-陷門，

i，標記 Hi∈?q，則對ci∈?q，任意的線性組合的G-陷門，其中標記

定理7[12]（最小熵）設，以極大的概率選擇 A，且A←Uw，若從 D?,s中獨立隨機選取 xi(i=1,2,…,w)，則對任意的非零向量v∈?w{0} 的最小熵為，所以的概率是小于Ω(n)的。

定理8[12]（左基取樣）存在一個多項式時間算法SampleBasisLeft(A,M,TA,0,σ)，輸入矩陣 A、M ，M∈，格 Λ⊥q(A)的一組短基TA，輸出格的 一 組 短 基 TF1，其 中 F2=A|M ，

3 基于身份的代理重簽名的一般模型

基于身份的代理重簽名一般模型由以下多項算法KeyGen，Extract，Rekey，Sign，Resign，Verify組成：

（1）KeyGen(1n)：輸入一個安全參數n，輸出該方案的公共參數 pp和主密鑰msk。

（2）Extract(pp,msk,id)：輸入一個安全參數 pp，主密鑰msk和用戶身份id，運用私鑰提取算法輸出id的私鑰。

（3）Rekey(p kA,skB)：輸入用戶A的公鑰的 pkA，用戶B的私鑰skB，運用重簽名密鑰生成算法，輸出用戶A和B之間的重簽名秘鑰rkA→B。

（4）Sign(p p,skid,m ) ：輸入安全參數 pp，私鑰skid以及消息m，運用簽名算法輸出消息m的簽名σ。

（5）Resign(r kA→B,pkA,m,σ) ：輸 入 重 簽 名 密 鑰rkA→B，消息m，用戶A的公鑰 pkA以及用 pkA來驗證m的簽名σ，運用重簽名算法輸出消息m的簽名σ′。

（6）Verify(p p,pkB,m,σ′)：輸入安全參數 pp，用戶B的公鑰 pkB，消息m以及重簽名σ′，驗證重簽名算法是否是合法簽名，如果是則接受，否則拒絕。

4 方案介紹

（1）KeyGen(1n)：輸入安全參數n，算法如下：

② 隨機選擇向量Ai,Bj(0 ≤i≤1),(0 ≤j≤d )，l為用戶身份的長度，d為消息的長度，以及

③ 輸出pp=(A0,A1,…,Al,B1,B2,…,Bd,U,v )公共參數及主密鑰Msk=T。

（2）Extract( )pp,Msk,id ：輸入公共參數 pp，用戶身份id及主密鑰T。

（3）Rekey(FidA,FidB,rkA→B)：輸入用戶 A的公鑰FidA，用戶B的公鑰FidB及私鑰RidB。

①設用戶FidA=( )a11,a12,…,a1n

T，對任意的b1i∈?q，i=1,2,…,n 。

②根據定理2，運行原像抽樣算法Samplepre(FidB,RidB,a1i,σ)，抽取向量 δi，使得 FidBδi=a1imodq 且||δi||≤，令SidA-idB=( )δ1,δ2,…,δm，FidBSidA-idB=Fmodq，且滿足輸出重簽名密鑰 rkidA→idB=

（4）Sign(p p,skid,m )：輸入公共參數 pp，私鑰skid，消息m∈(0 ,1)nk∈?kq。

①隨機選取向量r∈{0 ,1}nk和標記T，計算：

以及u=Uu+v∈?q，其中參數U∈?l×kq,v∈?q。

② 由定理3，運行 SampleD( )Fid,u,R,s算法，，輸出一個與DΛ⊥u(Ai)?s分布統計上相近的抽樣，輸出用戶A對消息m的簽名σ=(i dA,eidA,t)。

（5）Resign(r kA→B,FidA,m,σ) ：輸 入 重 簽 名 密 鑰rkA→B=SidA-idB，用戶A及其公鑰FidA，消息m和用戶A對消息m簽名σ=(i dA,eidA,t)。

①代理者首先驗證用戶A對消息m簽名的正確性，即 FidAeidA=umodq 且是否同時成立。

②若上式成立，則利用代理重簽名密鑰計算重簽名eidB=SidA-idBeidA，即輸出用戶 A→B的重簽名為σ′=(i dB,eidB,t)。

（6）Verify(p p,FidB,m,t)：輸入公共參數 pp，用戶B的公鑰FidB，消息m和用戶 A→B對應的重簽名σ′=(i dB,eidB,t)。

利用計算出的Fid,Ft及t，驗證如果滿足同時成立，則接受重簽名σ′，否則拒絕。

5 方案的安全性分析

定理9在隨機預言機模型下，本文基于身份的代理重簽名方案是在環上的小整數解問題(R ingSISq.n.m.β)的困難假設下的，其中，假設存在一個概率多項式時間敵手A在進行了至多M 次的詢問，ε≥2-Ο(n)，且 1≤M≤2Ο(n)，當 敵 手 A進 行S次 詢 問 時 ，S∈{ }

0,1,…,M-1，在運行時間T內，以概率ε攻破該方案，構造了一個算法 B，則利用敵手 A以概率來解決RingSISq.n.m.β困難問題。

證明 以下證明過程包括6部分（證明過程可部分參考文獻[12]和文獻[13]）。

（1）參數生成：敵手A將(i d ′,m(1),m(2),…,m(p))發送給模擬者 B，id′為目標身份且id′=(b ′1,b′2,…,b′l) ∈(0 ,1)l，m(1),m(2),…,m(p)為 p個選擇的消息。

（2）私鑰提取詢問：當敵手A詢問用戶身份id的私鑰時，且 id≠id′，模擬 B將計算用戶公鑰 Fid=，通過運行左基取樣算法，R←將產生的私鑰R發送給敵手A。

（3）重簽名密鑰詢問：當敵手A對身份(i dA,idB)進行重簽名密鑰詢問時，若idA=idB時，詢問停止，否則，模擬者B計算重簽名密鑰rkidA→B，首先利用用戶A的公鑰FidA和用戶B的公私鑰對(FidB,RidB)，以及重簽名密鑰生成算法生成的重簽名密鑰rkidA→idB=SidA-idB，使得AidBSidA-idB=AidAmodq并發送SidA-idB給敵手A。

（4）簽名詢問：模擬者 B 首先根據 id′=(b′1,b′2,…,b′l)目標身份產生公開參數 A0,A1,…,Al,i=0,1,…,l，令 Ai=EiG-A0Ri，Ri為 [A0,Ai]的一個G-陷門 且Ri∈ ?lq×

w因為g為一個環同態[7]，Ei表示為：

分析可得以下結論:

①當id=id′時：

②當id≠id′時：

同樣令 A′=E′iG-A0R′i，R′i為 [A0,A′i] 的一個G-陷門且 R′i∈ ?lq×w。再根據消息m(1),m(2),…,m(p)生成公開參數B0,B1,…,Bd（下面計算過程可參考文獻[51]）當模擬者B計算串q∈{0 ,1}≤d的集合Q時，d為消息m(i)，i∈{0 ,1,…,p}的長度，且有|Q|=(d -1) p+1，q不是任意消息m(i)的前綴，則選擇任意的q∈Q且記γ=|q|≤d ，其中 E′i表示如下：

通過分析得出結論：

①對任意消息m不以q為γ位前綴時，而是以φ為γ位前綴時：

所以利用多項式算法SampleD產生id′在消息m上的簽名，最后將簽名發送給敵手A。

（5）重簽名詢問：當敵手A詢問用戶身份id(i d ≠id′)在消息m上的重簽名，模擬者B首先對消息m上的簽名σ進行驗證。若Verify( )pk,m,σ=1成立，則利用重簽名密鑰計算出重簽名σ′，并發送σ′給敵手A。

（6）偽造階段：敵手A對消息m′進行偽造簽名，對每個消息m(j)，當模擬者B隨機選取t(j)∈T，如果前綴發生碰撞，有且j≠s，則模擬者發生的概率至多為否則，當模擬者B隨機選擇一個前綴B希望有t≤?γ=t′≤γ，敵手輸出偽造簽名 σ′=(id′,e′,t′)，由于敵手認為t≤?γ∈Tγ是獨立選取的，故t≤?γ=t′≤γ發生的概率為1|Tγ|。故若不是，則中止模擬。

設 v=Ft′e′-U ?u′,則有Ft′e′=U ?u′+v。

令 Ft??e?=U?u?+v 對任意的，當時F=[A |-AR|E′G-AR′]，有 E=E=0t00id′t0t?t′以及 RU←D?,σ′,U=A0Ru則有：

由以上分析可得A0φ=0，下面令：

可知ψ≠0且很小（根據文獻[8]可知）ψ=0的概率是小于 2-Ω(n)，由于 σ?，σ′是有效的簽名且 ||σ?||,||σ′||≤，此外，對于任意的標記，所以可得到

6 效率分析

本文提出的基于身份的代理重簽名方案，較好地利用了理想格所特有的結構，使其具有較高的運算效率，減少了運算的復雜度，所以該方案要比其他同類的基于身份的方案的運算速度快得多。在本方案中，使用了Hash函數運算，以及陷門委托算法、原像抽樣算法，下面是將本文方案與基于相同性質的文獻的方案進行比較，分析結果如表1。

表1 方案的效率對比

7 結論

本文利用理想格，構造了一個新的在標準模型下給出安全性證明的基于身份的代理重簽名方案，該方案的安全性基于環上的小整數解困難問題，即在RingSIS假設下，該方案滿足不可偽造性，與其他的基于身份的簽名方案相比，充分地利用了理想格中的特殊的代數結構，構造的簽名方案具有較短的簽名和相對較短的私鑰長度，降低了運算復雜度，提高了運算效率。

[1]Blaze M，Bleumer G，Strauss M.Divertible protocols and atomic proxy cryptography[J].Lecture Notes in Computer Science（LNCS），1998，1403：127-144.

[2]Ateniese G，Hohenberger S.Proxy re-signatures：new definitions，algorithms，and applications[C]//ACM Conference on Computer and Communications Security，Alexandria，VA，USA，2005：310-319.

[3]Libert B，Vergnaud D.Multi-use unidirectional proxy resignatures[C]//ACM Conferenceon Computerand Communications Security，Alexandria Virginia，USA，2008：511-520.

[4]Schnorr C P.Efficient identification and signatures for smartcards[J].Lecture Notes in ComputerScience（LNCS），1990，435：688-689.

[5]Shao Jun，Feng Min，Zhu Bin，et al.The security model of unidirectional proxy re-signature with private re-signature key[J].Lecture Notes in Computer Science（LNCS），2010，6168：216-232.

[6]Rückert M.Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[C]//Post-Quantum Cryptography.Berlin Heidelberg：Springer，2010：182-200.

[7]Micciancio D，Peikert C.Trapdoors for lattices：Simpler，tighter，faster，smaller[C]//Advances in Cryptology—EUROCRYPT 2012.Berlin Heidelberg：Springer，2012：700-718.

[8]Ducas L，Micciancio D.Improved short lattice signatures in the standard model[C]//Advances In Cryptology-CRYPTO 2014.Berlin HeidelbErg：Springer，2014：335-352.

[9]賽煒，胡予濮.基于理想格的公鑰密碼中模多項式的應用研究[D].西安：西安電子科技大學，2014，1：10-11.

[10]Yang D T，Xu C G，Xu L，et al.Identity-base signature scheme over ideal lattices[J].Journal of Cryptologic Research，2015，2（4）：306-316.

[11]Alwen J，Peiker C.Generating shorter bases for hardrandom lattices[C]//The 26th International Symposium on Theoretical Aspects of Computer Science，Freiburg，Germany，2009：535-553.

[12]Gentry C，Peikert C，Vaikuntanathan V.Trapdoors for hard lattices and new cryptographic constructions[C]//Symposium on Theory of Computing 2008，Victoria，British Columbia，Canada，2008：197-206.

[13]李明祥，劉陽，趙秀明.高效格上的基于身份的簽名方案[J].計算機應用研究，2014，3（3）：825-828.

[14] 王小云，劉明潔.格密碼學研究[J].密碼學報，2014，1（1）：13-27.

[15]Cash D，Hofheinz D，Kiltz E，et al.Bonsai tree，or how to delegate a lattice basis[C]//Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques，2010：523-552.

SHANG Yufang,LIANG Xiangqian,SUN Yiru

College of Mathematics and Systems,Shandong University of Science and Technology,Qingdao,Shandong 266590,China

Identity-based proxy re-signature over ideal lattice.Computer Engineering and Applications,2017,53（21）：110-114.

As an important tool of key management,the proxy re-signature scheme can not only simplify the secret key management and certificate management,but also can be used to provide certificate path and so on.Currently,for the difficulty of integer factorizating and logarithm discretization and the insecurity of proxy re-signature schemes in the quantum environments,a proxy re-signature scheme that can resist the attack of quantum has been presented in the literature.The first identity-based proxy re-signature scheme over ideal lattice is constructed in this paper,by using ideal lattice and based on the difficulty of the Small Integer Solution（SIS）problem.Compared with other proxy re-signature scheme that has the same properties,this has a shorter signature,and public key,and the advantage of decreasing the computational complexity.

proxy re-signature;ideal lattice;Small Integer Solution（SIS）problem

A

TN91

10.3778/j.issn.1002-8331.1605-0428

國家自然科學基金（No.61402265，No.61170054）。

商玉芳（1990—），女，碩士研究生，主要研究領域為信息安全理論與應用；梁向前（1969—），男，博士，副教授，主要研究領域為信息安全，E-mail：liangxq87@126.com；孫意如（1991—），女，碩士研究生，主要研究領域為信息安全理論與應用。

2016-05-31

2016-07-05

1002-8331（2017）21-0110-05

CNKI網絡優先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.2047.064.html