| 摘要: |
| 随着基于格的后量子密码体制快速发展, 格上困难问题求解算法已成为评估后量子密码方案安全性的关键技术. 当前, 经典计算模型下已存在枚举、筛法、格基约化等格上困难问题求解算法, 同时量子筛法、量子枚举等格上困难问题量子求解算法正逐步引起关注. 围绕后量子密码研究中涉及的格上困难问题, 对格上困难问题量子求解算法给出综述. 首先, 分类整了格上困难问题量子求解算法研究现状. 其次, 梳理各类格上困难问题量子求解算法的设计思路和应用的量子计算技术, 并总结各类格上困难问题量子求解算法的复杂度. 最后, 展望格上困难问题量子求解算法的未来发展趋势. |
| 关键词: 格公钥密码 格上困难问题 量子算法 |
| DOI：10.13328/j.cnki.jos.007437 |
| 分类号:TP309 |
| 基金项目:国家自然科学基金 (62472438, 62172433, 62172435); 国家重点研发计划 (2022YFB3102900); 河南省自然科学基金 (242300421414) |
|
| Survey on Quantum Algorithms for Solving Hard Problems in Lattice |
|
CAO Jin-Zheng1, LUO Xiang-Yang1, CHEN Xiao-Feng2, CHENG Qing-Feng1
|
|
1.School of Cyberspace Security, Information Engineering University, Zhengzhou 450001, China;2.School of Cyber Engineering, Xidian University, Xi’an 710071, China
|
| Abstract: |
| With the rapid development of Lattice-based post-quantum cryptography, algorithms for hard problems in Lattices have become an essential tool for evaluating the security of post-quantum cryptographic schemes. Algorithms such as enumeration, sieve, and Lattice basis reduction have been developed under the classical computing model, while quantum algorithms for solving hard problems in Lattices, such as quantum sieve and quantum enumeration, are gradually attracting attention. Although Lattice problems possess post-quantum properties, techniques such as quantum search can accelerate a range of Lattice algorithms. Given the challenges involved in solving hard problems in Lattices, this study first summarizes and analyzes the research status of quantum algorithms for such problems and organizes their design principles. Then, the quantum computing techniques applied in these algorithms are introduced, followed by an analysis and comparison of their computational complexities. Finally, potential future developments and research directions for quantum algorithms addressing Lattice-based hard problems are discussed. |
| Key words: Lattice-based public key cryptography hard problem in Lattice quantum algorithm |
