OpenAI 数学证明论文刷新 CVP 硬度下限

OpenAI 于 8 月发布了一份题为「Ten Advances in Mathematics」的论文，公开了 10 项由其模型完成的数学证明工作。其中最引人注目的一项，是关于格上最近向量问题（Closest Vector Problem, CVP）近似难度的全新硬度结果。该结果将 CVP 的 NP 难度边界推进到固定多项式近似因子 n^(1/400)，打破了自 1998 年以来二十多年未能改进的局面。

核心结果：CVP 硬度推进到固定多项式近似

CVP 是格密码学的核心问题之一：在给定格与目标点的情况下，找到距离目标点最近的格点。其精确版本早在 1980 年代就被证明是 NP 难的；1990 年代的研究进一步表明，即便允许任意常数因子甚至 n^(1/log log n) 这种「接近多项式」的近似，CVP 仍然保持 NP 难度。

这一结论在此后二十多年间几乎未被撼动，所采用的证明工具是经典的 PCP（概率可检验证明）机制。而 OpenAI 的新证明显示，CVP 在固定多项式近似因子 n^(1/400) 下仍然是 NP 难问题。由于 n^(1/400) 是「固定」的多项式，这一结果在概念上比此前任何一个「可改进」的近似因子都更具结构性意义。

专家进一步简化：近似因子优化至 n^(1/28)

密码学家 Chris Peikert（密歇根大学）在与播客 Security Cryptography Whatever 的对谈中提到，他并未对证明方法本身做任何改动，仅通过「更精细的簿记（bookkeeping）」就将近似因子从 n^(1/400) 优化到 n^(1/28)。这一现象说明原证明结构具有较大冗余空间，也为后续进一步收紧近似因子留下了可能。

Peikert 还指出，n^(1/400) 中的具体数字并非证明本身的固有障碍，更多是来自参数选取过程中的保守估计。AI 工具能够快速发现并指出这一点，本身也展示了 AI 辅助数学研究中「审阅与优化」这一环节的价值。

同期的其他重要进展

在与本期播客相关的同一时间窗口内，格密码与编码密码领域还出现了两项值得关注的事件：

• 针对二面体陪集问题（Dihedral Coset Problem, DCP）出现了声称的多项式时间量子攻击，一度引发社区紧张；后续由 eprint 2026/1693 等工作指出该攻击并不成立。
• 对 NIST 后量子标准化方案 Classic McEliece 出现了新的区分器攻击。考虑到编码密码学历史上多次因「看似无害的区分器」最终演变为实质性结构破解，这一进展被社区视为需要认真对待的信号。

影响与展望

CVP 硬度下界的提升对理论密码学有直接价值：格基加密、LWE/LWR 等后量子方案的最小安全假设长期基于 CVP 等格问题的近似难度，新结果为这些方案的安全性论证提供了更细粒度的支撑。不过，n^(1/28) 距离实用近似因子（如 γ ≈ n 量级）仍有相当距离，短期内不会改变现有 NIST 后量子标准的部署节奏。

更长远看，OpenAI 的这次尝试展示了通用大模型在「形式化数学证明」这一传统上由人类专家主导的领域中所能发挥的作用。从发现命题、构造候选证明，到被专家进一步压缩参数，AI 与人类研究者的协作模式正在逐步成型。