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

400 软件学报 2026 年第 37 卷第 1 期

2022 年, Albrecht 等人 [42] 改进了 LWE 的对偶格攻击, 提出算法中可以使用量子傅里叶变换替代经典算法. Liu 等
人 [43] 针对 LWE 问题的特性对组合算法做了进一步优化, 使算法的应用条件得到放松. 2024 年, Chen 等人 [44] 基于
带有复高斯窗口的窗口量子傅里叶变换, 将 LWE 转换为具有纯虚高斯振幅的量子态. 进而提出针对特定参数
LWE 的多项式级量子求解算法. NTRU 方面, 2015 年, Fluhrer [45] 首次提出基于 Grover 量子搜索的 NTRU 求解, 主
要思想是根据密钥多项式的生成结构设计搜索算法. 2019 年, Laaji 等人 [46] 针对三元 NTRU 提出了两种基于
Grover 量子搜索的量子算法, 目标分别是恢复密钥与密文. 2021 年, 董经等人 [47] 提出利用 Claw-Finding 量子碰撞
算法替代 Grover 量子搜索算法进行密钥多项式搜索, 可进一步降低 NTRU 量子密钥恢复的复杂度. CVP 方面,
2016 年, Eldar 等人 [62] 利用系统范式设计了特殊参数的 CVP 量子求解算法. 2018 年, Aono 等人 [57] 使用改进的量
子枚举算法直接进行问题求解, 并探讨了一系列枚举剪枝技术的量子加速. Eldar 等人 [63] 、Allen 等人 [64] 提出并分
析了基于问题归约的最差情况问题量子求解算法. 特殊结构格方面, 2017 年, Cramer 等人 [65] 由实际密码方案的攻
击出发, 提出主理想格上 SVP 的量子求解算法, 并通过经典归约扩展至任意的理想格. 此后, Cramer 等人 [66] 、
Ducas 等人 [67] 、Boer 等人 [68] 从算法输出结果、量子比特复杂度等方面对理想格上 SVP 量子求解算法进行了分析
与提高.

格子困难问题量子算法

SVP 量子求解算法, 通过归约可求解大部分格上困难问题
2013年 2019年 2021年 2023年
量子筛法 筛法结合 Grover 搜索 元组筛法 + Grover 搜索 筛法结合量子碰撞 改进量子碰撞筛法
2018年 2018年 2023年
基于量子回溯算法
提出量子回溯算法 枚举树上进行回溯搜索 量子枚举复杂度优化
量子枚举
2020年 2021年 2023年
基于变分量子算法
绝热算法构造格枚举 优化量子格枚举算法 新算法构造、复杂度估计
2019年
量子格基约化 量子 LLL 约化算法
针对特定问题的量子求解算法, 利用问题的特殊条件构造
量子 BKW 2005年 2015年 2018年 2022年
利用 BKW 解 LWE BKW 算法改进 量子 c-求和 BKW 复杂度折中
2022年
基于变分量子算法 基于变分量子算法的 LWE求解
量子 LWE 求解
2017年 2022年
量子对偶算法
量子混合算法解 LWE 量子增强 LWE 对偶算法
量子Primal算法 归约至 SVP 应用量子筛法、
量子枚举等算法
归约至SVP 应用量子筛法、
量子枚举等算法
量子 NTRU 攻击
2019年 2020年 2022年
量子密钥搜索算法 三元 NTRU 的量子攻击 基于 Grover 搜索的 基于量子碰撞搜索
NTRU 攻击 的 NTRU 攻击
2016年
基础量子算法 量子枚举方法
CVP 求解
2016年 2022年
特殊量子算法
系统范式方法 量子归约方法
2017年 2019年 2020年 2021年
特殊结构格 主理想格上SVP求解算法 理想格上算法输出分析 理想格上算法复杂度分析 改进的理想格量子算法
图 2 格上困难问题量子求解算法发展概况

本文立足于后量子格公钥密码的安全性评估, 对格上困难问题量子求解算法的相关研究进行回顾和梳理. 首
先, 归纳格上困难问题量子求解算法分类. 其次, 介绍格上困难问题量子求解算法设计中应用到的量子加速技术,