標準模型下格上基于身份的盲簽名方案*

湯永利，周 錦，劉 琨，葉 青，閆璽璽

河南理工大學 計算機科學與技術學院，河南 焦作 454000

標準模型下格上基于身份的盲簽名方案*

湯永利，周 錦，劉 琨，葉 青+，閆璽璽

河南理工大學 計算機科學與技術學院，河南 焦作 454000

隨機預言模型下的盲簽名方案都依賴于隨機預言假設，即使方案被證明安全，在實際應用時未必安全。構造了一個標準模型下格上基于身份的盲簽名方案。該方案中引入一個短格基派生算法，根據用戶的身份產生對應的私鑰，并利用Gentry等人提出的原像抽樣陷門單向函數產生消息的簽名。在標準模型下依據Juels和Pointcheval等人提出的安全模型，基于小整數解問題（small integer solutions，SIS）的困難性，證明了該方案滿足one-more不可偽造性。分析表明，與同類方案相比，該方案密鑰長度和簽名長度有所減小，效率更高。

格；基于身份；標準模型；盲簽名

1 引言

盲簽名的概念首先由Chaum[1]在1982年提出，消息擁有者在不公布消息真實內容的情況下，即可獲得消息簽名者對真實消息的合法簽名。由于盲簽名具有保護用戶隱私的性質，在電子現金、電子選舉、不經意傳輸等領域得到了廣泛的應用。1985年Shamir[2]提出了基于身份密碼學的概念，降低了密碼算法的計算開銷和實現成本，而且去除了PKI體制中的公鑰證書管理負擔。結合盲簽名和基于身份密碼學，Zhang和Kim在2003年利用雙線性對提出了基于身份的盲簽名方案[3]。目前，很多研究者仍繼續對基于身份的盲簽名方案進行研究，但是大多方案的安全性是基于數論難題（如大整數分解和離散對數問題）的，然而在量子計算機得到應用的前提下，基于數論假設的困難問題都可以在多項式時間內得到解決[4]。因此，設計能抵抗量子攻擊的簽名方案成為該領域需解決的問題。

1996年，Ajtai在STOC上發表的文獻[5]中論證了基于格的公鑰密碼體制是量子計算機不能攻破的少數經典公鑰密碼體制之一。格[6]是Rm中一類具有周期性結構離散點的集合。嚴格地說，格是m維歐式空間Rm的n（m＞n）個線性無關向量組v1,v2,…,vn的所有整系數線性組合，即，向量組v1,v2,…,vn稱為格的一組基?；诟竦墓€密碼體制還有其他優良特性，如平均情況與最差情況一樣安全以及簡單高效等，因而近幾年引起了國內外密碼學家的密切關注。2008年Gentry和Peikert等人[7]基于小整數解問題（small integer solutions，SIS）提出了一個帶原像抽樣的陷門單向函數，并指出該原像抽樣陷門單向函數可用于構造基于格的簽名方案和格上基于身份的加密方案。2010年Rückert在文獻[8]中，利用原像抽樣陷門單向函數設計了第一個基于格的盲簽名方案（lattice-based blind signature scheme，LBSS）。同年Rückert在文獻[9]中提出了第一個格上基于身份的簽名方案（lattice-based identitybased signature scheme，LIBSS）。此后其他的LIBSS也被提出[10-11]，它們的構造大部分是基于Gentry和Peikert等人[7]提出的框架，在生成簽名密鑰的時候都要用到格基派生技術?；诖丝蚣軜嬙斓幕谏矸莸暮灻桨福谑褂酶窕缮夹g產生簽名密鑰的時候，通常情況下會導致格基的維度膨脹，進而使簽名密鑰和消息簽名的尺寸變大，影響簽名方案的效率。Gu等人[12]在2012年提出了一個在隨機預言模型下格上基于身份的盲簽名方案，該方案是在隨機預言模型下可證明安全的，方案中假設存在一個理想的抗碰撞的哈希函數，即使方案被證明安全，在實際應用中未必安全。目前還沒有一個在標準模型下可證明安全的基于身份的盲簽名方案。

