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

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

f : X = [M 1 ] → Z g : Y = [M 2 ] → Z, 的碰撞需要查询标准预言机的次数, 则其复杂度分析如下. 搜索
,
表示找到函数
√
算法调用常数次检测算法, 而检测算法的查询复杂度为 O( M 1 M 2 /l) 次插入/删除操作和 O(l+m) 次预言机查询;
( )
2 1/3 2 量子碰撞
当 M 1 ⩽ M 2 < M 时, 令 l = m = Θ (M 1 M 2 ) ; 当 M 2 ⩾ M 时, 令 l = m = M 1 ; 综合以上分析, Claw-Finding
1 1
算法总体的时间复杂度如下:

 1/3
 O((M 1 M 2 ) log(M 1 )), M 1 ⩽ M 2 < M 2
 1

Q 2 (claw finding (M 1 , M 2 )) =  .
 1/2 2
 O(M log(M 1 )), M 2 ⩽ M
2 1
董经等人 [47] 针对 NTRU 的求解修改了 Claw-Finding 量子碰撞算法, 使其适用于 NTRU 的多比特输出形式.
√
由于算法中所搜索函数的自变量分别为 f 3 和 f 1 f 2 , 根据分析可得算法复杂度为 O( | f 1 f 2 |/N). 除了理论上的复杂度
下降, 基于 Claw-Finding 量子碰撞的 NTRU 量子密钥恢复相比基于 Grover 搜索的量子密钥恢复不需要维护大规
模的指数列表, 同时不需要强量子预言假设, 实现难度更低. 综合对 NTRU 的量子密钥恢复, 基本的设计思路是在
密钥搜索的过程中应用 Grover 搜索、量子碰撞搜索等技术, 结合量子算法的特殊性质对算法加速. 在具体的攻击
方法中, 还针对 NTRU 的密钥的特殊结构与具体量子加速方法的实现方式, 进一步提高密钥搜索攻击效率. 下一
步可以考虑优化问题归约方法, 将原问题转化为新的量子计算问题, 并利用量子碰撞的最新成果 [101–103] 进一步提
高算法效率. 此外, 可以结合侧信道信息 [104] , 改进对 NTRU 的分析方法.
7 CVP 的量子算法
最近向量问题 (closest vector problem, CVP) 是格理论中重要的基础问题, 也是多种格公钥密码设计与分析的
必要工具. 格密码研究中较受关注的是 CVP 的一种变体, 即有界距离解码问题 (bounded distance decoding, BDD).
该问题中, 需要寻找与目标向量间距离小于给定值的格向量. CVP 与多数格问题相似, 存在两类量子求解方法: 第
一, 与 SVP 类似, 使用量子枚举等通用量子求解算法进行处理; 第二, 根据问题特定结构设计直接求解算法. 本节
据此分类方法, 对 CVP、BDD 的量子求解算法进行介绍, 基本脉络如图 13 所示.

基础求解 枚举 量子枚举算法
方法 算法
量子剪枝改进
CVP 问题
基于系统范式的量子算法
特殊求解 基于归约的量子算法
方法
基于 Voronoi 图的量子算法
图 13 CVP 量子求解算法分类

CVP 的基础求解算法方面, 较有代表性的是量子枚举算法. Aono 等人 [57] 将针对 CVP 的枚举算法进行量子
化, 并进一步推广至 BDD 问题的求解. 设目标向量为 u, 量子枚举算法可输出集合 L∩S 中的向量, 其中 S =
Ball n (u,R). 接下来通过比较所有向量与 u 的距离, 获得满足条件的向量. 枚举的具体过程与 SVP 求解过程类似,
可以视为对枚举树的深度优先搜索: 深度为 n−k 的节点代表 π k+1 (L)∩S 中的格点, 当算法遍历 π k+1 (L)∩S 中每个
点时, 通过以该点为中心遍历一个小球体可得到 π k (L)∩S 中所有格点. 除了基本的枚举算法, Aono 等人还针对圆
柱体剪枝等多种剪枝技术进行量子算法设计, 实现枚举的多方面加速. 以 BDD 的求解为基础, 作者探讨了该量子
算法在 LWE 求解中的应用.
CVP 的特殊求解算法方面, Eldar 等人 [62] 利用系统范式 (systematic normal form) 进行格的平滑分析, 并依此设
计量子算法, 可以在特定参数下有效求解 BDD 问题. Eldar 等人 [63] 更进一步提出一种量子求解算法, 利用量子傅
里叶变换、量子相位估计等手段, 可将最差情况的 BDD 实例归约为随机格上的 BDD, 并提出了一种多项式级的
量子求解算法. Aggarwal 等人 [105] 对 Eldar 等人提出的算法进行了详细讨论, 给出了量子算法与对应经典算法的原
理分析. 在此基础上, Aggarwal 等人将 BDD 的研究成果与格向量采样等技术结合, 提出了新的量子筛法, 以
2 0.8345n 的时间复杂度求解 SVP. 另一种重要的 CVP 求解算法是基于 Voronoi 图的算法 [106] , 主要原理是将空间分