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

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

步骤设计了对应的量子线路, 如图 7 所示.
量子 LLL 算法中 Size-reduce 过程代表格基向量满足 Lovász 条件时运行的约减步骤, Swap 过程代表不满足
时进行的向量交换步骤. 量子 LLL 使用 r dlog ˜ B+r log ˜ B+max(d,r)·m 个量子比特, 其中 ˜ B 是初始基向量长度上
2
2
4
界, m 是算法所计算数值的比特长度, r 是格的秩, d 是维度. 文献 [61] 进一步设计了可逆的 LLL 线路, 减小了量子
存储的消耗量. 总体上, 格基约化较为依赖经典算法结构, 其对应量子算法的设计也主要集中于各个步骤的量子线
路实现. 在 LLL 算法的量子化的基础上, 如何应用各种优化的格基约化算法和量子线路设计技巧 [85–88] 改进现有的
量子格基约化算法, 是未来的潜在研究课题之一.

|L |L
Size-reduce Size-reduce
GSO Swap
|B |B
|M Lovász |M

|Lov |Lov

|I +1 max |K
≤ n
|I –2 –2) –1 –2 –2) –1
|ctl 1 |ctl 1
≤|I ≤|I ≤|I ≤|I
0≤|J (0≤|J 0≤|J (0≤|J
|ctl 2 |ctl 2
|J |J
j 循环 j 循环
图 7 量子 LLL 算法线路图

格密码研究中的另一种重要格基约化算法是 BKZ 算法, 其流程结合了 LLL 约化算法与局部枚举、筛法等
SVP 求解算法, 在约化效果与时间消耗等方面达到较好平衡. 理论上, BKZ 格基约化算法在量子计算模型下一方
面可受益于本节介绍的 LLL 量子化改进, 另一方面可受益于前两节介绍的量子筛法、量子枚举改进. 当前对
SVP 量子求解算法的研究多数关注各环节本身的进一步加速与分析, 对 BKZ 综合多方面量子改进的整体优化与
分析尚待深入, 这也是 SVP 量子求解算法领域未来的潜在研究课题之一.

5 LWE 问题的量子算法
使用以上介绍的量子筛法、量子枚举、量子格基约化这 3 类算法可以解决精确或近似版本的 SVP, 进而通过
格问题的归约解决大部分格上困难问题, 这也是格上困难问题的一种通用解法. 除此之外, 针对特定格上困难问题
专门设计的量子求解算法也是格上困难问题量子求解算法的重要组成部分. 目前, 越来越多的后量子公钥密码方
案选择 LWE 问题或其变形作为安全性基础, 对该问题的量子求解算法作为重要的密码分析手段也成为研究热
点. 设 k、q 是整数, s ∈ Z 是未知秘密向量, e ∈ Z 是未知噪音向量, 给定已知矩阵 A = {a i } ∈ Z m×k 和已知向量
k
k
q q q
b ≡ A· s+e mod q, LWE 问题要求计算秘密向量 s 和噪音向量 e. 该问题有多种求解方法, 除了归约至格上 SVP 的
通用求解方法 (称为 Primal 方法), 还存在 BKW 算法、对偶算法等专门的求解方法, 其具体关系如图 8 所示, 对这
些算法的量子加速是格上困难问题量子求解算法的重要研究内容. 近年来基于变分量子算法的 LWE 求解研究也
得到了学术界的关注.
按照求解方法和问题归约路径, 可将常用的量子 LWE 求解方法分为以下几种: (1) 基于量子 SVP 求解的攻
击, 遵循 Primal 攻击的基本思想, 实质上是量子筛法等量子 SVP 算法在 LWE 中的应用; (2) 量子 BKW 算法, 该算
法的量子加速有两个方面, 其一是格向量组合的量子加速, 其二是量子傅里叶变换的加速; (3) 量子对偶攻击, 该方