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

歐海文 范 禎 蔡斌思 楊明曌

1(北京電子科技學(xué)院 北京 100071) 2(西安電子科技大學(xué) 陜西 西安 710071)

0 引 言

隨著網(wǎng)絡(luò)的快速發(fā)展，為了提高認(rèn)證的性能，數(shù)字簽名應(yīng)運(yùn)而生。自1976年，Diffie等[1]第一次提出數(shù)字簽名的概念,到1978年，Rivest等[2]提出基于大整數(shù)分解的RSA簽名,隨后數(shù)字簽名進(jìn)入快速發(fā)展的階段，各種基于大整數(shù)因子分解和離散對(duì)數(shù)的數(shù)字簽名方案被提出。1984年 Shamir[4]提出基于身份的簽名IBS(Identity-Based Signature)后，相繼出現(xiàn)了很多使用雙線性對(duì)基于身份的數(shù)字簽名方案 ，該類簽名方案可以將用戶的身份等信息作為公鑰，對(duì)簽名的信息進(jìn)行驗(yàn)證。1996年，Mambo等[3]提出代理簽名，該類簽名方案中，原始簽名者A在不將其私鑰給他人的情況下，將其數(shù)字簽名權(quán)利委托給代理簽名者B，則B可以代替A進(jìn)行簽名，這樣的方案應(yīng)該滿足不可偽造性、可驗(yàn)證性、可區(qū)別性等。

但是隨著量子計(jì)算機(jī)和量子算法的出現(xiàn)，人們發(fā)現(xiàn)大整數(shù)分解和離散對(duì)數(shù)問題可以在多項(xiàng)式時(shí)間內(nèi)被量子計(jì)算機(jī)[5]解決，與數(shù)論困難問題不同的是格困難問題被認(rèn)為是可以抵抗量子攻擊，而且是后量子密碼中最具有潛力的一類，所以構(gòu)造基于格困難問題的代理簽名方案是必不可少的。2012年Micciancio等[6]提出了新的格陷門生成算法，而且將其運(yùn)用在簽名方案中。2014年，Ducas等[7]在文獻(xiàn)[6]的前提下，在標(biāo)準(zhǔn)模型下利用理想格提出了一個(gè)短的格簽名；同年，李明祥等[12]構(gòu)造了格上基于身份的簽名方案。2015年,San等[14]提出可基于理想格的群簽名方案, 同年，楊丹婷等[13]提出了理想格上基于身份的簽名方案。2016年，孫意如等[15]提出理想格上基于身份的環(huán)簽名方案。本文利用文獻(xiàn)[7]中的理想格特殊的代數(shù)結(jié)構(gòu)上的陷門技術(shù)，構(gòu)造了一個(gè)基于身份的代理簽名方案，使得密鑰相對(duì)較小，提升了運(yùn)算效率。

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

在本節(jié)中，我們給出一些相關(guān)的定義和定理。

1.1 格和環(huán)

定義1設(shè)b1,b2,…,bm是Rn上m個(gè)線性無關(guān)的向量，則b1,b2,…,bm的所有整系數(shù)的線性組合構(gòu)成的集合稱為格，記作：

Λ=L(b1,b2,…,bm)={Σxibi|xi∈Z}

式中：b1,b2,…,bm稱作一組格基，m稱為格的秩，n稱為格的維數(shù)。如果定義一個(gè)n×m的矩陣Bn×m=(b1,b2,…,bm)，也可以定義該格為Λ=L(B)={Bx|x∈Zm}。如果n=m，稱該格為滿秩格，一般格和滿秩格的性質(zhì)是一樣的。

定義2兩種特殊的模q整數(shù)格：

Λq(A)={x∈Zm|x=AΤemodq，e∈Zn}

1.2 SIS問題

格上的困難問題有很多種，但這里主要介紹以下困難問題。

1.3 格上的高斯分布

定義5以c為中心，方差參數(shù)是s的n維高斯函數(shù)為

式中：?x∈n，s∈。

定義6以向量c>0為中心，實(shí)參數(shù)為s>0可以定義n維格Λ的離散高斯分布為:

式中，?x∈Λ。

定理1[6]對(duì)于任意格Λ(假設(shè)是n維格)上的光滑參數(shù)都有:

1.4 主要定理和算法

算法1[6]TrapGen(A′,H,s)(陷門生成算法)

當(dāng)w≥2logq+2時(shí)，A′極大的概率是從均勻分布中選取的，而且A″在統(tǒng)計(jì)上也是接近均勻分布。當(dāng)A′可以隨機(jī)選取時(shí)，算法可以簡寫為TrapGen(w,H,s)，該算法是隨機(jī)生成的。

算法2[7]SampleD(A,u,R,s)(原像取樣算法)

算法3[6]DelTrap(A′=[A|A1],H′,s′) (陷門委托算法)

定理3[7]環(huán)R上任意一個(gè)元素r，都有s1(r)≤‖r‖1=∑|ri|。

2 簽名方案

(1) 主密鑰生成

① 運(yùn)行算法TrapGen(w,I,σ) ，得到隨機(jī)矩陣A∈R1×m和R∈Rw×k，使得R是A的G-陷門。

② 隨機(jī)選取矩陣:

A0,A1,…,Al,B0,B1,…,Bd∈R1×k，v∈Rq。

③ 主私鑰是R，公布主公鑰是:

pk={A,A0,A1,…,Al,B0,B1,…,Bd,v}。

(2) 用戶私鑰提取

① 利用主公鑰和身份信息IDA,IDB，計(jì)算