Agrawal和Boneh等人[13]在2010年美密會上提出了一個新的短格基派生算法，該算法并不會增加格的維度，即能使生成密鑰的長度保持不變，從而提高密碼方案效率。

本文將Agrawal提出的新的短格基派生算法引入基于身份的盲簽名方案[12,14]中，構造了一個標準模型下格上基于身份的盲簽名方案。方案中，使用新的短格基派生算法根據用戶的身份信息生成用戶的私鑰，從而達到縮短用戶私鑰和簽名長度的目的，并利用Gentry等人提出的原像抽樣陷門單向函數產生消息的簽名。根據文獻[15-16]提出的盲簽名的安全模型，基于格上SIS困難問題證明方案滿足one-more不可偽造性，本文方案與現有其他基于格的盲簽名方案[17-18]相比，生成的用戶私鑰和簽名長度要小，效率更高。

2 預備知識

2.1 格上困難問題

定義1對于整數q與矩陣，定義兩個整數格：

定義2（小整數解問題）給定整數q，矩陣，實數β，找到一個非零向量x∈Zm，使得Ax=0modq，并且||x||≤β。

定義3（非齊次小整數解問題）給定整數q，矩陣，實數β，找到一個非零向量x∈Zm，使得Ax=ymodq，并且||x||≤β。

定義4[19]（光滑參數smoothing parameter）設任意一個n維格Λ和一個實數ε＞0，光滑參數ηε(Λ)為使得ρ1s(Λ?{0})≤ε成立的最小的s(s＞0)。

定理1[7]對于任意秩為k的n維格Λ，c∈Rn，正數ε＜exp(-4π)和s≥ηε(Λ)，對于每一個x∈Λ有：

定理2[19]設一個任意的秩為k的n維格Λ，任意c∈Rn，ε∈(0,1)，s≥ηε(Λ)，則有：

2.2 原像抽樣算法和格基派生算法

定理3[7]對于任意格的基B∈Zn×k，高斯參數和c∈Rn，算法SampleD(B,s,c)的輸出分布與DZk,s,c(x)在統計上是不可區分的。

定理3中算法SampleD(B,s,c)采樣輸出的向量e滿足Be的分布在上是均勻的。

定理4[7]對于矩陣上的一個短陷門基TA，向量，高斯參數，算法SamplePre(A,TA,y,s)輸出向量在統計距離上是不可區分的。

定理5[7]給定任意素數q=poly(n)和任意m≥5nlgq，存在一個概率多項式算法TrapGen(1n)，輸入為1n，輸出矩陣和一個滿秩的集合S?Λ⊥(A,q)，A在上是均勻分布的，并且||S||≤L=m1+ε，ε＞0 。

定理6[13]輸入一個矩陣的一個短基TA，在Dm×m中選取的可逆矩陣R∈Zm×m，高斯參數，算法BasisDel(A,R,TA,s)隨機輸出格Λ⊥(AR-1)的一個基B，并且。

3 標準模型下格上基于身份的盲簽名方案

下面介紹本文提出的標準模型下格上基于身份的盲簽名方案。方案中各個參數的取值范圍和參數符號介紹如下：n為安全參數且n是大于0的整數，q為素數且q≥2，m≥5nlgq，本方案中用到一個哈希函數是一個抗碰撞的哈希函數。

方案具體描述如下。

Setup(1n)：私有密鑰生成器PKG（private key generator）以安全參數n為輸入，運行陷門生成算法TrapGen(1n)，根據定理5可知生成矩陣和對應的短基為系統主密鑰，A0為系統公鑰。假設消息M是由任意d比特長的比特串{0,1}d組成，那么隨機選擇d個不相關的向量。公布系統的公共參數PP=A0,C1,C2,…,Cd，主密鑰MK=S0。

