理想格上基于身份的环签名方案

孙意如 梁向前 商玉芳

摘要：现有的签名方案大多是基于双线性对，但在量子计算环境下此类方案被证明是不安全的。格具有运算简单、困难问题难以破解等特点，为了抵抗量子攻击，基于格中标准的小整数解（SIS）困难假设，利用Ducas等提出的理想格技术（DUCAS L， MICCIANCIO D. Improved short lattice signatures in the standard model. Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2014： 335-352），构造了一种能够在标准模型下给出安全性证明的基于身份的环签名方案。该方案主要分为4个步骤：主密钥生成算法Kergen（n）、签名私钥生成算法Extract（R，ID）、签名算法Sign（Ts，M）和验证算法Verify（P，M，e）。输出的签名为单个向量。相比同类型格上的签名方案，在一定程度上缩减了公钥、签名私钥及签名的长度，提高了运算效率，适用于轻量级认证，算法的安全性也间接保证了电子商务和云计算等领域的安全性。

关键词：

理想格；标准模型；基于身份；环签名；小整数解

中图分类号： TP301.6； TP309.2 文献标志码：A

0引言

作为加密体制与数字签名体制的结合物，基于身份的环签名方案是一项轻量级认证中的重要技术，在电子商务、云计算等领域有着较高的实际应用价值。1991年，群签名的概念首次由Chaum等[1]提出，在群签名中，任一群成员均可代表所属群进行匿名签名，是一种可以对签名者进行模糊操作的签名方案，验证者只能检验签名是否出自此群，而不能确定该群中具体的签名者。2001年，环签名的概念由Rivest等[2]首次提出，被称为群签名的简化，与群签名不同的是，环签名不设立环管理员，不需要对环进行创建和撤销等操作，签名者可以利用自己的私钥和其他环成员的公钥独立产生签名，因而环签名满足无条件匿名性。2002年，结合环签名方案和基于身份的加密方案，首个基于身份的环签名由Kim等[3]提出，解决了签名方案中的证书验证和存储难题，并受到国内外学者们的关注。最近，众多诸如这种类型的基于身份的环签名方案也被陆续提出，如2005年，Chow等[4]构造了一个高效的、针对双线性对的计算次数为常数的基于身份的环签名方案；2006年，Liu等[5]构造了一种基于身份的环签名方案，此方案可在标准模型下给出安全性证明。以上构造的签名方案均是基于双线性对，而在量子计算环境下，此类方案被证明是不安全的，如1994年，Shor[6]指出：基于数论困难问题假设的加密方案不能够有效地抵抗量子攻击。为了设计可以抵抗量子攻击的基于身份环签名方案，众多国内外学者逐渐开始尝试利用格及特殊格的优点和特性进行签名方案的设计。如2010年，首个标准模型下基于身份的格上环签名方案由Wang[7]提出，但作者并没有给出相应的安全性证明或分析；2012年，参照Boyen在2010年提出的信息添加技术[8]，田苗苗等[9]给出了一种格上的环签名方案，相比之前提出的格上的环签名方案，作者给出了标准模型下的选择子环、适应性选择消息的安全性证明，提高了此类方案的安全性，但方案的签名长度和密钥长度较长，不利于计算效率的提高；2013年，参照Cash等[10]在2010年给出的格基生成算法和信息添加技术，基于格中标准的小整数解（Small Integer Solution， SIS）困难问题，李玉海等[11]在格上构造了一种基于身份的环签名方案，与文献[8，10]中的签名方案相比，提高了方案的计算效率，并在标准模型下给出了方案在选择身份和消息攻击下具有不可伪造性的证明，但方案密钥长度、签名长度依然不是很理想；基于SIS困难问题，2014年，参照Micciancio等[12]给出的陷门生成算法，在标准模型下，Ducas等[13]给出了一个理想格上的短格签名方案；2015年杨丹婷等[14]也利用理想格的特殊代数结构，文献[12]中给出的理想格技术，构造了一种基于身份的签名（IdentityBased Signature， IBS）方案。此方案在一定程度上减少了计算复杂度，缩短了签名和公钥长度，可在标准模型下给出安全性证明，并在文章最后分析了在选择身份和固定选择消息攻击下，方案满足不可伪造性，但只针对单一的身份id进行签名，无法实现方案的匿名性。

