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

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

割, 使得每一部分内的向量之间互相接近. 随着量子机器学习等量子信息技术的发展, 基于 Voronoi 图的量子算法
逐渐受到关注 [107] . 因此, CVP、BDD 的量子 Voronoi 图算法也是未来的重要研究课题.

8 特殊结构格上的量子算法
后量子密码学中, 特殊结构的格具有重要的研究意义. 尽管格问题已成为多种密码方案的理论基础, 然而实际
的密码方案运行过程中, 随机格上加解密操作需要大量计算. 为追求更高效率, 很多基于格的公钥密码方案选择使
用带特殊结构的格作为底层安全性基础. 在此背景下, 针对特定的格结构设计适合的算法成为后量子格密码研究
的关键课题, 其中理想格上 SVP 的求解算法尤其受到研究者关注: 当前格密码方案大量使用环 SIS、环 LWE, 而
这些特殊结构问题的复杂度可归约至最差情况理想格上的 SVP. 本节重点介绍理想格上 SVP 量子求解算法. 一个
理想格的构造如下: 设 m 阶分圆域 K, 度 n = φ(m), 其上整环表示为 R K = [ω m ], 在环上取一个整理想 h ⊂ R K ; 在域
,
K 上通过 Minkowski 嵌入定义典型的 Hermite 向量空间, 即令 ς m = exp(2iπ/m) ⊂ C ψ i : K → C 是由 ω m 至 ς i m 的域
同态, i 与 m 互素. 基于以上定义, 任一理想 h ⊂ R K 均可通过映射转化为一个格结构. 随着越来越多格密码方案采
用特殊结构格, 理想格上的 SVP 求解算法持续吸引研究者的关注, 产生了一系列算法设计与分析成果, 如图 14 所示.

特殊结构格上量子算法

量子算法设计 量子算法分析

主理想格上
密码方案攻击 基于算法 基于量子
经典步骤 计算原理
的求解质 的算法复
主理想格 一般理想格 量分析 杂度分析
上 SVP 求解 上 SVP 求解
图 14 特殊结构格上量子求解算法发展脉络

理想格量子算法设计方面, 理想格上的 SVP 量子求解算法源于主理想格上全同态加密、多线性映射等密码
方案的量子攻击, 其基本原理如下. 对已有的私钥, 选择失真较小的整元素 g ∈ R K , 则对应的公钥为理想 J = (g),
可由一组约化程度较低的格基描述. 攻击方法分为两个阶段: 首先, 利用量子计算求解主理想问题, 即恢复 J 的一
个生成元 h; 随后, 使用 CVP 算法在对数单位格中恢复私钥 g, 此两个步骤的时间复杂度都是多项式级的. Cramer
等人 [108] 总结此类攻击, 针对主理想格提出了 SVP 求解算法: 假定已知主理想的任一生成元, 则算法在主理想格上
√
O( n)
能以多项式级别的时间复杂度得到近似因子为 2 的短向量. 该算法相比随机格上的 SVP 算法, 考虑了主理想
格的特殊性质, 达到明显的加速效果, 具体对比见图 15. 虽然该方法可以成功实现对理想格的攻击, 但其明显短板
是只讨论了主理想, 而实际格密码中常用的环 SIS、环 LWE 等结构的安全性依赖于一般理想上最差情况的 SVP
复杂度. Cramer 等人 [65] 总结了已有的针对主理想格密码方案的攻击, 并扩展至一般的理想格, 提出了最差情况的
√
理想格 SVP 求解方法. 给定分圆域 K 上任意理想 R K , 其量子算法可在多项式时间内求解近似因子 γ = exp(O( n))
的理想格 SVP 问题. 总体而言, 该算法主要步骤包括: (1) 以量子多项式时间求解近似主乘积问题, 从而将一般理
想格上的 SVP 归约至主理想格; (2) 应用已有结果, 求主理想格上的短向量, 并由求解结果恢复理想格上短向量.
√
√
Cramer 等人 [66] 进一步将近似因子从 exp(O( n)) 放宽至 exp(O( m)), 提出了多项式时间内求较短理想格向量的量
子算法.
理想格量子算法分析方面, Ducas 等人 [67] 在启发式假设的基础上定量估计了上述量子算法的近似因子; 通过
理论估计, 20 000 阶以上的分圆域上, 基于理想格性质设计的专用量子算法输出结果优于 BKZ-300. Ducas 等人进
而提出多种启发式的优化技巧, 如利用已知的大量短向量构造 Voronoi 结构, 进一步降低近似因子的具体取值.