商玉芳，梁向前，孫意如

山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590

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

商玉芳，梁向前，孫意如

山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590

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

代理重簽名；理想格；小整數(shù)解問題

1 引言

代理重簽名的概念最早于1998年在歐密會(huì)上由Blaze，Bleumer等人[1]提出。在代理重簽名方案中，Alice和Bob之間存在著一個(gè)半可信的代理者，作為他們兩者之間的轉(zhuǎn)換者，即代理者能夠把一個(gè)消息m在Alice下的簽名轉(zhuǎn)換為Bob在同一消息m上的簽名，同時(shí)，代理者擁有一個(gè)重簽名秘鑰，并且由Alice和Bob的私鑰生成，但是，代理者不能代理Alice或Bob在任一消息上進(jìn)行簽名，因?yàn)榇碇睾灻喈?dāng)于一個(gè)變換函數(shù)，它具有很多的應(yīng)用場景，如簡化秘鑰管理、提供路徑證明、透明認(rèn)證等。

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

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

2 預(yù)備知識(shí)

2.1 格

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

這里b1,b2,…,bn∈Rn構(gòu)成了格Λ的一組基。

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

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

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

2.2 理想格

定義3[7]環(huán)Zn的理想I又是格Zn的子格，稱這個(gè)子格為格Zn的理想格。具體定義如下：多項(xiàng)式環(huán)若滿足以下三條性質(zhì)：

（1）f(x)的首項(xiàng)（最高次的項(xiàng)）系數(shù)為1。

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

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

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

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

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

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

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

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

其中，對任意的x∈Rn，c為中心，s為標(biāo)準(zhǔn)差。如果下標(biāo)c，s為0時(shí)，可省略不寫。

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

同高斯函數(shù)的定義下標(biāo)s，c也可省略不寫。

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

2.4 相關(guān)定理

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

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

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

定理3[11]存在一個(gè)有效的多項(xiàng)式算法SampleD(A,u,R,s)，輸入矩陣 A∈，u∈?q，可逆標(biāo)記H∈?對應(yīng) A的一個(gè)G-陷門R∈和參數(shù)s1(R )，輸出一個(gè)與分布統(tǒng)計(jì)上相近的抽樣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 方案介紹

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

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

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

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

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

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

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

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

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

①隨機(jī)選取向量r∈{0 ,1}nk和標(biāo)記T，計(jì)算：

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

② 由定理3，運(yùn)行 SampleD( )Fid,u,R,s算法，，輸出一個(gè)與DΛ⊥u(Ai)?s分布統(tǒng)計(jì)上相近的抽樣，輸出用戶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)。

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

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

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

利用計(jì)算出的Fid,Ft及t，驗(yàn)證如果滿足同時(shí)成立，則接受重簽名σ′，否則拒絕。

5 方案的安全性分析

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

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

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

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

（2）私鑰提取詢問：當(dāng)敵手A詢問用戶身份id的私鑰時(shí)，且 id≠id′，模擬 B將計(jì)算用戶公鑰 Fid=，通過運(yùn)行左基取樣算法，R←將產(chǎn)生的私鑰R發(fā)送給敵手A。

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

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

w因?yàn)間為一個(gè)環(huán)同態(tài)[7]，Ei表示為：

分析可得以下結(jié)論:

①當(dāng)id=id′時(shí)：

②當(dāng)id≠id′時(shí)：

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

通過分析得出結(jié)論：

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

所以利用多項(xiàng)式算法SampleD產(chǎn)生id′在消息m上的簽名，最后將簽名發(fā)送給敵手A。

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

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

設(shè) v=Ft′e′-U ?u′,則有Ft′e′=U ?u′+v。

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

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

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

6 效率分析

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

表1 方案的效率對比

7 結(jié)論

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

[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，F(xiàn)eng 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]賽煒，胡予濮.基于理想格的公鑰密碼中模多項(xiàng)式的應(yīng)用研究[D].西安：西安電子科技大學(xué)，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，F(xiàn)reiburg，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].計(jì)算機(jī)應(yīng)用研究，2014，3（3）：825-828.

[14] 王小云，劉明潔.格密碼學(xué)研究[J].密碼學(xué)報(bào)，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

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

商玉芳（1990—），女，碩士研究生，主要研究領(lǐng)域?yàn)樾畔踩碚撆c應(yīng)用；梁向前（1969—），男，博士，副教授，主要研究領(lǐng)域?yàn)樾畔踩?，E-mail：liangxq87@126.com；孫意如（1991—），女，碩士研究生，主要研究領(lǐng)域?yàn)樾畔踩碚撆c應(yīng)用。

2016-05-31

2016-07-05

1002-8331（2017）21-0110-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.2047.064.html