清华大学破解格密码，或颠覆美国PQC布局
清华大学破解格密码，或颠覆美国PQC布局
2024年4月10日，清华大学交叉信息研究院的陈一镭助理教授在eprint平台上发表了一篇具有里程碑意义的论文，提出了一种全新的量子算法，可以破解格密码。这一突破性成果如果通过同行评议验证，不仅将把量子计算推进到一个新的时代，还将对密码学、安全等领域产生深远影响。
格密码学：后量子时代的安全基石
格密码学是后量子密码学领域的重要分支，其安全性基于解决格上数学难题（如最短向量问题SVP和最近向量问题CVP）。这些问题在经典计算机及量子计算机上均难以破解，因此格密码学被视为抵御量子攻击的有力工具。
格密码系统使用称为“格”的几何结构构建，并使用矩阵表示。其中，近似最短向量问题（Approximate Shortest Vector Problems in Lattices，简称Lattice Problems）和带错误学习问题（Learning with Errors，LWE）是格密码学的核心难题。这些问题即便面对量子计算机的挑战，也被认为是难以直接解决的。
美国国家标准与技术研究院（NIST）在后量子密码学标准化项目中，选择了多个基于格密码学的算法，包括Kyber、Dilithium和SPHINCS+。这些算法被认为是目前最有可能抵抗量子计算机攻击的候选方案。
陈一镭的突破：多项式时间量子算法
陈一镭教授的论文展示了多项式时间量子算法，用于求解具有特定多项式模数-噪声比的有误学习问题（LWE）。具体而言，该算法通过以下关键技术创新实现了对LWE问题的突破：
在量子算法设计中引入具有复杂方差的高斯函数，特别是利用了复高斯函数离散傅里叶变换中的卡斯特波特征。
使用带有复高斯窗口的窗口量子傅里叶变换，这使得能够结合时域和频域的信息。
通过这些技术，陈一镭将LWE实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为LWE秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组。
颠覆性影响：重塑后量子密码学布局
这一突破的科学意义是双层的：
这将是自30年前Peter Shor提出大数分解的量子算法以来，最重要的量子算法突破。
这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性影响。目前NIST选择的大多数后量子密码方案都是基于格问题或LWE，陈一镭的工作无疑将使它们的安全性受到质疑。
图灵奖得主、量子计算领域权威、清华交叉信息研究院院长姚期智对此给出了高度评价：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”
未来展望：量子计算的新纪元
目前，这一研究成果仍在同行评议中。考虑到Wiles解决费马大定理和Perelman解决庞佳莱猜想都经过了一年以上的时间验证，预计陈一镭的工作也需要数月时间才能完成验证认可。
如果这一成果最终得到验证，它不仅将改变我们对量子计算能力的认知，还将推动密码学和安全领域进入一个全新的发展阶段。正如NIST的后量子密码学项目负责人Dustin Moody所说：“总体而言，Shor算法几乎可以破解我们目前使用的所有公钥密码体系。”而陈一镭的工作可能进一步加速了这一进程。
这一突破提醒我们，量子计算的发展正在以前所未有的速度推进，同时也为我们提供了重新思考和构建安全体系的机会。无论最终结果如何，陈一镭的工作都将成为量子计算和密码学发展史上的一个重要里程碑。