式中：IDA=(a1,a2,…,al),IDB=(b1,b2,…,bl)∈{0,1}l。

(3) 代理授權(quán)

① 原始簽名者A根據(jù)自己的需求生成授權(quán)證書W，其中可以包含原始簽名人身份信息、代理者的身份信息、代理授權(quán)期限、代理授權(quán)范圍等內(nèi)容，根據(jù)自身需求添加。

② 計(jì)算c=H2(IDA,IDB,W)，y=H1(W)。

④ 計(jì)算S=xc。

⑤ 將(W,S)公開發(fā)布。

(4) 授權(quán)驗(yàn)證和代理簽名密鑰的生成

② 如果授權(quán)成功，代理者B計(jì)算

③ 利用代理者B的私鑰RB通過添加零行可得到矩陣B′的陷門R′。那么代理簽名的密鑰為(B′,R′)。

(5) 代理簽名

③ 輸出(s′,e)即為代理簽名。

(6) 驗(yàn)證

3 方案的分析

3.1 正確性分析

3.2 方案效率分析

本文方案與一般格上代理簽名方案的代理授權(quán)方式不同，需要用到兩個(gè)的Hash函數(shù)的和一次SampleD算法。代理密鑰的生成過程只需要簡單的矩陣間的線性運(yùn)算，不用耗費(fèi)太多時(shí)間。簽名階段進(jìn)行了一次SampleD算法，計(jì)算一次Hash函數(shù)，減小了運(yùn)算復(fù)雜度。而且利用了理想格的特殊結(jié)構(gòu)，與同類的其他方案相對(duì)比，公私鑰的長度相對(duì)變短，且簽名僅是m+2k維的單個(gè)向量，從而提升了運(yùn)算效率。

3.3 方案安全分析

命題1原始簽名者A對(duì)代理者B的授權(quán)認(rèn)證不能被偽造。

證明假設(shè)授權(quán)合法的情況下，敵手C可以利用算法D在選擇身份和固定選擇消息攻擊下以不可忽略的概率偽造代理簽名，其優(yōu)勢(shì)至少是δ。即算法模擬者可以利用C的偽造解決RingSIS問題。

是可逆的。

其他代理簽名詢問：首先進(jìn)行代理密鑰提取詢問，將RB*通過添加零行得到B′的陷門R′，再利用其對(duì)消息進(jìn)行簽名。

B′*e*=B′*e′=u

A[Im|-RB*|-R′](e′-e*)=0

4 結(jié) 語

本文提出了一個(gè)基于身份的代理簽名方案，與以往的該類簽名方案相比，使得授權(quán)方式更簡單。而且利用了理想格的特點(diǎn)，明顯減小了密鑰大小，代理簽名相對(duì)較短，降低了計(jì)算復(fù)雜度，提升了運(yùn)算效率。任何人都可以對(duì)該代理授權(quán)行為進(jìn)行認(rèn)證。代理簽名的密鑰生成既要利用原始簽名者A的私鑰，還要利用代理者的私鑰才能生成，所以防止了原始者偽造和代理簽名者的偽造，而且證明了其在選擇消息攻擊下的強(qiáng)不可偽造性。

[1] Diffie W, Hellman M E. New directions in cryptography[J].IEEE Transactions on Information Theory, 1976,22(6):644-654.

[2] Rivest B R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[C]//Communications of the ACM,1978.

[3] Mambo M, Usuda K, Okamoto E. Proxy Signatures: Delegation of the Power to Sign Messages (Special Section on Information Theory and Its Applications)[J].Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 1996, E79-A(9):1338-1354.

[4] Shamir A. Identity-Based Cryptosystems and Signature Schemes[M]//Advances in Cryptology. Springer Berlin Heidelberg, 1984:47-53.

[5] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Siam Journal on Computing, 1996, 41(2):303-332.

[6] Micciancio D, Peikert C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[M]//Advances in Cryptology-EUROCRYPT 2012. Springer Berlin Heidelberg, 2012:700-718.

[7] Ducas L, Micciancio D. Improved Short Lattice Signatures in the Standard Model[M]//Advances in Cryptology-CRYPTO 2014. Springer Berlin Heidelberg, 2014:335-352.

[8] Lyubashevsky V. Lattice signatures without trapdoors[C]//Proceedings of the 31st Annual international conference on Theory and Applications of Cryptographic Techniques. Springer-Verlag, 2012:738-755.

[9] Micciancio D, Regev O. Worst-Case to Average-Case Reductions Based on Gaussian Measures[C]//IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 2004:372-381.

[10] Lyubashevsky V, Peikert C, Regev O. On Ideal Lattices and Learning with Errors over Rings[J].Journal of the Acm, 2013,60(6):43.

[11] 江明明, 胡予濮, 王保倉,等. 格上的高效代理簽名[J]. 北京郵電大學(xué)學(xué)報(bào), 2014, 37(3):89-92.

[12] 李明祥, 劉陽, 趙秀明. 高效的格上基于身份的簽名方案[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(3):825-828.

[13] 楊丹婷, 許春根, 徐磊,等. 理想格上基于身份的簽名方案[J]. 密碼學(xué)報(bào), 2015, 2(4):306-316.

[14] Ling S, Nguyen K, Wang H. Group Signatures from Lattices: Simpler, Tighter, Shorter, Ring-Based[C]//Public-Key Cryptography,2015:427-449.

[15] 孫意如, 梁向前, 商玉芳. 理想格上基于身份的環(huán)簽名方案[J]. 計(jì)算機(jī)應(yīng)用, 2016,36(7):1861-1865.