量子安全的轻量级密码与安全协议

The emergence of quantum computers poses a deadly threat to the existing widely-used public-key cryptography based on hard problems in number theory. With the advent of the era of quantum computing, it is of great urgency to design secure post-quantum cryptographic algorithms and protocols in quantum computing environment. The U.S. government is soliciting the quantum-resistant cryptographic algorithms. In view of the disadvantages of the current post-quantum public-key cryptography, such as the key sizes are large and the concrete security is unclear, we will research into quantum-immune lightweight public-key schemes and protocols in this project. We will first reduce the key sizes by using quantum-resistant problems with special structures, then propose provably secure cryptographic schemes according to security reduction theory, then choose parameters for the schemes by analysing the concrete security and quantum complexity of the hard problems, and finally implement highly efficient and secure post-quantum public-key cryptosystems via optimization. The specific research contents are as follows: 1. Design and analysis of lattice-based cryptographic schemes and protocols; 2. Algebraic analysis and design of public-key cryptosystems based on error-correcting codes; 3. Algebraic analysis and design of multivariate public-key cryptosystems; 4. Computational complexity theory in quantum computing environment; 5. Implementation and test of post-quantum cryptosystems. The research of this project will effectively promote the development of practical post-quantum cryptography and lay the foundation for the standardization of post-quantum cryptography.

量子计算机的出现将对现有广泛使用的基于数论困难问题设计的公钥密码算法产生致命的威胁。随着量子计算时代的来临，设计量子计算环境下安全的后量子密码算法与协议已经迫在眉睫，美国政府正在征集相关密码标准。针对当前后量子公钥密码存在的密钥规模大、具体安全性不清晰的缺点，本项目研究量子安全的轻量级公钥密码和安全协议，通过寻找特殊结构的抗量子困难问题缩减密钥规模，利用安全归约理论提出可证明安全的密码方案，然后分析困难问题的具体安全性和量子复杂度选取方案的参数，最后通过优化的方法实现高效安全的后量子公钥密码系统。具体内容包括：基于格的公钥密码与安全协议的分析与设计；基于纠错码的公钥密码的代数分析与设计；多变量公钥密码的代数分析与设计；量子计算环境下相关的计算复杂性理论；后量子密码系统的实现与测试。本项目的研究将有力地推动实用后量子密码的发展，为后量子密码的标准化打下基础。

量子算法对现实世界广泛使用的重要密码算法RSA、ECC产生致命的威胁，随着量子计算技术的不 断突破，设计量子计算环境下安全的后量子密码算法与协议已经成为密码应用的大事件，美国NIST已经和将继续标准化若干后量子密码算法。针对当前后量子公钥密码存在的密钥规模大、具体安全性不清晰的缺点，本项目聚焦量子安全的轻量级公钥密码和安全协议，寻找特殊结构的抗量子计算困难问题缩减密钥规模，提出高效安全的密码方案，分析计算困难问题的具体安全性和量子复杂度来选取方案的参数，优化实现高效安全的后量子公钥密码系统。本项目围绕量子安全的轻量级密码的设计与分析问题进行研究，取得如下重要进展。通过引入临时密钥以及双重Σ-协议这一崭新路线，规避了格签名方案设计中拒绝采样的使用，得到了能够在单一简单计算模块中同时实现相同高安全强度签名和加密的轻量级后量子密码方案；基于后量子重要的计算困难问题——LWE、LPN、SIS，提出了若干安全高效的后量子密码方案；基于我们独特的格分析方法，对两类重要的隐藏数问题的求解难度进行了分析，对一个持续近20年的密码学猜想给出了否定的回答，同时解决了持续33年的种子密钥恢复难题；对一定比例的理想格SVP问题给出多项式时间的求解算法，揭示了数域中素理想SVP问题的计算复杂性与其分解群之间的深刻联系；针对NIST系列格加密征集算法提出了精确评估密钥不匹配攻击所需问询次数的系统性方法；对美国NIST格签名标准算法Dilithium提出通用的部分信息泄露攻击；我们也提出量子公钥加密协议、盲量子计算协议、量子基于身份加密方案以及基于物理法则的后量子选举系统。此外，我们开发了基于编码和多变量的后量子密码自动化检测平台，用于评估算法的具体安全性，服务国家战略需求。本项目的研究促进了我国的后量子密码发展，为我国后量子密码标准的制定贡献了力量。