后量子安全领域因亚马逊网络服务(AWS)研究员丹尼尔·西蒙提交的一篇新科学论文而震动。在这篇新预印本中,他描述了一种量子算法,据称能够以多项式复杂度解决构成现代后量子标准基础的關鍵数学问题——即其运行时间随问题规模呈幂次增长,而非此前认为的指数增长。
如果这一结果被证实,可能会从根本上改变我们对格基密码学抗量子计算能力的认知。然而,必须强调:该文档并未包含对现行标准(如ML-KEM密钥封装机制或ML-DSA数字签名)的实际攻击。这只是一个尚待验证的理论突破。
算法核心及其与格的关联
西蒙以其1990年代的同名算法闻名,该算法是著名舒尔算法的前身。在新工作中,他聚焦于所谓的二面体陪集问题(DCP)。简而言之,量子计算机接收一组关联状态,需要揭示它们之间的隐藏值。DCP本身并不直接用于加密,但在2000年代初,数学家奥代德·雷格夫证明,高效求解DCP将能够攻击多维格上的特定问题变体,包括最短向量问题(SVP)和学习误差问题(LWE)。
雷格夫方法的主要限制在于需要一个理想化的工具来解决另一个复杂问题。西蒙声称,他通过在量子计算机上直接执行必要的变换,绕过了这一障碍。这可能为加速求解结构化LWE变体开辟道路,而2024年采用的NIST标准正是基于这些变体构建的。
恐慌为时过早:背后隐藏的细节
尽管标题引人注目,西蒙的工作并未展示对ML-KEM的破解或ML-DSA签名的伪造。该研究者并未攻击具体的密码学参数,其算法也未包含实现所需的逻辑量子比特数、量子门或纠错操作评估。此外,LWE是一个庞大的问题家族,某一类的结果不会自动迁移到业界使用的所有结构化变体上。
科学界已有先例,关于格的多项式量子算法的重大声明未能通过验证。例如,2024年,研究者陈一磊声称取得类似突破,但几天后其证明被发现存在致命错误,他随后撤回了结论。目前,对西蒙的工作尚无独立共识,这是不应过早下结论的主要标志。
我的分析:这篇预印本对行业是一个重要信号,但并非恐慌的理由。它凸显了我们当前理论安全模型的脆弱性。即使西蒙的算法被证明正确,距离实际威胁仍有数十年之遥。然而,密码学界应加速向混合方案过渡,并推动后量子算法的多样化,避免将所有安全性押注在单一的数学基础上。