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

曹金政 等: 格上困难问题量子求解算法综述 413

5. 输出⊥
6. 在 L 中选取新生成的 k 维 ′ LWE 采样 (a i ,b i )
(区分阶段)
′
7. 使用傅里叶变换以 m BKW 个新 LWE 采样作为输入并求解, 作为原 LWE 解的 k 个分量
8. 递归进行前两阶段, 恢复完整的秘密向量 s
9. 输出 s

上述量子 BKW 算法在经典算法的基础上, 通过反复调用量子 Grover 搜索实现了格向量组合环节的平方级
加速. 更进一步, 相比原始 BKW 算法每次只组合一对向量, c-求和 BKW 每次进行 c 个向量的组合, 通过调节 c 值
可以改变算法的时间复杂度存储折中. 给定 n 维 LWE 问题, 其中模数 q = n , 噪音标准差 δ = n , 则 BKW 算法的
ν q
ν δ
时间复杂度 T = 2 θ(1+ϵ) 和空间复杂度 M = 2 µ(1+ϵ) 可以表示为:

1 ν q 1 ν q
θ = t · · ·n, µ = m· · ·n,
2 1 2 1
ν q −ν δ + ν q −ν δ +
2 2
其中, 不同 BKW 版本的复杂度参数 t、m 如表 5 所示. 应用量子搜索方法后, BKW 算法的时间复杂度得到了平方
级的下降. 下一步量子 BKW 算法在向量组合阶段的发展方向有: (1) 给出更精确的量子 BKW 复杂度估计; (2) 参
考量子筛法等, 探索 BKW 算法结构与更多量子加速技术的融合应用.

表 5 c-求和 BKW 算法复杂度参数

类型 算法 t m 条件
原始BKW 1 1 －
经典算法 logc
c-求和BKW logc c ⩾ 2
c−1
1
原始BKW 1 －
2
量子算法 clogc logc
c-求和BKW c ⩾ 2
2(c−1) c−1

5.2 基于量子傅里叶变换的 LWE 求解
第 5.1 节介绍了 BKW 第 1 阶段中利用 Grover 量子搜索算法加速向量组合的算法原理和复杂度. 第 1 阶段之
后, BKW 第 2 阶段需要使用快速傅里叶变换恢复秘密向量, 此过程也可以使用量子加速技术, 即量子傅里叶变换
(quantum Fourier transform, QFT) [92–94] . 量子傅里叶变换不仅应用于求解 LWE 的量子 BKW 算法, 同时也是求解
LWE 的对偶攻击 (dual attack) [42,95] 的重要组成部分. 对偶攻击经过 Guo 等人 [96] 的改进, 已经在求解 LWE 的效率上
超过 Primal 方法; Albrecht 等人 [42] 指出, 对偶攻击能够量子傅里叶变换结合; Pouly 等人 [95] 给出了对偶攻击的理论
证明. 下面以对偶攻击为例介绍量子傅里叶变换在求解 LWE 问题的应用.
对偶攻击的基本思路是将 LWE 转化为格上小整数解问题, 并用傅里叶变换找到秘密向量. 首先, 将 A 矩阵分

块表示为 A = [A 0 |A 1 ], 并将 s 相应地分段表示为 s = [s 0 |s 1 ], 则有 b ≡ A 0 · s 0 + A 1 · s 1 +e mod q. 随后, 要求找到向量

T
x, y 使得 x · A 0 ≡ y mod q, 这一操作相当于求小整数解问题, 可以通过对偶格上的格基约化实现. 此时有等式 < x, b >
T T T T
≡ x · A 0 · s 0 + x · A 1 · s 1 + < x,e >=< y, s 0 > +x · A 1 · s 1 + < x,e >. 接下来, 对任意可能的 s 1 计算 < x, b > −x · A 1 · s 1 .
T
s
对随机的 s 1 值, 得到的值均匀随机分布; 而当 s 1 猜测恰好是秘密向量 的对应分量时, 得到的 < x, b > −x · A 1 · s 1
s 1 的过程可以通过傅里叶变换实现, 进而使用量子傅里叶变换达到量子加速效果.
是一个小值. 这个猜测
要将量子傅里叶变换应用于对偶攻击, 需解决的关键问题是计算余弦值 cos(2π(< w i , b >)/q). 定义 f W (b) =
1 ∑ N−1
ˆ
ˆ
n
cos(2π(< w i , b >)/q). 对任意 ϵ, δ > 0, 存在量子算法可以实现预言 O, 使得给定 b ∈ Z 后得到输出 O(b), 以
N i=0 q
|O(b)− f W (b)| ⩽ ϵ, 此结果保证了量子傅里叶变换可以适用于对偶攻击. 在进行傅里叶变换后, 将
ˆ
1−δ 的概率满足