目前，还不存在量子计算方法能够求解格上的困难问题，因此，格上的加密方案和签名方案能够抵抗量子攻击。本文基于SIS困难问题，依据Ducas等[13]提出的理想格技术，构造了一种标准模型下可证安全的基于身份的环签名方案，能够有效抵抗选择身份和消息攻击。与现有的方案比较，本文利用了理想格的一些特殊代数结构，构造的方案中具有较短的公钥和签名私钥，在一定程度上缩短了签名长度，并在不减弱其安全强度的前提下，提高了方案的运算效率。

1背景知识

1.1符号说明

为了方便签名方案的理解，在此将部分文献中用到的符号进行简要说明：Rm为m维实向量空间；Zn为n维整向量空间；L（A）为由矩阵A生成的格；Rn×nq为n×n维模q的实向量空间；Rq为模q的多项式环；T为标记前缀集合。

1.2格和理想格

1.4相关算法

文献[12]给出了一种新的方法来生成和运用格密码学上的“强陷门”，这种方法简单、有效，易于实现，包括了一种新的陷门，反转错误学习（Learning With Error， LWE）的专门算法，随机化SIS原象取样，以及陷门的安全授权。随后，Ducas等[13]参照文献[12]中的格陷门生成算法，基于理想格上逼近最短向量问题（Shortest Vector Problem， SVP）的最坏情况复杂性，提出了一个在标准模型下可证安全的签名方案，实现了短签名（输出的签名为一个格向量）和相当短的公钥（包含O（ lb n）个向量），降低了类似的短签名方案的计算复杂性（如文献[12]）。参照文献[12]的格陷门生成算法和文献[13]的理想格技术，提出理想格上基于身份的环签名方案，具体执行过程在第3章给出。

2IBS方案的形式化定义和安全性定义

2.1签名方案形式化定义

定义6基于身份的环签名方案[5]包括如下4个概率多项式时间（Probabilistic Polynomial Time， PPT）算法。

1）Kergen（n）。输入安全参数n，算法输出主密钥R及系统公开参数pp。

2）Extract（R，ID）。输入公共参数pp、主密钥R和用户身份ID，输出该用户的签名私钥T。

3）Sign（Ts，M）。输入公共参数pp、用户环P=（ID1，ID2，…，IDl）、用户IDs的签名私钥Ts以及待签名消息M，输出该用户对消息M的环签名e。

4）Verify（P，M，e）。输入公共参数pp、用户环P=（ID1，ID2，…，IDl）、消息M及其签名e，若e为有效签名，则输出Valid；否则，输出Invalid。

2.2签名方案安全性定义

假设一个基于身份的环签名方案满足两个条件：匿名性以及不可伪造性，则可称为是安全的签名方案。本文依据Bender等[15]构造的模型，给出如下形式化定义。

定义7匿名性[5]。假设敌手A在多项式时间内赢得以下Game的优势为Padv=Psuc-1/2，其中Psuc为敌手A赢得Game的概率，若Padv可忽略，则称签名方案满足匿名性。

1）输入系统安全参数n，模拟者B运行算法Kergen（n），将主密钥R以及系统公开参数pp输出并发送给敌手A。

2）敌手A发送用户环P，两个用户身份ID0，ID1∈P及消息M∈（0，1）进行签名询问，模拟者B随机选择i∈{0，1}，计算IDi的签名私钥Ti，并运行签名算法Sign（Ts，M），将签名结果e发送给敌手A。

3）敌手A对签名身份进行猜测，假设为i′，若IDi′=IDi，则敌手A赢得此Game。

