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

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

结果存储在列表中, 最后使用 Grover 量子搜索算法寻找符合条件的解. 对于长度为 N = 2 的输入, 量子傅里叶变
n
2
换的时间复杂度为 O((log N) ), 相比经典的快速傅里叶变换复杂度 O(Nlog N) 有指数级加速.
2
2
相比将格上困难问题归约为 SVP 的通用解法, 专用的 LWE 量子求解算法立足于 LWE 问题特殊结构, 通过
量子搜索、量子傅里叶变换等技术降低问题复杂度. 除了以上 LWE 量子求解方法, 研究者还基于量子计算特性
设计了更多特殊的求解算法. 如 Lv 等人 [97] 结合编码方法和变分量子算法提出了一种 LWE 量子求解方法, 使用两
个量子比特编码格基组合系数的随机浮动, 将向量扰动过程进行指数级加速. 作者还利用这种扰动加速了对
LWE 的 Primal 求解方法. 未来 LWE 量子求解发展可以探索的问题包括根据具体密码方案中 LWE 的特殊结构调
整求解算法 [64,98] 、 采用最新的量子加速技术 [99] 提高量子求解算法效率等, 本节总结了量子模型下 LWE 求解研究
的发展概况, 如图 9 所示.

Esser 等人 , 2018 Liu 等人 , 2022
[41]
[43]
向量组合应用 Grover 搜索 量子 BKW 复杂度优化
Guo 等人 , 2017
[91]
BKW 算法 向量组合方法
编码 BKW 中应用量子筛法
[42]
Albrecht 等人 , 2022
LWE 求解 对偶攻击 傅里叶变换
量子增强对偶攻击
Lv 等人 , 2022
[97]
变分量子算法
利用变分量子算法的 LWE 求解
图 9 量子 LWE 求解算法发展概况

6 NTRU 量子密钥恢复

本节介绍针对 NTRU 公钥密码体制 [29] 的量子密钥恢复算法, 包括利用 Grover 量子搜索的量子密钥恢复和利
用量子碰撞的量子密钥恢复. NTRU 提出于格理论发展早期, 至今仍是重要的格密码之一, 并且是 NIST 于 2022
年公布的后量子公钥密码标准之一. 同样入选 NIST 标准算法的 Falcon 数字签名也是构造在 NTRU 格上的. 虽然
NTRU 的安全性基础是格上 SVP, 但除了通用的归约至 SVP 求解还存在基于量子搜索算法的密钥恢复方法, 如
图 10 所示.

NTRU 体制攻击

通用攻击方法 专用攻击方法

归约至格上 SVP 密钥穷举 归约至碰撞
搜索 搜索
经典 SVP 量子 SVP
求解算法 求解算法 Grover 量子搜索 Claw-Finding 搜索
图 10 NTRU 量子密钥恢复分类

对 NTRU 进行密钥恢复的基本操作是在 N 维模多项式环上进行的 [100] . 定义 L(d 1 ,d 2 ) 为含有 d 1 个+1 系数、
d 2 个–1 系数, 其余全为 0 的三元多项式集合. 定义素数 q 和小整数 p. NTRU 中, 接收方 Bob 选取多项式, g(x) ∈
L g (d g ,d g ), 其中 、 d g 是给定参数, 多项式对 f, g 是私钥. Bob 分别求 f 模 p、q 的逆多项式 f p (x)、 f q (x), 并在 N 维
d f
模 q 多项式环上做卷积计算, 得到 h(x) ≡ p f q (x)g(x) mod(x −1) 作为公钥. 为了加速私钥 f 的生成, NTRU 在实现
N

中通常采用乘积多项式模式: 选择 3 个小系数多项式 f 1 (x)、 f 2 (x)、 f 3 (x) 组合得 f(x) = f 1 (x) f 2 (x)+ f 3 (x). 针对这种