Page 401 - 《软件学报》2026年第1期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(1):398−424 [doi: 10.13328/j.cnki.jos.007437] [CSTR: 32375.14.jos.007437] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
格上困难问题量子求解算法综述

曹金政 1 , 罗向阳 1 , 陈晓峰 2 , 程庆丰 1

1
(信息工程大学 网络空间安全学院, 河南 郑州 450001)
2
(西安电子科技大学 网络与信息安全学院, 陕西 西安 710071)
通信作者: 程庆丰, E-mail: qingfengc2008@sina.com

摘 要: 随着基于格的后量子密码体制快速发展, 格上困难问题求解算法已成为评估后量子密码方案安全性的关
键技术. 当前, 经典计算模型下已存在枚举、筛法、格基约化等格上困难问题求解算法, 同时量子筛法、量子枚举
等格上困难问题量子求解算法正逐步引起关注. 围绕后量子密码研究中涉及的格上困难问题, 对格上困难问题量
子求解算法给出综述. 首先, 分类整了格上困难问题量子求解算法研究现状. 其次, 梳理各类格上困难问题量子求
解算法的设计思路和应用的量子计算技术, 并总结各类格上困难问题量子求解算法的复杂度. 最后, 展望格上困难
问题量子求解算法的未来发展趋势.
关键词: 格公钥密码; 格上困难问题; 量子算法
中图法分类号: TP309

中文引用格式: 曹金政, 罗向阳, 陈晓峰, 程庆丰. 格上困难问题量子求解算法综述. 软件学报, 2026, 37(1): 398–424. http://www.jos.
org.cn/1000-9825/7437.htm
英文引用格式: Cao JZ, Luo XY, Chen XF, Cheng QF. Survey on Quantum Algorithms for Solving Hard Problems in Lattice. Ruan
Jian Xue Bao/Journal of Software, 2026, 37(1): 398–424 (in Chinese). http://www.jos.org.cn/1000-9825/7437.htm

Survey on Quantum Algorithms for Solving Hard Problems in Lattice
1
1
2
CAO Jin-Zheng , LUO Xiang-Yang , CHEN Xiao-Feng , CHENG Qing-Feng 1
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

为应对量子计算对经典密码的安全威胁 [1−5] , 基于格上困难问题设计的后量子格密码凭借抵抗量子计算的特
性成为研究热点 [6−8] . 美国国家标准与技术研究院经过 2012–2022 年的多轮后量子密码算法征集与遴选后, 于
2023 年 8 月发布了 3 种后量子公钥密码方案, 其中 2 种方案是基于格设计的 [9−11] , 足以体现格密码的重要地位, 格

* 基金项目: 国家自然科学基金 (62472438, 62172433, 62172435); 国家重点研发计划 (2022YFB3102900); 河南省自然科学基金 (242300421414)
收稿时间: 2024-01-18; 修改时间: 2024-04-07; 采用时间: 2025-03-28; jos 在线出版时间: 2025-07-30
CNKI 网络首发时间: 2025-07-31