定义8不可伪造性[5]。若敌手A在多项式时间内赢得以下Game的概率Psuc可忽略，则称签名方案能够抵抗适应性选择身份和消息攻击，满足不可伪造性。

1）输入系统安全参数n，B运行算法Kergen（n），将输出的主密钥R保密，公开参数pp发送给敌手A。

2）敌手A随机选择一个用户身份ID∈P进行多项式次数私钥提取询问，模拟者B运行算法Extract（R，ID），并将输出结果发送给敌手A。

3）敌手A选择用户环P和消息M∈（0，1）进行多项式次数签名询问，模拟者B运行算法Sign（Ts，M），并将输出签名结果e发送给敌手A。

4）敌手A对消息M′输出一个伪造环签名（P′，t′，e′），若验证环签名（P′，t′，e′）输出结果为Valid，且环P′中的元素没有进行私钥提取询问，（P′，M′）没有进行签名询问，则敌手A赢得此Game。

3理想格上基于身份的环签名方案

4签名方案分析

本文利用理想格中的特殊代数结构，利用Micciancio等[12]提出的格陷门生成算法GenTrap，提出了一种标准模型下基于身份的环签名方案。

4.1有效性分析

4.2效率性分析

与其他格上同类型的基于身份的签名方案相比，本文利用理想格的特殊代数结构构造了一种标准模型下可证安全的基于身份的环签名方案，将待签名消息进行隐藏后签名。签名公钥、私钥的长度都相对较短，最终输出的签名为单个向量，在降低运算复杂度的同时，签名长度也在一定程度上缩短，比如文献[11]中最终输出的签名为l+k+1个m维向量，签名长度比较长，增加了签名方案的计算复杂性。

本文的签名方案在步骤Extract和步骤Sign中，仅需运行DelTrap算法[12]和SampleD算法[12]以及少量的向量运算，不需要相对耗时的算法，比如2010年Rückert[16]提出的签名方案中的Extlattice算法、Extbasis算法；2013年李玉海等[11]提出的签名方案中的ExtBasis算法、RandBasis算法，因而在一定程度上提高了算法的运算速度。为了方便比较基于格上困难问题的签名方案的优势和缺陷，表1给出了几种方案的主要参数（公共参数、签名私钥、签名等）长度对比。

4.3安全性分析

4.3.1匿名性

定理9本文提出的理想格上基于身份的环签名方案满足无条件匿名性。

证明输入安全参数n，系统随机选择两个抗碰撞Hash函数，以及d+3个独立随机向量A0，B0，…，Bd，U∈R1×kq，v∈Rq，模拟者B运行算法Kergen（n），将输出的系统公开参数pp={A，A0，B0，…，Bd，U，v}和主密钥R发送给敌手A。

敌手A接收到公共参数pp和主密钥R之后，发送用户环P，两个用户身份ID0、ID1∈P及消息M∈（0，1）给模拟者B，进行签名询问，模拟者B随机选择i∈{0，1}，运行算法Extract（R，ID），得到用户IDi的签名私钥Ti，然后运行签名算法Sign（Ts，M），将用户IDi对消息M的签名结果e发送给敌手A。

假设模拟者B用ID1-i的私钥T1-i进行签名运算，得到的签名为e′，对于固定的用户环P和待签名消息M，因为所有由本文中签名方案输出的合法签名都是某一特定的集合中的随机向量，签名e和e′的验证向量均为Pt，即Pt·e=Pt·e′=u（mod q），故签名e和e′具有相同的离散高斯分布。也就是说敌手A的优势Padv是可忽略的，即本文提出的基于身份的环签名方案满足匿名性。

4.3.2不可伪造性

5结语

格上基于身份的环签名方案是数字签名的一项重要发展，能够抵抗量子攻击，以保证电子交易和云计算的安全性。本文基于SIS困难假设，依据Ducas等[13]提出的理想格技术，构造了一种基于身份的可在标准模型下给出安全性证明的环签名方案。该方案具有较短的公钥和签名的私钥，在一定程度上缩减了签名长度，提高了运算效率，并且可以抵抗选择身份和消息攻击。本文提出的签名方案可以延拓为理想格上基于身份的代理（盲）签名方案、签密方案、代理（盲）签密方案等，下一步的工作是设计构造密钥和签名更短的签名方案和理想格上的签密方案。

