近日清华大学交叉信息研究院陈一镭助理教授在eprint上发布了重要论文，给出了一个破解格密码的量子算法。论文标题为Quantum Algorithms for Lattice Problems。 链接：https://eprint.iacr.org/2024/555。

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

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

这篇论文提出的算法及分析极为新颖而深奥。回想Wiles 1994年解决费马大定理（Fermat's Last Theorem），以及Perelman 2002年解决庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。

清华交叉信息研究院院长姚期智说：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”