Extract(PP,id,MK)：系統根據收到的簽名者的身份信息id，通過自己的主秘密密鑰S0和公共參數PP，使用定理6提出的格基派生算法BasisDel(A0,H(id),S0,s)輸出簽名者的私鑰Sid，其中Sid為格Λ⊥(A0H(id)-1)的一個基，s為高斯采樣參數。

Sign(PP,SKid,μ)：假設要簽名的消息為M，則簽名者S和消息擁有者C做如下操作。

（1）消息盲化：消息擁有者C隨機均勻選取t∈D={t∈R|||t||≥1/s}，使用定理3中的算法SampleD(A0H(id)-1,s)輸出一個向量u，計算，μ為盲化后的消息，把μ發給簽名者S。

（2）對盲化消息簽名：簽名者S在接收到消息擁有者C發來的盲化消息μ之后，使用定理4中的原像采樣陷門算法對μ進行簽名。SamplePre(A0H(id)-1,Sid,μ,s)輸出盲化消息的簽名，簽名者S驗證且e′≠0 ，如果不滿足則重新選取，事實上根據定理2以極大概率成立，并在本地存儲(μ,e′)，然后將簽名發送給消息擁有者C。

（3）消息去盲：消息擁有者C收到簽名之后，做去盲操作e=t-1(e′-u)，e即為消息M的簽名。

Verify(PP,id,M,e)：任意驗證者都能驗證(M,e)的正確性，通過下面的計算。

（1）驗證e≠0且，如果滿足進行（2）驗證，不滿足則拒絕。

4 安全性分析

本文基于Juels等人[15]和Pointcheval等人[16]提出的安全模型，證明本文方案滿足正確性、盲性和onemore不可偽造性。盲性是指簽名者對消息進行簽名時不能獲得任何有關簽名消息的信息。one-more不可偽造性是指攻擊者與簽名者交互，獲得l個不同消息的誠實簽名，無法偽造第l+1個新消息的簽名。

4.1 正確性

定理7本文提出的簽名方案滿足正確性。

證明（1）因為消息簽名e=t-1(e′-u)，所以 ||e||=||t-1(e′-u)||，由定理 4 可知，由定理 3可知，由用戶盲化操作可知，因此。

（2）因為A0H(id)-1(t-1(e′-u))=t-1(A0H(id)-1e′-A0H(id)-1u)，在簽名算法中e′←SamplePre(A0H(id)-1,Sid,μ,s)，所以A0H(id)-1e′=μ，μ為盲化的消息，從而A0H(id)-1e=t-1(μ-A0H(id)-1u)。又因為，所以。故所提出的簽名方案是正確的。 □

通過雞胚絨毛尿囊膜試驗研究， 10種防曬劑均有不同程度的刺激性，其中苯基苯并咪唑磺酸和二苯酮-3為強刺激性物質，其余防曬劑為中等刺激性物質。

4.2 盲性

定理8本文提出的簽名方案滿足消息的盲性。

證明簽名者S不能從盲化后的消息μ中得到有關消息M的任何信息，也就是要證明消息M的概率分布和盲化消息μ的概率分布的統計距離為0，即：

4.3 不可偽造性

Juels和Pointcheval等人在文獻[15]和文獻[16]中定義了盲簽名的安全模型，其中要求盲簽名滿足onemore不可偽造性，即如果對于任意偽造者A在掌握簽名公鑰條件下，與誠實簽名者進行l次簽名交互，得到l個不同消息的簽名，偽造第l+1個新消息的簽名的概率是可以忽略的，則簽名方案滿足one-more不可偽造性。

定理9如果平均情況下的SISq,m,s是困難的，則本文提出的簽名方案在選擇消息攻擊下滿足onemore不可偽造性。

證明如果敵手F能夠攻破本文方案，即成功偽造出合法簽名，且其優勢（攻擊成功的概率）為ε，則可構造多項式時間算法T求解SIS問題。其中敵手在攻擊時至少要進行qε(qε＞1)次私鑰詢問，qs次簽名詢問。

