具有消息恢復(fù)功能的格身份簽名方案*

闞元平

(福建師范大學(xué)福清分校電子與信息工程學(xué)院，福建 福清 350300)

1 引言

基于身份的數(shù)字簽名IBS(Identity-Based Signature)由Shamir[1]于1984年首次提出，其特點(diǎn)是用戶公鑰可以是標(biāo)識(shí)用戶身份的任意字符串，如用戶的電子郵件地址等，因此避免了傳統(tǒng)公鑰體制的密鑰管理問題。第一個(gè)實(shí)用的IBS方案由Boneh和Franklin[2]于2001年利用雙線性對(duì)提出，但其計(jì)算復(fù)雜度較高。IBS作為在輕量級(jí)應(yīng)用領(lǐng)域的重要技術(shù)，在電子商務(wù)、電子政務(wù)、云計(jì)算等領(lǐng)域具有廣泛的應(yīng)用前景。

目前，IBS方案大多基于傳統(tǒng)密碼體制，而隨著量子計(jì)算機(jī)的發(fā)展，傳統(tǒng)密碼體制面臨重大的安全隱患——量子算法攻擊。1996年,Shor[3]指出,基于離散對(duì)數(shù)問題和大數(shù)分解問題的密碼體制可由量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)求解，因而基于雙線性對(duì)的密碼算法也不再安全?？紤]到量子計(jì)算的發(fā)展情形[4]，尋找可抵抗量子攻擊的IBS方案具有重要意義。

在后量子密碼時(shí)代，格密碼可有效抵抗量子攻擊。1996年,Ajtai[5]證明了格困難問題在最壞情形和平均情形的困難性等價(jià)規(guī)約，2009年,Bernstein[6]指出格密碼可抵抗量子攻擊。在此基礎(chǔ)上，Ckert[7]于2010年提出了首個(gè)基于格密碼的IBS方案，此后基于格密碼的IBS方案大量出現(xiàn)[8 - 12]，其中不乏具有抵抗強(qiáng)偽造攻擊的高效格身份簽名方案。2016年,Xie等[13]提出了一個(gè)高效的NTRU(Number Theory Research Unit)格的IBS方案，其可抵抗選擇明文偽造攻擊。

1993年Nyberg等[14]提出了消息恢復(fù)簽名的概念，由于其可減小消息和簽名的長(zhǎng)度，因而適用于資源受限的輕量級(jí)應(yīng)用領(lǐng)域。2013年,Tian等[15]提出了格消息恢復(fù)簽名方案，2014年,張襄松等[16]提出了無陷門的格消息恢復(fù)簽名方案。

本文在Xie等[13]方案基礎(chǔ)上，構(gòu)造一個(gè)具有消息恢復(fù)功能的格身份簽名方案，并給出了安全性證明。本方案具有高效、抵抗偽造攻擊、簽名長(zhǎng)度短的特點(diǎn)，可廣泛應(yīng)用于輕量級(jí)認(rèn)證領(lǐng)域。

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

2.1 符號(hào)說明[13,15]

安全參數(shù)N=2t，為大于8的正整數(shù)，其余的參數(shù)與之相關(guān)。R、Z分別為實(shí)數(shù)、整數(shù)空間。環(huán)Rq=Zq[x]/(xN+1)，其中q為大于5的素?cái)?shù)，xN+1可分解為kq個(gè)模q的不可約多項(xiàng)式。R×為Rq中的可逆元組成的集合，黑體小寫字母如x表示向量，黑體大寫字母如X表示矩陣，〈x,y〉表示向量?jī)?nèi)積，‖x‖表示歐式范數(shù)。

由f生成的矩陣，記為：

2.2 NTRU格

Λh,q={(u,v)∈R2|u+v*h≡0 modq}

NTRU格為2N維實(shí)向量空間R2N上滿秩的格，同時(shí)也是使用范圍最廣、效率最高的格之一?；鵄h,q中IN為N×N階單位陣，ON為N×N階元素為0的矩陣。

2.3 離散高斯分布

在N維實(shí)向量空間RN上，當(dāng)以σ>0為標(biāo)準(zhǔn)差，c∈RN為對(duì)稱中心時(shí)：

RN上高斯分布定義為：

格Λ的高斯分布定義為：

