高效的格上基于身份的签名方案.doc

高效的格上基于身份的签名方案*李明祥，刘 阳，赵秀明（河北金融学院 信息管理与工程系，河北 保定 071051）摘 要：基于身份的签名(IBS)方案可广泛应用于移动电子商务等资源受限的场合。本文首先利用Micciancio和Peikert在Eurocrypt12上提出的陷门生成算法GenTrap、原像抽样算法SampleD和陷门委托算法DelTrap构造了一个新的基于格的IBS方案；然后在标准模型下基于小整数解(SIS)问题证明了所提出的方案满足选择身份和固定选择消息攻击下的强不可伪造性；最后比较了所提出的方案与现有同类方案的计算性能，结果表明本文所提方案的效率最高。关键词：签名；基于身份；强不可伪造性；格中图法分类号：TP309.2 文献标识码：AEfficient identity-based signature scheme from latticesLI Ming-xiang*, LIU Yang, ZHAO Xiu-ming(Department of Information Management and Engineering, Hebei Finance University, Baoding Hebei 071051, China)Abstract: Identity-based signature (IBS) schemes can be widely used in the resource-constrained applications, such as mobile e-commerce. At first, a new lattice based IBS scheme was constructed by using trapdoor generation algorithm GenTrap, preimage sampling algorithm SampleD, and trapdoor delegation algorithm DelTrap which were proposed on Eurocrypt 2012 by Micciancio and Peikert. Secondly, the proposed scheme was proved to satisfy the strong unforgeability against selective identity and static chosen message attacks under the small integer solution assumption in the standard model. Finally, the computing performance of the proposed scheme was compared with the existing similar schemes. The comparison result shows that the proposed scheme enjoys the highest computation efficiency.Key words: signature; identity-based; strong unforgeability; lattices收稿日期：2013-4-17；修回日期：2013-5-22 基金项目：国家“九七三”重点基础研究发展规划项目基金（2011CB311809）；国家自然科学基金面上项目（61163050）；河北省教育厅资助科研项目（ZH2011216）。作者简介：李明祥（1968），男，山东济宁人，副教授，博士，主要研究方向为公钥密码学、金融密码学；刘阳（1986），女，硕士，助教，主要研究方向为入侵检测、数据挖掘；赵秀明（1965），女，硕士，教授，主要研究方向为云计算、云安全。0 引言基于身份的密码(Identity-based cryptography, IBC)体制1可广泛应用到各种资源受限的环境中。目前人们利用双线性对已设计了大量的基于身份的密码方案，如基于身份的加密方案2、基于身份的签名(Identity-based signature, IBS)方案3等。可是双向性对的计算效率却很低，因此人们一直在寻求利用其他方法构造IBC方案。基于格的密码体制是少数几种抗量子计算的经典公钥密码体制之一，由于量子计算机的出现只是时间问题，因此基于格的密码体制受到了人们的普遍关注。其中基于格的IBC方案的设计与分析更是受到了人们的格外关注。Ajtai4在STOC96上定义了小整数解(Small integer solution, SIS)问题，并开创性地证明了该问题在平均情况下是困难的。Ajtai5于1999年提出了一种陷门生成算法，Alwen和Peikert6于2009年又改进了Ajtai的陷门生成算法5。Gentry和Peikert7在STOC08上基于SIS问题提出了一种带原像抽样的陷门单向函数，并据此构造了一个基于格的签名方案，该方案在随机预言模型下是强不可伪造的。Cash和Hofheinz8在Eurocrypt10上根据Gentry等的原像抽样陷门函数7提出了一种格基委托技术，并据此构造了一个基于格的签名方案，该方案在标准模型下是存在性不可伪造的。Micciancio和Peikert9在Eurocrypt12上通过定义新颖的陷门概念，而设计了简单高效的陷门生成算法GenTrap、原像抽样算法SampleD以及陷门委托算法DelTrap等，并据此构造了一个高效的基于格的签名方案，该方案在标准模型下是强不可伪造的。最近，利用Gentry等7提出的原像抽样陷门函数，Xia与Yang10构造了一个基于格的IBS方案，并在随机预言模型下证明了该方案的存在性不可伪造性；根据Cash等8提出的格基委托技术，Liu与Hu11构造了一个基于格的IBS方案，并在标准模型下证明了该方案的强不可伪造性。本文利用Micciancio等10提出的有关算法，构造了一个高效的基于格的IBS方案，并在标准模型下证明了所提IBS方案的强不可伪造性。与现有其他同类IBS方案10, 11相比，本文所提IBS方案要高效得多。1 预备知识1.1 格定义1 设为一组线性无关的向量，则以为基的格及其对偶格定义为，.定义2 对整数与矩阵，定义两个整数格，.这两个格是对偶的，即，。1.2 SIS问题定义3 给定整数、矩阵以及实数，求解一个非零整数向量，满足，且，即。该问题即为SIS问题。1.3 离散高斯分布定义4 对任意的向量、实数和维格，定义上的高斯函数为，其中为中心，为标准差。当下标和为1和时，可省略不写。定义5 对任意的向量、实数和维格，定义上的离散高斯分布为，其中。与上面一样，也可省略下标或。定义6 对任意的维格及实数，光滑参数为最小的实数，使得。通俗地说，光滑参数是为了在上得到均匀分布而必须添加的高斯噪声的大小。1.4 几个重要结论引理7（文献7） 对任意的维格及实数，有于是对任意函数，存在可以忽略的，使得，其中。引理8（文献7） 存在概率多项式时间算法，它输入维格的基、实数和向量，而能依分布输出抽样。引理9（文献12） 对于任意维格、向量以及实数与，有引理10（文献9） 假设是子高斯随机矩阵，并知其参数，则存在通用常数，使得对任意，都有矩阵的奇异值，而该式不成立的概率至多为。引理11（文献9） 设为的基，为的陷门，且其标记为，则格可由基产生，其中是的任意一个解。而且在以适当顺序正交化时，满足。2 IBS方案的形式化定义与安全模型2.1 形式化定义一个IBS方案由4个算法组成，即系统参数生成算法Setup、私钥提取算法Extract、签名算法Sign和签名验证算法Verify。输出系统参数和主密钥；输出用户的私钥；输出用户对消息的签名；输出1当且仅当是用户对消息的有效签名。2.2 安全模型根据文献13提出的选择身份(Selective identity)安全概念和文献14提出的固定选择消息(Static chosen message)安全概念，我们可定义IBS方案在选择身份和固定选择消息攻击下的强不可伪造性(SU-SMA-SelectiveID)。该安全概念可通过一个在敌手和挑战者之间的游戏予以定义。初始阶段：将发送给，其中为目标身份。固定签名答复：首先运行输出和，然后运行输出，运行输出，最后将和签名发送给。私钥提取询问：输出，运行输出，并将私钥发送给。其他签名询问：输出，运行输出，运行输出，并将签名发送给。伪造阶段：输出。如果，并且不是某次签名询问的结果，则称在游戏中获胜。我们定义敌手的优势为它在上述游戏中获胜的概率。定义12 在上述游戏中，如果不存在这样的敌手，其优势至少为，运行时间至多为，私钥提取询问的次数至多为，签名询问的次数至多为，则称该IBS方案在SU-SMA-SelectiveID模型下是安全的。3 一个新的基于格的IBS方案Setup算法：已知安全参数，原语矩阵，其构造可参阅文献9。令，分布，选择矩阵，运行陷门生成算法GenTrap输出矩阵和陷门。任意选择矩阵和，其中为用户身份的长度，为消息的长度，选择向量。系统参数，主密钥。Extract算法：设用户，令，则由矩阵的陷门运行陷门委托算法DelTrap可输出矩阵的陷门，即用户的私钥。Sign算法：设用户，消息，令，因由矩阵的陷门通过添加零行可得到矩阵的陷门，故根据矩阵的陷门运行原像抽样算法SampleD可输出分布上的抽样，即用户对消息的签名。Verify算法：对用户在消息上的签名来说，若，且，其中矩阵的定义如上所述，则签名是有效的，否则签名是无效的。4 方案分析4.1 正确性定理13 本文提出的IBS方案是正确的。证明：因为，而，所以根据引理10知。由引理11可得，再由引理7可知。又，因此有，故据引理8可知Extract算法能正确执行，且由引理10知 。故，又，所以，故Sign算法能正确执行，且有，另据引理9可知。因此上述IBS方案是正确的。 4.2 安全性定理14 假设问题是难解的，其中，则本文提出的IBS方案在SU-SMA-SelectiveID模型下是安全的，其中，和分别为私钥提取询问和签名询问的次数。证明：设敌手在SU-SMA-SelectiveID模型下能攻破本文所提出的IBS方案，且其优势至少为，则可构造多项式时间算法求解SIS问题。可分为两种类型，其一是在未询问过签名的消息上输出伪造，另一是在已询问过签名的消息上输出伪造。显然，在任一情况下输出有效伪造的概率都至少为。的输入为矩阵，即一个SIS问题实例。为利用求解该SIS问题实例，应当模拟的挑战者。与第一种类型敌手的交互过程如下：初始阶段：接收输出的，其中为目标身份。固定签名答复：首先根据目标身份产生公开参数。对于，选取，令，其中.环同态的定义可参阅文献9。容易看出，对，有；对，有 ，故时，是可逆的。然后根据消息生成公开参数。计算串的集合，不是任意消息的前缀，且是满足此条件的最短串。集合不难计算出来，且有，计算可参阅文献8。任意选择，并记。对于，选取，令，其中.可以看出，对任意消息来说，如果以为前缀，则有；如果不以为位前缀，而以为位前缀，则有 ，因此不以为前缀时，是可逆的。将所产生的系统参数发送给。为生成在上的签名，计算因为的位前缀不是，所以是可逆的，因此为对应的陷门，并且有，又知，故可利用SampleD算法产生，即用户在消息上的签名。把所产生的签名发送给。私钥提取询问：当敌手询问用户的私钥时，计算由于是可逆的，因此为对应的陷门，并且有，又知，所以可利用DelTrap算法产生用户的私钥。其他签名询问：当询问用户在消息上的签名时，不失一般性，假设没有询问过的私钥，首先如私钥提取询问一样产生的私钥，然后再根据Sign算法产生用户在消息上的签名。伪造阶段：输出伪造，且有。若限制必须以为前缀，则敌手伪造有效签名的概率至少为。在这种情况下，能求解它的SIS挑战实例，即所以，令，则有， 。因为所以其最大为，则即为所给SIS问题实例的一个解。与第二种类型敌手的交互过程如下：接收输出的，并从所接收的消息中任意选取一个消息。根据目标身份产生。令，利用产生。选择，计算。设定消息的签名为，而应用上述方法产生其他消息的签名。另外，对于私钥提取询问和其他签名询问，都可应用上述方法作出相应的回答。在伪造阶段，输出伪造，其中。若限制，则敌手伪造有效签名的概率至少为。在这种情形下，故 ，令，则有，。由于，因此 ，则即为所给SIS问题实例的一个解。 4.3 效率本文提出的IBS方案在用户私钥提取阶段和签名阶段仅需少量SampleD抽样运算，而最近提出的其他基于格的IBS方案10, 11，不仅需要SampleD抽样运算，而且需要ToBasis运算8和判断向量的线性无关性等比较费时的运算。因此本文提出的IBS方案比其他同类IBS方案的运算速度要快得多。由于基于身份的公钥密码体制主要应用到各种资源受限的环境中，因而本文所提出的方案比其他同类方案更适合在实际场合应用。5 结束语本文提出了一个高效的基于格的IBS方案，并在标准模型下证明了它满足在选择身份和固定选择消息攻击下的强不可伪造性，与现有同类方案相比，本文所提方案具有更高的运算效率。另外，容易看出，本文所提方案不难扩展成基于分级身份的签名(Hierarchical identity-based signature, HIBS)方案15。我们下一步将探讨基于格的IBS方案在电子商务、云计算等领域中的应用，以便有效解决这些领域提出的与安全有关的问题。参考文献：1 SHAMIR A. Identity-based cryptosystems and signature schemesC/Proc of Crypto 1984, LNCS 196. Berlin: Springer-Verlag, 1984: 47-53.2 WATERS B. Efficient identity-based encryption without random oraclesC/Proc of Eurocrypt 2005, LNCS 3494. Berlin: Springer-Verlag, 2005: 114-127.3 PATERSON K G, SCHULDT J C N. Efficient identity-based signatures secure in the standard modelC/Proc of the 11th Australasian Conference on Information Security and Privacy, ACISP 2006, LNCS 4058. Berlin: Springer-Verlag, 2006: 207-222.4 AJTAI M. Generating hard instances of lattice problemsC/Proc of the 28th Annual ACM Symposium on Theory of Computing (STOC96). New York: ACM Press, 1996: 99-108.5 AJTAI M. Generating hard instances of the short basis problemC/Proc of the 26th International Colloquium on Automata, Languages and Programming (ICALP99), LNCS 1644. Berlin: Springer-Verlag, 1999: 1-9.6 ALWEN J, PEIKERT C. Generating shorter bases for hard random latticesJ. Theory of Computing Systems. 2011, 48(3): 535-553.7 GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructionsC/Proc of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008. New York: ACM Press, 2008: 197-206.8 CASH D, HOFHEINZ D, KILTZ E, et al. Bonsai tree, or how to delegate a lattice basisC/Proc of Eurocrypt 2010, LNCS 6110. Berlin: Springer-Verlag, 2010: 523-552.9 MICCIANCIO D, PEIKERT C. Trapdoors for lattices: simpler, tighter, faster, smallerC/Proc of Eurocrypt 2012, LNCS 7237. Berlin: Springer-Verlag, 2012: 700-718.10 XIA F, YANG B, SUN W, et al. An efficient identity-based signature from lattice in the random oracle modelJ. Journal of Computation