30 年来最重要的量子算法突破？

在计算机领域，解决格上的近似最短向量问题（Approximate Shortest Vector Problems in Lattices。Lattice Problems）以及与之等价的容错学习问题（Learning with Errors，LWE）是经典的算法难

题，科学界普遍认为它们超出了传统计算机的能力范围。

量子计算机是否有望能破解 Lattice Problems 以及 LWE？虽然这一问题长期以来受到关注，但鲜有实质性进展。

近日，清华大学交叉信息研究院助理教授陈一镭在 eprint 上发布的一篇论文，给出了破解格密码的量子算法，引发了全球计算机领域的震撼。

• 论文地址：https://eprint.iacr.org/2024/555.pdf

• 论文标题：Quantum Algorithms for Lattice Problems

清华大学在今天的官方公告中表示：「陈一镭的工作提出了一个全新的量子算法来解决 LWE 以及与之等价的格问题。这项工作仍在同行评议中。如果被验证为正确，将为这个悬而未决的问题给出肯定

的答复。」

它在科学上的意义将是双层的：第一，这将是自 30 年前 Peter Shor 提出大数分解的量子算法以来，最重要的量子算法突破。

第二，这将对美国 NIST 过去 10 年来选择后量子密码设计的思路产生颠覆性的影响，因为多数选出的后量子密码方案都是基于 Lattice Problems 或 LWE。陈一镭的工作无疑将使他们安全性受到质

疑。

这篇论文提出的算法及分析极为新颖而深奥。回想 Wiles 1994 年解决费马大定理（Fermat's Last Theorem），以及 Perelman 2002 年解决庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上

专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。

对此，图灵奖得主、量子计算领域权威、清华交叉信息研究院院长姚期智给出高度评价：「作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！」

从论文致谢部分的内容来看，为理论计算机领域引入格密码和容错学习问题的纽约大学计算机科学家、2018 年哥德尔奖得主 Oded Regev 本人应该已经看过论文手稿。

那么，这篇论文究竟取得了怎样的突破？

具体而言，这篇论文展示了一种多项式时间量子算法，用于求解具有特定多项式模数 - 噪声比的有误学习问题（LWE）。结合 Regev [J.ACM 2009] 所展示的从格问题到 LWE 的还原，论文得到了多项

式时间量子算法，用于求解所有 n 维网格的决定性最短向量问题（GapSVP）和最短独立向量问题（SIVP），其近似因子为。在此之前，还没有任何多项式甚至亚指数时间的量子算法可以在任何多项

式近似因子内求解所有格的 GapSVP 或 SIVP。

为了开发求解 LWE 的量子算法，这篇论文主要引入了两种新技术：

首先，陈一镭在量子算法的设计中引入了具有复杂方差的高斯函数，特别是利用了复高斯函数离散傅里叶变换中的卡斯特波特征。其次，陈一镭使用带有复高斯窗口的窗口量子傅里叶变换，这使得能够

结合时域和频域的信息。利用这些技术，陈一镭将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组。

求解 LWE 的量子算法

论文第三章主要专注于定理的证明：

• 3.1 节展示了具有几个已知秘密坐标的 LWE 和标准 LWE 一样难；
• 3.2 介绍了将 LWE 转换成具有唯一最短向量的特殊 q-ary 格；
• 3.3 节列出了主要量子算法中使用的参数；
• 3.4 节概述了主要的量子算法；
• 3.5 节详细提供了主要量子算法的九个步骤，但将所有长度超过三页的证明推迟到第 3.6 节；
• 3.6 节提供了第 3.5 节中遗漏的所有详细证明。

具体而言：

论文展示了 LWE 的三种变体，最后一个变体在 Def. 3.4 中正式定义，本文提出的量子算法最终将解决这个问题。 

下面三种缩减都是对现有经典多项式时间缩减的微小修改，从标准 LWE 到它们的变体。

1. 有 k 个无误差坐标的 LWE。

2. 有 k 个选择误差项的 LWE。

3.LWE，秘密遵循误差分布。

将 LWE 转换成具有唯一最短向量的特殊 q-ary 格

现在定义一个 q-ary 格，使得找到这个特殊 q-ary 格的唯一最短向量意味着求解。

设：

参数选择

本小节将介绍更多量子算法中使用的参数。设 D ∈ N + 为缩放参数。

参数是在以下约束下设置的:

量子算法有九个步骤，下面的每个条件通常只在一个或几个步骤中使用：

主要量子算法的详细概述

本节中，作者运行一个由 9 大步骤组成的量子子程序，时间复杂度为 O (n) 次。每次运行量子子程序时都会获得一个经典线性方程，其中随机系数在中的最短向量上（与 LWE 秘密和误差向量相关）。

因此，运行 O (n) 次后将得到一个满秩线性方程组，并通过高斯消元法计算 LWE 秘密项和误差项。

如下为量子子程序中 9 大步骤的高级描述，包括了每个步骤中获得的状态以及经典信息。 

主要量子子程序：9 大步骤详解

步骤 1：在上准备一个叠加，并应用复高斯窗。

步骤 2：在 |φ1⟩上应用。

步骤 3：在 |φ_2⟩上 应用复高斯窗，得到 |φ_3⟩ 和 z′。

步骤 4：在 |φ_3⟩上应用。

步骤 5：将 |φ_4⟩ 划分为了高阶和低阶 |h′⟩ |h′′⟩，然后测量 |h′′⟩。为了推导出 |φ_5⟩的表达式，作者注意到 |φ_4⟩ 可以等效地写为：

步骤 6：在 |φ_5⟩应用。

步骤 7：提取 |φ_6⟩ 的中心，得到纯虚高斯态 |φ_7⟩。

步骤 8：提取 v′_1 mod D^2_p1 并保留 |φ_8⟩ = |φ_7⟩。

在第 8 步中，作者首先执行四次操作，然后进行部分测量，最后将这四次操作反转（将确保这四次操作是可逆的）。目标是提取 v′_1 mod D^2_p1，最终返回到 |φ_7⟩。也就是说，将学习 v′_1 mod D^2_p1 而不折叠或修改 |φ_7⟩。

步骤 9：从 v′_1 mod D^2_p1 和 |φ_8⟩ 中提取秘密上的线性方程。

在第 9 步中，作者的目标是将 |φ_8⟩ 转换为秘密上的经典线性方程，最终给出如下主引理（引理 3.8）的证明。步骤 9 使用步骤 8 中获得的 v′_1 mod D^2_p1 信息，并插入 LWE 秘密中的已知项的 κ-1 坐标。

陈一镭简介

陈一镭是清华大学交叉信息学院助理教授，上海期智研究院 PI。曾任 VISA 研究院研究员。于 2018 年获得波士顿大学计算机博士学位，本科毕业于上海交通大学。主要研究兴趣是密码学，特别是在伪

随机，格密码，数论，和量子计算等方向。

在个人介绍中，陈一镭的研究成果主要包括设计了格问题的量子算法，建立了多线性映射和代码混淆在格问题上安全实现的基础，提出了证明 Fiat-Shamir 假设的方法，以及提出了一个不可逆群的构造。

也就是说，在 2022 年，陈一镭就发表了有关格问题的研究。该研究「Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering」发表于 2022 年欧洲密码大会（Eurocrypt

2022），并收到 Journal of Cryptology 邀稿。

在 2022 年这篇研究中，陈一镭团队和普林斯顿大学的刘启鹏和 Mark Zhandry 提出了一个能解决特殊格问题的多项式时间量子算法。这些特殊格问题是 SIS 和 LWE 的变种。他们虽然并不等价于标准

的格问题，但是已经非常接近于密码学常用的问题。他们的量子算法中使用了一种被称为 “过滤” 的方法，是在量子算法的设计中第一次使用，可能为未来量子算法的设计带来新的思路。

参考：

https://sqz.ac.cn/password-50

文章来自微信公众号“机器之心”，作者：机器之心编辑部