構造算法T模擬F的攻擊環境并利用F的偽造簽名求解SIS問題的一個實例。

Setup：算法T隨機產生一個矩陣和對應的陷門T0?Λ⊥(B)，選擇R1～Dm×m，然后運行BasisDel(B,R1,T0,s)輸出S0，其中S0是的基，設為主公鑰，S0為主秘密密鑰。使用算法SampleD(B,s)隨機選取d個非零向量，并且使得BEi在上是均勻分布的。選擇qε-1個不相關的非奇異矩陣。令Ci=BEi，公開公共參數，系統主秘密密鑰MK=S0。

私鑰詢問：當身份IDi被詢問時產生相對應的私鑰，其中i=1,2,…,qε。算法T收到IDi計算，使用BasisDel(A0,H(IDi),S0,s)算法生成對應的私鑰Si，并在本地存儲(IDi,Si)，然后把Si發送給敵手F，假設敵手詢問的IDi是以前詢問過的，那么算法T首先會在本地查找(IDi,Si)，并把對應的Si發送給敵手。

簽名詢問：當算法T收到(IDi,μM)，其中IDi為簽名者的身份信息，μM為盲化后的消息，使用原像陷門采樣函數對盲化消息μM簽名，eM′←SamplePre(A0H(id)-1,Si,μM,s)，eM′即為消息μM的簽名。之后算法T檢查，如果不滿足則重新簽名，把(IDi,μM,eM′)存儲在本地，并且把eM′發送給敵手F。如果接收到的消息是以前詢問過的，那么算法T首先在本地的數據庫查找(IDi,μM,eM′)。如果找到，則直接把對應的eM′返回給敵手F。敵手F在收到簽名后進行去盲操作，最后得到消息的簽名(IDi,M,eM)。

偽造：最終經過有限次的私鑰提取詢問和簽名詢問，敵手F偽造了可用簽名(IDi,M,eM)，偽造成功的概率為ε。

可以知道：（1）eM≠0并且；（2）A0H。如果i≠1，則簽名驗證失敗。當i=1時，有，因為并且Ci=BEi，所以。令并且，則上式等于BeM=BEM，因此B(eM-EM)=0modq，。這樣知道eM-EM為SIS問題實例的一個解，SIS問題的參數為，因為這個解不能是0解，所以eM≠EM。那么eM=EM的概率大約為，敵手F成功偽造簽名的概率為ε，pro(i=1)=1/qε。因此eM-EM為問題的解的概率近似接近于。 □

5 效率對比

簽名方案的效率主要取決于簽名私鑰的長度、公鑰的長度和簽名的長度。本文中，n為安全參數，m是格的維度，d為被簽名消息的比特長度，q為素數且q≥2。

本文方案主要使用了簡單的線性運算（模乘、模加），與所有數論上的基于身份的盲簽名方案相比，計算效率顯然更高。從表1中可知，文獻[17]是格上的代理盲簽名方案，其生成私鑰的算法增加了格的維度，所有私鑰和簽名都變長了。本文使用新的派生算法，保證維度不變，因此效率有所提升。文獻[18]是格上基于身份的代理盲簽名，該方案為了滿足強不可偽造性，使用代理密鑰和用戶私鑰分別對消息進行處理和簽名，其中用代理密鑰簽名生成的消息簽名變大。而本文方案只進行一次簽名和一次驗證，故生成的簽名長度不變，計算效率也有所提高。文獻[12]是在隨機預言模型下證明安全的基于身份的盲簽名方案，隨機預言模型下可證明安全并不代表真實世界的安全，因為它依賴于現實世界無法實現的隨機預言假設。從表1中可以看出，本文方案在公鑰和私鑰長度上比文獻[17]要短，簽名長度比文獻[17]和文獻[18]都短，簽名效率更高，和文獻[12]相比，雖然公鑰長度長，但是在標準模型下證明安全。

Table 1 Efficiency comparison表1 效率對比

6 結論

