Page 402 - 《软件学报》2026年第1期
P. 402

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


                 上困难问题求解算法作为评估后量子格密码安全性的手段也日益受到重视                           [12] . 已有的格上困难问题经典求解算
                 法针对最短向量问题 (shortest vector problem, SVP)、错误学习 (learning with errors, LWE) 等问题的求解积累了丰
                 富成果  [13−15] . 但随着量子计算机的快速发展, 量子计算技术直接应用成为可能, 采用量子搜索等加速技术                       [16,17] 的格
                 上困难问题量子求解算法逐渐兴起, 受到国内外研究者广泛关注                     [18−30] . 格上困难问题量子求解算法中最常用的量
                 子加速技术是     Grover 搜索、量子碰撞搜索、量子傅里叶变换等. 这些量子加速方法与格上困难问题求解的基本
                 原理相结合, 发展出一系列量子算法, 如图            1  所示.

                                                         格上困难问题量子求解



                     基于量子 Grover 搜索     基于量子碰撞搜索      基于量子傅里叶变换     基于量子回溯      基于变分量子算法      基于量子线路优化

                  基于量子搜  量子 LWE  量子 NTRU  量子 NTRU  基于碰撞的  量子 LWE  量子 LWE  基于量子回溯  基于变分算法  基于变分算法  量子格基约化
                   索的筛法  组合求解  方案攻击     方案攻击  量子筛法    对偶求解算法  组合求解算法  的枚举算法     的 SVP 求解  的 LWE 求解  算法设计
                  量子可证明
                    筛法   基于量子  基于量子     基于量子          基于 QFT 的        在枚举树上     基于变分  基于变分
                        Grover 搜索的  Grover  碰撞搜索  基于量子  LWE 分布  BKW 算法的  运行量子回溯  量子算法、  量子算法    量子 LLL 算法
                         BKW 算法  搜索的攻击  的密钥恢复  漫步的筛法   判定   秘密向量恢复   加速短向量搜索    量子绝热  的 LWE 问题  对应量子线路
                  量子启发式                 攻击方法                                    算法的枚举  求解
                    筛法
                                            图 1 格上困难问题量子求解算法基本技术

                    2004  年, Regev  等人  [31] 最早对  SVP  的量子求解做了分析, 将其转化为二点问题, 进而归约至量子计算中二面
                 体群隐含子群问题, 证明了其在量子计算中复杂性仍为亚指数级的. 此后, 研究者提出了一系列                             SVP  量子求解算
                 法, 可分类为量子筛法、量子枚举、量子格基约化等. 图                2 给出了格上困难问题量子求解算法主要类型的发展概况.
                    后量子格密码研究领域中, 格上困难问题求解思路主要分为两类: (1) 将问题归约后使用                          SVP  求解算法  [32–40] ,
                 (2) 针对问题的特定结构设计专用算法           [41–47] . 基于这两种求解思路, 可将格上困难问题量子求解算法同样分为基
                 于  SVP  求解的通用算法和针对特定格问题的专用算法.
                    (1) 量子  SVP  求解算法. 大多数格上困难问题都可以归约为             SVP, 进而利用   SVP  求解算法解决, 这也是求解
                 格上困难问题最基本的思想. 量子计算模型下               SVP  求解算法主要包括量子筛法、量子枚举、量子格基约化. 量子
                 筛法方面, 2013  年, Laarhoven  等人  [48] 提出使用  Grover 量子搜索加速筛法中向量组对约减的步骤, 进而对          AKS  筛
                 法、列表筛法等启发式筛法实现了平方级次加速                  [49] . 2016  年, Becker 等人提出了正轴体筛法  [50] 和  LD  筛法  [51] .
                 2019  年, Kirshanova 等人  [52] 研究了量子计算下  k 列表问题的求解方法, 并将其应用于元组筛法, 给出了查询复杂
                 度的分析. Albrecht 等人  [53] 对量子筛法中多种关键组成部分进行了量子实现和复杂度分析, 如高维球的临近向量
                 算法、过滤搜索、向量和的重量计数等. 2021             年, Chailloux  等人  [54] 在量子筛法的基础上进一步扩展, 使用量子漫
                 步替代量子筛法中的       Grover 量子搜索步骤, 并利用局部敏感过滤加速. 2023          年, Bonnetain  等人  [55] 基于量子漫步给
                 出了同时求多组碰撞的算法, 并应用在量子筛法中; Chailloux             等人  [56] 结合量子加速与编码技术加快了元组筛法的
                 运行. 量子枚举方面, Grover 量子搜索在枚举过程中难以适用. 为了构造量子枚举, 主要有两种设计思路. 一种是依
                                                                                               √
                 托经典枚举的搜索树结构, 在枚举过程中应用量子回溯算法, 对                    T  个节点的搜索树, 时间复杂度约为           T , 该方法
                 由  Aono  等人  [57] 提出, 并由  Bai 等人  [58] 给出了复杂度分析. 2023  年, Bindel 等人  [59] 进一步降低了该方法的复杂度
                 上界. 另一种量子枚举方法由         Albrecht 等人  [60] 提出, 主要思路是将  SVP  通过编码转化为哈密顿算符的基态, 并利
                 用变分量子算法求解. 量子格基约化方面, LLL             是最基础、应用最广的约化算法. 2019          年, Tiepelt 等人  [61] 首次将
                 LLL  算法的流程通过量子线路进行实现, 并利用该方法构造了对梅森素数密码系统的攻击.
                    (2) 特殊问题量子求解算法. 主要包括对于            LWE、NTRU、CVP    等特定的格上困难问题的求解算法, 以及带
                 结构的特殊格上困难问题求解算法. 这些特殊问题是多种后量子公钥密码标准的安全性基础, 其量子求解算法具
                 有重要研究价值. LWE      方面, 2018  年, Esser 等人  [41] 基于  c-求和方法提出一种基于组合的    LWE  求解算法, 并利用
                 Grover 量子搜索算法对其主要操作         (向量组合查找) 实现量子加速, 相比经典计算下的时间复杂度达到平方加速.
   397   398   399   400   401   402   403   404   405   406   407