格Λ的離散高斯分布定義為：

2.4 NTRU格上的小整數(shù)解問題

2.5 高斯采樣算法

高斯采樣函數(shù)Gaussian_Sampler(B,σ,c)[17]可在概率多項(xiàng)式時(shí)間內(nèi)輸出N維向量v，使其分布與給定的格Λ的離散高斯分布DΛ,σ,c統(tǒng)計(jì)近似。

輸入：N維格Λ的基B，離散高斯分布標(biāo)準(zhǔn)差σ，中心c′∈ZN。

輸出：v←DΛ,σ,c。

1.令vN=0,cN=c′;

2.fori=N…1 do

6.ci-1=ci-zibi,vi-1=vi+zibi;

7.輸出v0。

3 具有消息恢復(fù)功能的格身份簽名方案

本節(jié)將在Xie等[13]方案基礎(chǔ)上，構(gòu)造一個(gè)具有消息恢復(fù)功能的格身份簽名方案。下面給出具體的密鑰生成、簽名生成和簽名驗(yàn)證算法。

3.1 系統(tǒng)主密鑰生成算法

本算法在指定安全參數(shù)N、素?cái)?shù)q、方差σ的情況下，輸出系統(tǒng)主私鑰msk(master secret key)和系統(tǒng)主公鑰mpk(master public key)。

輸入：N,q∈Z,σ>0。

3.若〈f,g〉?R，重新開始;

4.計(jì)算f1,g1∈RN,使其滿足f*f1-g*g1=1，令fq=qf1,gq=qg1;

5.用Babai最近平面法計(jì)算(f′,g′)，使得存在k∈R滿足(f′,g′)=(fq,gq)-k(f,g);

6.若‖(f′,g′)‖>Nσ，重新開始;

3.2 用戶私鑰產(chǎn)生算法

在本方案中，用戶身份id(identification)作為用戶的公鑰，而用戶id的私鑰SKid(SecretKey)則由系統(tǒng)根據(jù)用戶身份id及系統(tǒng)主私鑰msk計(jì)算而來。因此，系統(tǒng)需要首先驗(yàn)證用戶身份并需維護(hù)用戶密鑰列表，當(dāng)用戶注冊(cè)時(shí)，若其選用的用戶身份id未被注冊(cè)，將其放入用戶密鑰列表，并輸出用戶私鑰SKid；否則用戶需重新選擇用戶身份id后再次注冊(cè)。系統(tǒng)驗(yàn)證用戶身份后，執(zhí)行如下算法：

輸入：用戶身份id，系統(tǒng)主私鑰msk。

輸出：用戶私鑰SKid=(s1,s2)。

1.若用戶身份id已存在于用戶密鑰列表中，則拒絕，令用戶重新選擇用戶身份id后重新開始;

3.(s1,s2)=Gaussian_Sampler(B,σ,(t,0))，滿足s1+s2*h=t;

4.返回SKid=(s1,s2);

系統(tǒng)將SKid=(s1,s2)安全地交付給用戶。

3.3 簽名算法

簽名者用下面的算法，利用自己的私鑰SKid對(duì)要簽名的消息m進(jìn)行消息可恢復(fù)的格身份簽名。

輸入：用戶私鑰SKid，消息m。

輸出：消息簽名(z1,z2,r)及部分消息m2。

1.選擇y1,y2∈DZN,s;

2.計(jì)算u=H1(y1+h*y2);

3.令m=m1‖m2，其中|m1|=l2，若|m|≤l2，則m2=⊥;

6.計(jì)算c=H2(r,m2);

7.計(jì)算zi=yi+si*c,i=1,2;

8.以概率min(DZN,s/MDZN,s,SKidu,1) 輸出消息簽名(z1,z2,r)及部分消息m2。

簽名者將消息簽名(z1,z2,r)及部分消息m2發(fā)送給驗(yàn)證者，而普通簽名算法則需傳輸整個(gè)消息m和消息簽名，本算法減少了l2比特的傳輸數(shù)據(jù)量，因此更適用于輕量級(jí)認(rèn)證領(lǐng)域。

3.4 驗(yàn)證算法

消息驗(yàn)證者收到消息可恢復(fù)的格身份簽名及部分消息后，利用簽名者的公鑰即其身份id，用以下算法進(jìn)行簽名的驗(yàn)證。若最終簽名能通過驗(yàn)證則輸出原始消息m，否則拒絕該簽名。