本文提出了一個標準模型下格上基于身份的盲簽名方案，并且分析了方案的安全性和效率，利用Agrawal等人[13]提出的新的短格基派生算法在不增加格的維度的情況下生成用戶的私鑰，從而達到縮短用戶私鑰和簽名長度的目的，使用原像抽樣陷門單向函數對消息進行簽名，故方案密鑰長度和簽名長度更短，計算效率更高。本文方案的安全性主要基于格上的困難問題，因此能抵抗量子攻擊。

[1]Chaum D.Blind signatures for untraceable payments[M]//Advances in Cryptology.Boston:Springer US,1983:199-203.

[2]ShamirA.Identity-based cryptosystems and signature schemes[C]//LNCS 196:Proceedings of CRYPTO 1984,Santa Barbara,USA,Aug 19-22,1984.Berlin,Heidelberg:Springer,1985:47-53.

[3]Zhang Fangguo,Kim K.Efficient ID-based blind bignature and proxy signature from bilinear pairings[C]//LNCS 2727:Proceedings of the 8th Australasian Conference on Information Security and Privacy,Wollongong,Australia,Jul 9-11,2003.Berlin,Heidelberg:Springer,2003:312-323.

[4]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal on Computing,1997,26(5):1484-1509.

[5]Ajtai M.Generating hard instances of lattice problems[C]//Proceedings of the 28th Annual ACM Symposium on Theory of Computing,Philadelphia,USA,May 22-24,1996.New York:ACM,1996:99-108.

[6]Wang Xiaoyun,Liu Mingjie.Survey of lattice-based cryptography[J].Journal of Cryptologic Research,2014,1(1):13-27.

