闞元平

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

1 引言

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

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

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

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

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

2 預備知識

2.1 符號說明[13,15]

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

由f生成的矩陣，記為：

2.2 NTRU格

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

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

2.3 離散高斯分布

在N維實向量空間RN上，當以σ>0為標準差，c∈RN為對稱中心時：

RN上高斯分布定義為：

格Λ的高斯分布定義為：

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

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

2.5 高斯采樣算法

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

輸入：N維格Λ的基B，離散高斯分布標準差σ，中心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 具有消息恢復功能的格身份簽名方案

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

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

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

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

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

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

5.用Babai最近平面法計算(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計算而來。因此，系統(tǒng)需要首先驗證用戶身份并需維護用戶密鑰列表，當用戶注冊時，若其選用的用戶身份id未被注冊，將其放入用戶密鑰列表，并輸出用戶私鑰SKid；否則用戶需重新選擇用戶身份id后再次注冊。系統(tǒng)驗證用戶身份后，執(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對要簽名的消息m進行消息可恢復的格身份簽名。

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

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

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

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

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

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

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

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

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

3.4 驗證算法

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

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

輸出：消息m或拒絕。

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

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

4 安全性分析

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

4.1 正確性

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

證明消息簽名(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假設NTRU格上的近似最短向量問題無多項式有效求解算法，則本方案在隨機預言機模型下可有效抵抗適應性選擇明文和選擇身份攻擊。

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

A和C之間的交互如下：

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

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

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

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

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

□

4.3 有效性

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

5 結(jié)束語

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

參考文獻:

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

附中文參考文獻：

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

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

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

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