輸入：消息簽名(z1,z2,r)及部分消息m2，用戶身份id。

輸出：消息m或拒絕。

2.計(jì)算c=H2(r,m2);

4.計(jì)算u=H1(h*z2+z1-t*c);

4 安全性分析

本節(jié)對(duì)上述簽名方案的正確性進(jìn)行證明；給出了本方案在隨機(jī)預(yù)言機(jī)模型下的安全性證明，證明了本方案可有效抵抗適應(yīng)性選擇明文和選擇身份攻擊；最后對(duì)簽名的有效性做出了分析，說明本方案可有效減少簽名傳輸數(shù)據(jù)量。因此，本方案具有高效、抵抗偽造攻擊、簽名長(zhǎng)度短的特點(diǎn)，可廣泛應(yīng)用于輕量級(jí)認(rèn)證領(lǐng)域。

4.1 正確性

定理1本方案中簽名算法輸出的合法有效簽名能夠通過驗(yàn)證，并恢復(fù)完整消息。

證明消息簽名(z1,z2,r)及部分消息m2，用戶身份id。由上述算法可知：

∴h*z2+z1-t*c=h*(y2+s2*c) +y1+s1*c-(s1+s2*h)*c=y1+h*y2

∴H1(h*z2+z1-t*c) =u

□

4.2 安全分析

定理2假設(shè)NTRU格上的近似最短向量問題無多項(xiàng)式有效求解算法，則本方案在隨機(jī)預(yù)言機(jī)模型下可有效抵抗適應(yīng)性選擇明文和選擇身份攻擊。

證明若存在攻擊者A以不可忽略的概率ε=ε(N)攻破本方案，則可構(gòu)造一個(gè)多項(xiàng)式時(shí)間的挑戰(zhàn)者C,以近似不可忽略的概率ε=ε(N)攻破NTRU格上的近似最短向量問題。

A和C之間的交互如下：

問詢：A以如下方式進(jìn)行問詢，一般假定A須在其他問詢前首先對(duì)身份id問詢隨機(jī)預(yù)言機(jī)H，其中哈希問詢H(id)及對(duì)身份id提取問詢只能問詢一次。

(1)哈希函數(shù)H問詢：對(duì)于身份idi的問詢，C查詢用戶密鑰列表ID_list(identification-list)，其初始值為空。若idi存在，則返回相應(yīng)的H(idi)給A；否則，C均勻隨機(jī)選擇si1,si2∈DZN,s，計(jì)算H(idi)=si1+h*si2，并將(idi,Pidi,SKidi=(si1,si2))放入ID_list，將H(idi)作為idi的應(yīng)答發(fā)送給A。

(2)提取問詢：給定idi，C查詢ID_list尋找與之匹配的SKidi并將其發(fā)送給A。

(4)哈希函數(shù)F1,F2,H1,H2問詢：當(dāng)A將(idi,mi)發(fā)送給C對(duì)F1,F2,H1,H2分別或者結(jié)合問詢，C查詢Sign_list找到對(duì)應(yīng)的參數(shù)進(jìn)行返回。

按照如下方式，C可有效解決NTRU上的小整數(shù)解問題：

□

4.3 有效性

本文給出的構(gòu)造方法可將任意基于NTRU格小整數(shù)解問題的身份簽名方案改成具有消息恢復(fù)功能的格身份簽名方案。由于具有消息恢復(fù)功能的格身份簽名方案為本文首次提出，無法查找相應(yīng)的文獻(xiàn)進(jìn)行有效的對(duì)比分析，因此只對(duì)本方案可有效減少簽名長(zhǎng)度方面進(jìn)行分析。根據(jù)簽名過程可知，若原方案簽名形式為((z1,z2,n),m),則新簽名方案為((z1,z2,r),m2)，本方案簽名長(zhǎng)度減少|(zhì)n|+|m|-[(l1+l2)+(|m|-l2)]=|n|-l1比特，不妨設(shè)l1=l2=|n|/2比特，則本方案將簽名長(zhǎng)度有效縮短|n|/2比特。

5 結(jié)束語(yǔ)