[7]Gentry C,Peikert C,Vaikuntanathan V.Trapdoors for lattices and new cryptographic constructions[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing,Victoria,Canada,May 17-20,2008.New York:ACM,2008:197-206.

[8]Rückert M.Lattice-based blind signatures[C]//LNCS 6477:Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security,Singapore,Dec 5-9,2010.Berlin,Heidelberg:Springer,2010:413-430.

[9]Rückert M.Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[C]//LNCS 6061:Proceedings of the 3rd International Conference on Post-Quantum Cryptography,Darmstadt,Germany,May 25-28,2010.Berlin,Heidelberg:Springer,2010:182-200.

[10]Tian Miaomiao,Huang Liusheng.Identity-based signatures from lattices:simpler,faster,shorter[J].Fundamental Information,2014,145(2):171-187.

[11]Liu Zhenhua,Zhang Xiangsong,Hu Yupu.Revocable and strongly unforgeable identity-based signature scheme in the standard model[J].Security and Communication Networks,2016,9(14):2422-2433.

[12]Gu Chunxiang,Chen Li,Zheng Yonghui.ID-based signatures from lattices in the random oracle model[C]//LNCS 7529:Proceedings of the 2012 International Conference on Web Information Systems and Mining,Chengdu,China,Oct 26-28,2012.Berlin,Heidelberg:Springer,2012:222-230.

[13]Agrawal S,Boneh D,Boyen X.Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[C]//LNCS 6223:Proceedings of the 30th Annual Cryptology Conference on Advances in Cryptology,Santa Barbara,USA,Aug 15-19,2010.Berlin,Heidelberg:Springer,2010:98-115.

[14]Wang Fenghe,Hu Yupu,Wang Chunxiao.Lattice-based blind signature schemes[J].Geomatices and Information Science of Wuhan University,2010,35(5):550-553.

[15]Juels A,Luby M,Ostrovsky R.Security of blind digital signatures(extended abstract)[C]//LNCS 1294:Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology,Santa Barbara,USA,Aug 17-21,1997.Berlin,Heidelberg:Springer,1997:150-164.

[16]Pointcheval D,Stern J.Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,13(3):361-396.

[17]Zhang Lili,Song Yongxuan.Proxy blind signature scheme from lattice basis delegation[J].International Journal of Advancements in Computing Technology,2012,4(21):99-104.

[18]Zhang Lili,Ma Yanqin.A lattice-based identity-based proxy blind signature scheme in the standard model[J].Mathematical Problems in Engineering,2014:307637.

[19]Micciancio D,Regev O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM Journal on Computing,2007,37(1):267-302.

附中文參考文獻：

[6]王小云,劉明潔.格密碼學研究[J].密碼學報,2014,1(1):13-27.

[14]王鳳和,胡予濮,王春曉.基于格的盲簽名方案[J].武漢大學學報:信息科學版,2010,35(5):550-553.

Lattice-Based Identity-Based Blind Signature Scheme in Standard Model*

TANG Yongli,ZHOU Jin,LIU Kun,YE Qing+,YAN Xixi

College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China

2016-11,Accepted 2017-03.

The blind signature scheme in the random oracle model relies on the random oracle assumption.The scheme is proven to be secure in theory,but it may not be secure in practice.This paper constructs an identity-based blind signature scheme with lattice in the standard model.A short basis delegation algorithm is introduced to generate the private key.The signature of the message is generated by the forward sampling algorithm proposed by Gentry et al.Under the standard hardness assumption of the small integer solutions problem(SIS),the new scheme is proven to be one-more unforgeable based on Juels and Pointcheval's security model in the standard model.The comparison results show that the key length and signature length are shorter,and the efficiency is higher.

lattice;identity-based;standard model;blind signature

+Corresponding author:E-mail:yeqing@hpu.edu.cn

10.3778/j.issn.1673-9418.1611022

*The“13th Five-Year”National Crypto Development Foundation of China under Grant No.MMJJ20170122(國家密碼管理局“十三五”國家密碼發展基金);the Project of Science and Technology Department of Henan Province under Grant No.142300410147(河南省科技廳項目);the Project of Education Department of Henan Province under Grant Nos.12A520021,16A520013(河南省教育廳項目);the Doctoral Fund of Henan Polytechnic University under Grant No.B2014-044(河南理工大學博士基金).

CNKI網絡優先出版:2017-03-22,http://kns.cnki.net/kcms/detail/11.5602.TP.20170322.1754.002.html

TANG Yongli,ZHOU Jin,LIU Kun,et al.Lattice-based identity-based blind signature scheme in standard model.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1965-1971.

A

TP309

TANG Yongli was born in 1972.He received the Ph.D.degree in cryptology from Beijing University of Posts and Telecommunications in 2008.Now he is a professor at Henan Polytechnic University.His research interests include information security and cryptology,etc.

湯永利（1972—），男，河南孟州人，2008年于北京郵電大學獲得博士學位，現為河南理工大學教授，主要研究領域為信息安全，密碼學等。

ZHOU Jin was born in 1991.He is an M.S.candidate at Henan Polytechnic University.His research interest is cryptology.

周錦（1991—），男，河南鄭州人，河南理工大學碩士研究生，主要研究領域為密碼學。

LIU Kun was born in 1978.She is an associate professor and M.S.supervisor at Henan Polytechnic University.Her research interests include information security and cryptology,etc.

劉琨（1978—），女，河南焦作人，碩士，河南理工大學副教授、碩士生導師，主要研究領域為信息安全，密碼學等。

YE Qing was born in 1981.She received the Ph.D.degree in cryptology from Beijing University of Posts and Telecommunications in 2014.Now she is a lecturer at Henan Polytechnic University.Her research interest is cryptology.葉青（1981—），女，遼寧營口人，2014年于北京郵電大學獲得博士學位，現為河南理工大學講師，主要研究領域為密碼學。

YAN Xixi was born in 1985.She received the Ph.D.degree in cryptology from Beijing University of Posts and Telecommunications in 2012.Now she is a lecturer at Henan Polytechnic University.Her research interest is cryptology.

閆璽璽（1985—），女，河南靈寶人，2012年于北京郵電大學獲得博士學位，現為河南理工大學講師，主要研究領域為密碼學。