量子算法新突破？Simon对DCP的多项式时间解法引热议，但ML-KEM与ML-DSA暂未受冲击

Simon预印本的核心主张

Simon的论文提出了一种针对DCP的多项式时间量子算法。DCP长期以来被视为连接格密码问题的关键桥梁 。核心主张包括：

• DCP的多项式时间求解器：该算法能在量子计算机上以多项式时间求解DCP，其基础是Regev在2002年提出的将二面体子群问题（Dihedral Subgroup Problem）归约为DCP的结论 。
• 填补20年理论空白：自Regev的归约将DCP与格问题联系起来后，该领域一直存在一个开放性问题（约从2004年起）。如果Simon的主张成立，则将填补这一空白 。
• 新的技术路径：该算法用一种称为“分块-查询”（block-and-query）的新技术替代了先前方法中的关键预言机（oracle），以提取隐藏的子群信息 。
• 声称对格问题的影响：论文称，该算法可以结合Regev 以及Brakerski、Kirshanova、Stehlé和Wen 的归约改进，得到解决格问题的多项式时间量子算法，例如求解最短向量问题（SVP）和带误差学习问题（LWE）的多项式因子近似解 。
• 容忍错误率：论文还声称该算法能够容忍高达1/O(log n)的样本错误率，这使得它能与归约路径结合，有效解决格问题 。

验证现状：“怀疑”与“等待核实”的态度

截至2026年8月7日至8日，密码学界的反应普遍谨慎且充满怀疑 。

• 未经同行评审：该草稿被标记为“初步草稿”，于2026年8月6日发布在IACR ePrint服务器上 。它未经同行评审，也未在任何期刊或会议上发表。
• 早期反应充满怀疑：多位专家分析指出，论文中多个关键性的证明仅以草图形式呈现，且最后的推论部分依赖未发表的私人通信，而非已发表的推导 。一位行业分析师将初步反应描述为“高度怀疑”（heavy skepticism）。
• 无独立验证：自预印本发布以来的几天里，尚未有任何独立的验证或反驳发表 。社区的主流情绪是“事实优先，再谈反应”（facts before reaction）。
• 非实际攻击：各方报道一致强调，这是一个关于DCP的理论性主张，而非对任何标准化密码系统实施的攻击 。

这对ML-KEM和ML-DSA意味着什么

对于正在部署或评估NIST后量子密码标准的组织而言，直接的答案是明确的：没有理由基于此预印本改变既定路线 。

• 暂无直接实际威胁：该预印本没有实现对ML-KEM（FIPS 203）或ML-DSA（FIPS 204）的攻击 。没有任何NIST参数集被攻破 。
• 理论影响是间接的：DCP通过已知的归约与格问题相关联，但这些归约是否能产生针对Module-LWE或Module-SIS（ML-KEM和ML-DSA背后的具体困难假设）的具体攻击，是尚未被证明的更进一步的步骤 。
• 结构性问题，非实际问题：如果该主张被证实，它将强化“量子计算机能高效解决某些格问题”的理论基础。然而，广义的“格问题”范畴远大于NIST标准中使用的具体结构化格假设 。
• 与先前工作的对比：2025年，Bai等人曾提出一个针对DCP限制变体（在2的幂次模数上的外推DCP）的准多项式时间算法 。Simon声称的“完全多项式时间”将是一个更大的飞跃，但尚未得到确认。

专家社区反应：高度怀疑，呼吁谨慎

密码学及后量子安全社区的反应传达了一个明确信息：等待、验证、不要过度反应 。

• 报告称“高度怀疑”：后量子行业的分析师指出，证明过程的粗略性质以及依赖未发表的参考文献是需要仔细审视的主要警示信号 。
• 条件性影响：即使DCP可以在多项式时间内求解，对基于格的PQC的理论影响也是“有条件”的——这取决于具体的归约路径，而不仅仅是DCP可解 。
• 尚未有主要机构表态：NIST、学术实验室及标准机构尚未发布正式声明，鉴于预印本仅发布数日，这一点符合预期 。
• 总体姿态：社区将此事视为一个需要仔细审查的重要主张，但并非改变PQC部署时间表或参数设置的理由 。

总而言之，Daniel Simon的预印本是一项重大的理论主张，如果被证实，可能对格密码的基础产生深远影响。但就目前而言，它只是一个未经证实且存在明显缺陷的预印本，并未改变像ML-KEM和ML-DSA这类NIST标准化后量子算法的实际安全状况。