参考文献：

[1]

CHAUM D， VAN HEYST E. Group signature [C]// EUROCRYPT91： Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques. Berlin： Springer， 1991： 257-265.

[2]

RIVEST R L， SHAMIR A R， TAUMAN Y. How to leak a secret [C]// ASIACRYPT01： Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security： Advances in Cryptology. Berlin： Springer， 2001： 552-565.

[3]

ZHANG F， KIM K. IDbased blind signature and ring signature from pairing [C]// ASIACRYPT02： Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security： Advances in Cryptology. Berlin： Springer， 2002： 533-547.

[4]

CHOW S S M， YIU S M， HUI L C K. Efficient identity based ring signature [C]// ACNS05： Proceedings of the Third International Conference on Applied Cryptography and Network Security. Berlin： Springer， 2005： 499-512.

[5]

AU M H， LIU J K， YUEN T H， et al. IDbased ring signature scheme secure in the standard model [C]// IWS 2006： Proceedings of the 2006 International Workshop on Security. Berlin： Springer， 2006： 1-16.

[6]

SHOR P W. Polynomialtime algorithm for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing， 1997， 26（5）： 1484-1509.

[7]

WANG J. Ring signature and identitybased ring signature from lattice basis delegation [EB/OL]. [20151019]. http：//eprint.iacr.org/2010/378.

[8]

BOYEN X. Lattice mixing and vanishing trapdoors： a framework for fully secure short signatures and more [C]// PKC 2010： Proceedings of the 2010 Public Key Cryptography. Berlin： Springer， 2010： 499-517.

[9]

田苗苗，黄刘生，杨威.高效的基于格的环签名方案[J].计算机学报，2012，35（4）：712-718.（TIAN M M， HUANG L S， YANG W. An efficient ring scheme based on lattice [J]. Chinese Journal of Computers， 2012， 35（4）： 712-718.）

[10]

CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees or how to delegate a lattice basis [C]// EUROCRYPT10： Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 523-552.

[11]

李玉海，田苗苗，黄刘生.一种格上基于身份的环签名方案[J].小型微型计算机系统，2013，34（8）：1768-1771.（LI Y H，TIAN M M， HUANG L S. An identity based ring signature scheme on lattice [J]. Journal of Chinese Computer Systems，2013， 34（8）： 1768-1771）.

[12]

MICCIANCIO D， PEIKERT C. Trapdoors for lattices： simpler， tighter， faster， smaller [C]// EUROCRYPT12： Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 700-718.

[13]

DUCAS L， MICCIANCIO D. Improved short lattice signatures in the standard model [C]// Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2014： 335-352.

[14]

杨丹婷，许春根，徐磊，等.理想格上基于身份的签名方案[J].密码学报，2015，2（4）：306-316.（YANG D T， XU C G， XU L， et al. Identitybased signature scheme over ideal lattices [J]. Journal of Cryptologic Research， 2015， 2（4）： 306-316.）

[15]

BENDER A， KATZ J， MORSELLI R. Ring signatures： stronger definitions and constructions without random oracles [J]. Journal of Cryptology， 2009， 22（1）： 114-138.

[16]

RCKERT M. Strongly unforgeable signatures and hierarchical identitybased signatures from lattices without random oracles [C]// PQC 2010： Proceedings of the 2010 PostQuantum Cryptography. Berlin： Springer， 2010： 182-200.

[17]

李明祥，刘阳，赵秀明.高效的格上基于身份的签名方案[J].计算机应用研究，2014，31（3）：825-828.（LI M X， LIU Y， ZHAO X M. Efficient identitybased signature scheme from lattices [J]. Application Research of Computers， 2014， 31（3）： 825-828.）