AWS的量子算法挑战后量子密码学的基础
科学界因亚马逊网络服务研究员丹尼尔·西蒙的一项新研究而震动。他提出的量子算法，根据初步评估，能够从根本上加速解决一系列数学问题，而这些问题正是现代后量子密码学的基础。核心论点在于，该算法的时间复杂度并非指数增长，而是多项式增长，如果这一结论得到证实，将颠覆当前关于格结构对量子攻击抵抗力的认知。
需要强调的是：该文件中既没有对ML-KEM和ML-DSA等现行标准的实际攻击，也没有对其真实参数的理论破解。西蒙的工作——他以90年代同名算法闻名，该算法是著名肖尔算法的前身——聚焦于一个更抽象的问题，即二面体陪集问题（DCP）。
数学突破的本质
DCP并不直接用于保护钱包或连接，但它是格密码学的基石。早在2000年代初，奥德·雷格夫就证明，有效解决DCP将能够攻击多维格上的某些变体问题。然而，他的方法依赖于一个理想化、不存在的工具来执行另一项复杂的计算操作。西蒙声称找到了一种绕过这一限制的方法，直接在量子计算机上执行所需的变换。
结合更早的研究，该算法可能扩展到最短向量问题（SVP）和学习误差问题（LWE）的变体。简单来说，SVP是在复杂多维格中寻找最短向量，而LWE是从带有故意添加“噪声”的方程系统中恢复秘密。正是基于这些问题的难度，NIST在2024年采用了相关标准：密钥封装机制ML-KEM和数字签名算法ML-DSA。
恐慌为时过早
尽管这条新闻可能引发轰动性标题，但我呼吁保持谨慎。该研究并未展示对ML-KEM的破解或对ML-DSA签名的伪造。此外，LWE是一个完整的问题家族，实际标准使用的是经过特殊结构化的子类。针对某一类LWE的结果不能自动推广到所有密码系统。
预印本中缺少关键信息：运行算法所需逻辑量子比特数量、量子门数量以及纠错量的评估，这些对于在密码学意义上显著的规模上运行是必需的。没有这些数据，谈论实际威胁还为时过早。历史上有过响亮声明化为泡影的例子——比如2024年，研究员伊莱·陈声称找到了LWE的多项式算法，但几天后其证明中发现了致命错误。
我的分析：这项工作是一个重要的智力挑战，它强调我们对量子计算的理解仍处于形成阶段。然而，对行业而言，这更多是加速向混合方案过渡和多样化密码原语的信号，而非恐慌的理由。距离NIST标准的量子破解实际实现，我们可能还有很长的路要走，但忽视这样的理论突破将是极其轻率的。