基于LWE的数字签名方案

黄建鑫 李豪 罗烨 白凤娥

摘要：数字签名是实现身份识别、安全计算、信息可信发布的基本密码原语。现有签名方案大多是基于大整数因式分解和离散对数问题。但随着量子技术的实现与发展，这些方案都不能抵抗量子计算攻击。该文基于LWE的数字签名方案，该方案的安全性基于格的最坏情况难解性LWE问题，具有较好的抗量子特性。

关键词：格；数字签名方案；LWE；公钥密码体制；hash函数

中图分类号：TN918.91 文献标识码：A 文章编号：1009-5039（2018）17-0047-03

Abstract： Digital signature is the basic cryptic primitives for identity identification， security calculation and information trustworthiness release. Most of existing signature schemes are based on big integer factorization and discrete logarithm problem. But with the development and implementation of quantum technology， these schemes will be cracked by quantum computation attacks. We proposed a signature scheme based on LWE problem and its security is based on solving lattice problem in worst case. So， our scheme is good at anti-quantum attack.

Key words： lattice； digital signature scheme； LWE； public key cryptosystem； hash function

1 引言

计算机和网络技术的发展将人类带入信息化社会，随之而来的是备受關注的信息安全问题。现代密码学已成为信息安全技术的核心，数字签名是现代密码学主要研究的内容之一。数字签名技术在身份识别和认证、数据完整性、抗抵赖等方面具有其他技术所无法替代的作用，它在电子商务和电子政务等领域有着极其广泛的应用。[1]数字签名技术能够进行技术验证，这是书写签名与印章签名所不具有的优点。数字签名技术不仅具有更强的操作性、更加成熟的技术，而且也是应用最为广泛的电子签名方法，其程序更加规范与科学，能够准确地验证相关电子文件数据在传输的过程中是否被改动，从而使电子文件的真实性、完整性以及其不可抵赖性得到有效保证。数字签名在电子数据内容的认可以及对签名人身份的验证方面应用得也比较多。数字签名能够有效地避免出现收件人在收到信息之后又对其进行否认，或者是对伪造信息进行发送以及信息修改[2]等问题，对于信息安全防护、实现网络数据的保密性、完整性、不可抵赖性有着重要的作用。

数字签名就是一段数字串，它是非对称密钥加密技术与数字摘要技术的应用，是公开密钥加密技术与报文分解函数相结合的产物，其特点是只有信息的发送者才可以产生，除此之外，任何人不能对其进行伪造，这段数字串能够对发送者信息进行确认。它的安全性是基于某种数学难题，而在数字签名中都是基于传统的大整数分解问题和离散对数问题等困难问题。随着量子计算的发展，现在已经出现了解决这些困难问题的量子算法，为了避免量子时代到来后的危机，研究基于新型困难问题的算法是重中之重。

1996年，Ajtai在提出了一个开创性的结论[3]，提出了一个基于格的公钥密码方案，基于某些格问题的任意一个密码体制，其安全性等价于最难情况下的密码体制的安全性，这个结论提供了基于格的公钥密码体制的理论基础。1997年Ajtai和Dwork合作提出了基于格中最难情况下的u-SVP问题的AD加密体制[4]。Lyubashevsky证明其与GapSVP的困难性等价，从而证明了AD加密体制的安全性，但在实际应用中其存在着运算速度太慢和容易被攻破的缺陷。

2005年，Regev [5]首次提出了一类基于LWE（Learning With Error）问题的加密方案[6]，在文中Regev证明了LWE问题的困难性依赖于格上最难情况下的GapSVP问题，从而证明了其安全性。故简单而又安全的LWE问题常常被用来构造基于格的各种加密体制和签名方案。目前，LWE和SIS两个难题假设是构造格公钥密码的最实用的格难题，可证明安全理论的提出和发展，解决了密码算法或协议依靠猜想设计并反复修补漏洞的缺陷，将破解密码算法或协议的难度规约到解决“极微本原”难题，从而能够可靠地保证方案的安全性。本项目通过对于格技术的分析选取了LWE技术。

LWE加密技术方案与数字签名是本项目的主要研究对象，借鉴基于LWE的多比特IBE类和多比特BGN类及其他LWE方案，在理论和实际应用上进行更深入的研究和拓展。

而基于格的公钥密码算法是后量子密码中的典型代表，基于格的密码算法，其安全性是基于最坏情况难解性的，相比于平均情况下难解性会更安全些，并且其可以抵抗量子攻击。同时基于格的密码算法系统相对高效且易于实现。

基于LWE技术的数字签名方案，主要在数字签名中运用格技术中的LWE技术使其拥有抵御量子攻击的能力，并提高其有效性，安全性及效率。数字签名的主要过程：将摘要信息与发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过。

本文主要研究内容如下：

（1）在现有的数字签名方案中，将具有高效性、安全性、可抵御量子攻击特性的LWE加密技术融入其中，使其在性能，安全，效率等多方面得到其提升。

（2）完成数字签名过程的解析与实施，探究LWE技术融入的方向。

（3）研究私钥加密的过程中是如何结合LWE技术的加密机理。

（4）对比LWE技术中多个加密方案分类，探究并选取其中安全性与高效性最佳的方案进行实施。

（5）在研究完成后的加密方案中，设法在不影响安全性的情况下，从下面三个角度改进现有方案：①密钥及密文长度；②空间复杂性；③计算复杂性。

2 预备知识

4 基于LWE的数字签名的实现

（1）sender 对目标信息m使用hash函数加密；

（2）再对加密后的目标信息m和私钥使用sign函数生成信息；

（3）将目标信息m和该信息发送到receiver；

（4）receiver接收信息后，对m使用hash函数，并将它与sender发送的信息与公钥一起使用verify函数；

（5）使用verify函数后，若为true，则表示受到的信息是由发送方发出，为false则不是由发送方发出。

上述过程如图1所示。

5 结束语

基于LWE技术的数字签名方案，主要在数字签名中运用格技术中的LWE技术使其拥有抵御量子攻击的能力，并提高其有效性，安全性及效率。数字签名的主要过程：将摘要信息与发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息對比。

基于格的密码算法，其安全性是基于最坏情况难解性的，相比于平均情况下难解性会更安全些，并且其可以抵抗量子攻击。同时基于格的密码算法系统相对高效且易于实现。这已经成为后量子时代密码算法系统的有力竞争者。

参考文献：

[1] 赵维武，王维.数字证书验证系统的设计与实现[J].实验技术与管理， 2008，25（1）：1-1.

[2] GOLDWASSER S， MICALI S， RIVEST R L. A digital signature scheme secure against chosen-message attacks[J]. SIAM joumal on computing， 1988，17（2）：281-308.

[3] M.Ajtal. Generating hard instances of lattice Problems （extended abstract）[C]. In STOC， 1996：99-108.

[4] AjtaiM， Dwork C. A public-key cryptosystem with worst-case/average-case equivalence[C]//ACM Symposium on Theory of Computing（STOC）. EI Paso：ACM Press， 1997：284-293.

[5] Regev O. On Lattices， Learning with Errors，Random Linear Codes， and Cryptography[J]. Journal of the Association for Computing Machincry， 2009，56（6）：1-40.

[6] Daniele Micciancio and OdedRegev. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM- J. Comput. Preliminary version in FOCS 2004，37（1）：267-302.

[7] LyubashevskyV， PeikertC， RegevO. On ideal lattices and learning with errors over rings[C]//Crypto10.French Riviera：Springer， 2010：1-23.

[8] REGEV O.Onlattices，learning with errors，random linear codes，and cryptography[J]. Journal of the ACM（JACM）， 2009，56（6）：34.