隨著量子計(jì)算機(jī)的發(fā)展，基于大數(shù)分解問題及離散對(duì)數(shù)問題的密碼體制已不再安全，但格密碼被認(rèn)為是量子安全的，所以本文在格密碼基礎(chǔ)上構(gòu)造了具有消息恢復(fù)功能的身份數(shù)字簽名方案。本方案在隨機(jī)預(yù)言模型下不可偽造，且與普通格身份簽名比較，減少了簽名長(zhǎng)度，效率更高，可以廣泛應(yīng)用于輕量級(jí)應(yīng)用領(lǐng)域。在其他格模型及標(biāo)準(zhǔn)格模型下，構(gòu)造能抵抗適應(yīng)性選擇身份和消息攻擊的消息恢復(fù)格身份簽名方案是下一步值得研究的工作。

參考文獻(xiàn):

[1] Shamir A. Identity-based cryptosystems and signature schemes[C]∥Proc of Workshop on the Theory and Application of Cryptographic Techniques(CRYPTO 1984),1984:47-53.

[2] Boneh D,Franklin M K.Identity-based encryption from the Weil pairing[C]∥Proc of International Cryptology Conference on Advances in Cryptology,2001:213-229.

[3] Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Review,1996,41(2):1484-1509.

[4] Krenn M,Huber M,Fickler R,et al.Generation and confirmation of a (100×100)-dimensional entangled quantum system[J].Proceedings of the National Academy of Sciences of the United States of America,2014,111(17):6243-6247.

[5] Ajtai M.Generating hard instances of lattice problems[C]∥Proc of the 28th Annual ACM Symposium on Theory of Computing,1996:99-108.

[6] Bernstein D J. Introduction to post-quantum cryptography[M]∥Post-Quantum Cryptography.Berlin:Springer Berlin Heidelberg,2009:1-14.

[7] Ckert M.Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[M]∥Post-Quantum Cryptography.Berlin:Springer Berlin Heidelberg,2010:182-200.

[8] Xiang Xin-yin. Identity-based forward secure signature scheme from lattices [J].Computer Engineering,2015,41(9):155-158.(in Chinese)

[9] Yang Dan-ting, Xu Chun-gen,Xu Lei,et al.Identity-based signature scheme over ideal lattices [J].Journal of Cryptologic Research,2015,2(4):306-316.(in Chinese)

[10] Yang Chun-li,Yan Jian-hua,Zheng Shi-hui,et al.Analysis and improvement of an identity-based signature scheme from lattices [J].Journal on Communications,2015,36(5):104-111.(in Chinese)

[11] Ducas L,Lyubashevsky V,Prest T.Efficient identity-based encryption over NTRU lattices[C]∥Proc of International Conference on the Theory and Application of Cryptology and Information Security,2014:22-41.

[12] Liu Z,Hu Y,Zhang X,et al.Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model[J].Security & Communication Networks,2013,6(1):69-77.

[13] Xie J,Hu Y P,Gao J T,et al.Efficient identity-based signature over NTRU lattice[J].Frontiers of Information Technology & Electronic Engineering,2016,17(2):135-142.

[14] Nyberg K,Rueppel R A.A new signature scheme based on the DSA giving message recovery[C]∥Proc of ACM Conference on Computer and Communications Security(CCS’93),1993:58-61.

[15] Tian M,Huang L.Lattice-based message recovery signature schemes[J].International Journal of Electronic Security & Digital Forensics,2013,5(3/4):257-269.

[16] Zhang Xiang-song,Liu Zhen-hua.Non-trapdoors lattice signature scheme with message recovery[J].Computer Science,2014,41(9):165-168.(in Chinese)

[17] Lyubashevsky V.Lattice signatures without trapdoors[C]∥Proc of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques,2011:738-755.

附中文參考文獻(xiàn)：

[8] 向新銀.格上基于身份的前向安全簽名方案[J].計(jì)算機(jī)工程,2015,41(9):155-158.

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

[10] 楊春麗,閆建華,鄭世慧,等.對(duì)一個(gè)格基身份簽名方案的分析和改進(jìn)[J].通信學(xué)報(bào),2015,36(5):104-111.

[16] 張襄松,劉振華.具有消息恢復(fù)功能的無陷門格簽名方案[J].計(jì)算機(jī)科學(xué),2014,41(9):165-168.