#问答时间#
问：格密码的量子算法今天看到新闻（http://t.cn/A6TCMhdI）如下。近日清华大学交叉信息研究院陈一镭助理教授在eprint上发布了重要论文，给出了一个破解格密码的量子算法。论文标题为Quantum Algorithms for Lattice Problems。 链接：http://t.cn/A6T9IBql。

解决格上的近似最短向量问题（Approximate Shortest Vector Problems in Lattices, 简称Lattice Problems）以及与之等价的带错误学习问题（Learning with Errors,简称LWE）是经典的算法难题，科学界普遍认为它们超出了传统计算机的能力范围。那么，量子计算机有望能破解Lattice Problems以及LWE吗？这个问题一直受到广大关注，但鲜有显著进展。陈一镭的工作提出了一个全新的量子算法来解决LWE以及与之等价的格问题。这项工作仍在同行评议中。

如果被验证为正确，将为这个悬而未决的问题给出肯定的答复。它在科学上的意义将是双层的: 第一，这将是自30年前Peter Shor提出大数分解的量子算法以来，最重要的量子算法突破。第二，这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响，因为多数选出的后量子密码方案都是基于Lattice Problems 或LWE。 陈一镭的工作无疑将使他们安全性受到质疑。 这篇文章（http://t.cn/A6Tlrzl0）更详细的总结了更多算法细节如下。

论文展示了一种多项式时间量子算法，用于求解具有特定多项式模数 - 噪声比的有误学习问题（LWE）。结合 Regev [J.ACM 2009] 所展示的从格问题到 LWE 的还原，论文得到了多项式时间量子算法，用于求解所有 n 维网格的决定性最短向量问题（GapSVP）和最短独立向量问题（SIVP），其近似因子为图片。在此之前，还没有任何多项式甚至亚指数时间的量子算法可以在任何多项式近似因子内求解所有格的 GapSVP 或 SIVP。 为了开发求解 LWE 的量子算法，这篇论文主要引入了两种新技术：首先，陈一镭在量子算法的设计中引入了具有复杂方差的高斯函数，特别是利用了复高斯函数离散傅里叶变换中的卡斯特波特征。其次，陈一镭使用带有复高斯窗口的窗口量子傅里叶变换，这使得能够结合时域和频域的信息。利用这些技术，陈一镭将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组。 是否可以说，如果这篇论文通过同行评议验证为正确，会增加了量子计算在遥远的未来可以破解更多加密算法的可能性，但仍然可以确定量子计算在2030年以前不会有任何实际用途。

@王孟源dudu 答：這是很純的應用數學問題，需要行内的專家花費幾年來確定論證是否正確。不過正因爲它討論的是很初步的原則性議題，即便正確，也不代表30年内能有實際應用，正如針對RSA的Shor's Algorithm是1994年發明，30年後剛有一點苗頭，RSA就被簡單替換掉了；更別提Shor's Algorithm是一個完整的解密方案，這篇論文卻只是一個弱弱的思路建議罷了。此外這篇論文所針對的Lattice Encryption也只是Post Quantum Encryption的選項之一，要替換的話早有現成的其他密碼可用。
2024-04-13