标准模型下格上基于身份的盲签名方案*

汤永利，周 锦，刘 琨，叶 青，闫玺玺

河南理工大学 计算机科学与技术学院，河南 焦作 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]提出的框架，在生成签名密钥的时候都要用到格基派生技术。基于此框架构造的基于身份的签名方案，在使用格基派生技术产生签名密钥的时候，通常情况下会导致格基的维度膨胀，进而使签名密钥和消息签名的尺寸变大，影响签名方案的效率。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年于北京邮电大学获得博士学位，现为河南理工大学讲师，主要研究领域为密码学。