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

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

法结合了格方法与傅里叶分析, 可以从这两个方面进行量子加速; (4) 变分量子算法等其他量子算法. 本节从算法
结构、主要技术、复杂度分析等方面介绍 LWE 的量子求解算法, 重点梳理量子 BKW 算法的量子采样组合过程
和量子对偶算法的量子傅里叶变换过程, 并介绍基于变分量子算法的 LWE 求解发展情况.

求解策略 问题归约 经典算法 量子算法

Primal
基于 方法 格上 BDD
格归 筛法、枚举、 对应量子 SVP
约方 格基约化等 求解算法
法 Dual 对偶格上 SIS
方法
LWE 问题
密钥区分阶段 FFT 密钥搜索 量子 FFT 搜索
基于 BKW
组合 算法
方法
向量约化阶段 组合算法 量子组合算法

图 8 LWE 问题求解主要算法分类

5.1 量子 BKW 算法

BKW 算法是一种基于组合的求解算法, 可用于求解错误学习问题 LWE 和含噪奇偶校验问题 LPN. 该算法分
′
为约化和区分两个阶段. BKW 算法的约化阶段将输入的 LWE 采样 (a i ,b i ) 进行加减组合, 最终得到满足 a 的前若
i
干个元素均为 0 的 LWE 采样 (a ,b ). 迭代进行以上描述的采样组合过程之后, BKW 算法的约化阶段输出大量的
′
′
i
i
′
LWE 采样, 其非零部分构成一个新的 LWE 实例. 新 LWE 实例的维度相对原 LWE 降低, 且新的秘密向量 s 就是
原秘密向量 s 在对应位置的分量. BKW 算法的区分阶段利用多数投票或傅里叶变换方法得到约化后新 LWE 实例
′
的解 s , 即原 LWE 问题的部分秘密向量. 由 BKW 的基本结构可知, 算法的主要计算消耗来自第 1 阶段中向量组
合的操作. Albrecht 等人 [89] 首先提出了针对 LWE 的 BKW 求解算法, 主要工作是推广求 LPN 的 BKW 算法版本,
其约化阶段只涉及 2 个向量的组合. Esser 等人 [41] 为优化 BKW 算法约化阶段的时间/空间复杂度折中, 讨论了以 c
个向量为一组进行组合, 将此过程描述为 c-求和问题 (c-sum problem, c-SP), 基于此思路提出了 c-求和 BKW 算法,
并分析了此算法的经典复杂度和量子复杂度. Wei 等人 [90] 对 BKW 求解多种参数集的复杂度进行了总结. Guo 等
人 [91] 讨论了 BKW 算法与量子筛法的结合运用.
本节介绍基于 Grover 量子搜索的量子 c-求和算法和量子 c-求和 BKW 算法, 如算法 3 和 4 所示, 主要聚焦约
化阶段, 实际上初始版本的 BKW 也可以视为 c-求和问题取 c=2 的特例. 对 c-求和 BKW 算法实现量子加速的关
键是优化第 1 阶段的量子组合方法, 即使用量子加速技术求解 c-求和问题. 设自然数 c ⩾ 2 和素数 q, 给定由 b 维

随机向量 l i 组成的列表 L = (l 1 ,..., l N ), 且定义 l −i = −l i . 对于 b 维目标向量 t, c-求和问题 c- SP b (L, t) 要求找到集合
∑
[±N] = {±1,±2,...,±N} 的大小为 c 的子集 L, 满足 l j ≡ t mod q. 一个指数组合 L 称为 c-求和问题的一个单
j∈L
解, 而完整的 c-求和问题解是 N 个不同 L 的集合. 要将 c-求和问题应用于 BKW 算法, 可以设定目标向量 t 是全零
向量. 理论分析证明当输入的 LWE 采样足够多, c-求和问题可以有解. 经典 c-求和问题求解算法通过搜索所有可

能的 {i 1 ,i 2 ,...,i c } 系数组合来找到 c-求和问题的解. c-求和问题可以使用 Grover 量子搜索算法进行加速, 但首先需
要解决的一个问题是对经典内存的大量访问. 为实现量子算法访问经典内存, 文献 [41] 使用量子随机访问存储
(QRAM) 模型. 在此量子计算模型下, 量子 c-求和算法构造了如下定义的目标函数 f: