从一开始，解决格上的近似最短向量问题（Lattice Problems）以及带错误学习问题（LWE），都是计算机领域的经典算法难题。在这个问题中，我们需要在给定一个格子时找到最接近原点的向量，或是在带有噪声的学习问题中找到正确的解。这两个问题在密码学和计算机科学领域中都起到了重要的作用。

尤其是在科学界看来，它们远远超出了传统计算机的能力范围。

那么，量子计算机有望能破解Lattice Problems以及LWE吗？

在前段时间，来自清华大学交叉信息研究院陈一镓助理教授，便针对这些问题提出了一种全新的“破解格密码的量子算法”。这个算法基于量子计算的特性，利用量子比特的叠加和纠缠等特性对密码进行解密，可以提高密码破解的效率。这一算法的提出引起了广泛的关注

预印本论文一经发表，便在整个计算机界引起了巨大的轰动。

如著名密码学家N. P. Smart，就在第一时间发了篇博客文章，详细讨论了论文所带来的影响。

文章地址：https://nigelsmart.github.io/LWE.html

具体说，陈教授提出的这种多项式时间复杂度的算法，主要用于求解具有特定多项式模式的函数-噪声比的“带错误学习问题”（LWE）。该算法的思想是利用LWE问题的结构特性，通过多项式拟合来近似解决LWE问题。这种算法在密码学和信息安全领域具有重要的应用价值。

通过结合Regev所提出的从网格问题到LWE的还原，便可以获得多项式时间量子算法，并可以在的近似因子内求解所有n维网格的决策最短向量问题（GapSVP）和最短独立向量问题（SIVP）。

在此之前，还没有已知的多项式甚至亚指数时间量子算法可以在任何多项式近似因子内求解所有网格的GapSVP 或SIVP。

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

为了开发求解LWE的量子算法，作者提出了两种新的技术：

首先，在量子算法的设计中引入具有复杂方差的高斯函数。特别是，利用复高斯函数离散傅里叶变换中的卡斯特波特征。

其次，使用带有复高斯窗口的窗口量子傅里叶变换，从而能够结合时域和频域的信息。

基于此，便可以先将LWE实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为LWE秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组。

但遗憾的是，Hongxun Wu（UC伯克利博二学生）和Thomas Vidick（量子领域专家）发现，算法的第9步实际上存在一个尚不能修复的bug。

也就是说，这个通过多项式模数-噪声比，来求解LWE的多项式时间量子算法，无法成立了。

对此作者表示，希望像复高斯（Complex Gaussian）和窗口QFT（windowed QFT）这样的想法，会在量子计算中找到其他应用，而LWE问题或许会将有别的解决方法。

九大关键步骤

首先进行参数的设置，之后需要运行一个由九个步骤组成的量子子程序，共运行O(n)次。

论文中最关键的，是一个需要调用O(n)次的，由九个步骤组成的量子子程序。

其中，每次调用都会得到一个经典线性方程，其随机系数是中最短的向量（与LWE秘密向量和错误向量相关）。

在调用完O(n)次之后，便可以得到一个全秩线性方程组，并通过高斯消元法计算出LWE秘密和错误项。

步骤 1：在上进行叠加，并应用复高斯窗口

步骤 2：在|φ1上应用

步骤 3：在|φ2上应用复高斯窗口，得到|φ3和z′

步骤 4：在|φ3上应用

步骤 5：将|φ4分割成高阶|h′和低阶|h′′，然后对|h′′进行测量

步骤 6：在|φ5上应用

步骤 7：提取|φ6的中心，得到纯虚高斯状态|φ7

步骤 8：提取并保留|φ8=|φ7

在步骤8中，作者首先进行四次运算（可逆），然后进行部分测量，最后将四次运算反转。也就是说，需要在不折叠或修改|φ7的情况下，学习。

步骤 9：从和|φ8中提取秘密的线性方程

第9步的目标是将|φ8转换为秘密的经典线性方程，并最终得到主Lemma（3.8）的证明。

其中，步骤9使用步骤8中获得的信息，以及插入LWE秘密中的已知项的κ-1坐标。

这里，bug来了：|φ8.f的振幅不满足M2周期性。

或者，另一种解释是：|φ8.f包含p1...pκ向量。经过域扩展后，本应得到p1p2...pκ-p2...pκ向量，但按照|φ8.g的写法，它只包含p1...pκ向量。因此|φ8.g的表达式是错误的。

作者介绍

陈一镭是清华大学交叉信息学院（IIIS）的一名助理教授。

此前，他在波士顿大学获得博士学位，指导老师是Ran Canetti教授和Leonid Reyzin教授。并在上海交通大学获得学士学位。在那里，一个有趣的问题引导他走上了科研之路。

他的研究兴趣是密码学，特别是在伪随机，格密码，数论，和量子计算等方向。

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