💻 computer science

Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

本文通过利用一种新颖的图耦合分析和详尽的反集中技术，在依赖感知随机预言机和中心二项式抽象的框架下，为 ML-KEM-768 的诚实解封装失败概率建立了一个 $2^{-164.81}$ 的认证上界，从而严谨地证明了该方案启发式失败规模的合理性。

原作者： Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

发布于 2026-09-10✓ Author reviewed ⓘ

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字世界中，安全性往往依赖于那些在单向使用时非常容易，但在没有正确秘密信息的情况下极难逆向求解的数学问题。ML-KEM 是一种后量子密钥建立机制，旨在即使面对未来的量子计算机也能保持安全。与其他基于格的密码系统一样，它存在一个极小的所谓“诚实解封装失败”（honest decapsulation failure）的概率：即使双方都表现正常，双方原则上仍可能得出不同的密钥。估算这种情况发生的频率是一个重要的正确性问题。此前的分析主要依赖于对失败规模的启发式估计，而要获得一个能够保留不同误差项之间相关数学依赖关系的严谨界限，则要困难得多。

Aurélie Duriez 和 Christophe Tommasini 的一项新研究通过在明确的理想化随机函数/中心二项分布（ROM/CBD）抽象模型下，对 ML-KEM-768 进行严谨的数学分析来解决这一问题。这项工作并非模拟，也不试图计算精确的失败率。相反，作者推导出了一个关于诚实解封装失败概率的认证上限，同时保留了不同误差项之间重要的依赖关系。具体而言，该分析追踪了由公共矩阵以及两个密文压缩项所引起的依赖关系，而不是简单地将它们视为相互独立。最终得到的认证上限小于 2 的 164.81 次方的倒数。

这一发现意义重大，因为它在所研究的明确模型内，用一个考虑了依赖关系的认证上限取代了启发式的失败规模估计。该分析并非简单地假设相关的误差是独立的，而是保留了它们之间产生的数学依赖关系。认证界限达到了与早期启发式估计基本相同的规模，但这不应被解释为证明了那些估计就是精确的失败概率。结果是刻意收敛的：在论文研究的明确 ROM/CBD 抽象内，诚实解封装失败的概率被严格限制在一个极小的值之上。论文还明确指出，这并不是一个精确的解封装失败率，也不是关于 FIPS 203 中固定 SHAKE 实例的信息论陈述。

这项工作需要一种不同的处理问题的方法。简化的启发式分析如果将某些误差项视为独立，会变得容易得多，但实际的代数结构创造了严谨分析必须保留的依赖关系。因此，作者开发了一种方法，在计算过程中追踪这些依赖关系，而不是将其丢弃。研究过程还采用了 AI 辅助的方法论，用于探索候选方法、识别关键案例并构建分析结构。这种探索性的 AI 使用与详尽的计算机验证检查、精确或认证算术以及可独立检查的计算相结合，以封闭论证中最困难的部分。因此，最终的数学结论建立在明确、可复现的证据之上，而非 AI 输出本身。

其结果是在所述抽象内的一个严谨且透明的认证正确性界限。研究人员公开了他们的代码、数据和支持性人工制品，以便任何人都可以进行独立验证。这种可复现性在密码学中尤为重要，因为数学主张应当通过独立验证来赢得信任。研究表明，在所考虑的明确 ROM/CBD 抽象内，诚实解封装失败的概率被限制在一个极小的水平。然而，这不应被解释为 ML-KEM-768 的通用安全证书，不应被视为对标准化方案所有安全属性的证明，也不应被视为涵盖每种硬件或软件实现的陈述。

这一成就通过在明确定义的抽象内，从启发式的失败规模估计转向考虑依赖关系的认证上限，推进了对 ML-KEM-768 正确性这一特定方面的严谨理解。它表明，在保留相关误差项之间重要依赖关系的同时，仍然可以建立一个处于启发式规模的界限。数字 164.81 是该上限的认证指数：在所述 ROM/CBD 抽象内，诚实解封装失败概率被限制在 2 的 -164.81 次方之上。因此，这个数字应当被理解为论文所证明的认证界限的一个精确属性，而不是 ML-KEM-768 整体安全性或可靠性的通用衡量标准。

研究人员还仔细解释了他们工作的局限性。他们指出，他们的证明适用于该系统的特定抽象模型，并不一定适用于软件的所有可能实现方式。他们并未声称解决了所有变体加密标准的难题，也没有暗示该系统对所有类型的攻击都是免疫的。他们的重点严格限定在诚实条件下解密过程的正确性上。通过明确阐述他们证明了什么以及没有证明什么，他们确保了研究结果不会被误解。这项研究证明，在这样一个微小的错误可能导致巨大后果的领域，细致入微的分析具有重要意义。它表明，只要有足够的严谨性和正确的工具，即使是最复杂的数学系统也可以被理解和验证。

最后，这篇论文传递了一个精确但范围明确的信息：在所述 ROM/CBD 抽象内，诚实解封装失败的概率被严格限制在 2 的 164.81 次方的倒数之内。这是一个极小的认证上限，但它不是精确的失败率，也不是关于完整的已部署 ML-KEM-768 系统在每种现实世界条件下都能无故障运行的全面证明。其贡献在于，在明确定义的模型内部，用一个考虑了依赖关系、可复现且可独立检查的界限取代了启发式的失败规模估计。它的力量并不在于声称超越该模型的确定性，而在于对“证明了什么”以及“哪些仍在结果范围之外”做出了明确的界定。

技术摘要：面向 ML-KEM-768 的依赖感知型 ROM/CBD 正确性界限

问题陈述
在 FIPS 203 中标准化的 ML-KEM-768 存在非零概率，即诚实生成的密文解密出的消息与封装的消息不同（即解密失败）。虽然 FIPS 203 报告的启发式失败规模约为 $2^{-164.8}$ ，但该数值依赖于简化的模型，这些模型通常假设压缩误差与格噪声之间是独立的。以往的正式分析要么提供的可证明正确性界限显著较弱（例如约为 $2^{-80}$ ），要么将该启发式规模视为一个需要严格证明的开放问题。具体而言，现有的严谨方法通过将实际的联合分布替换为最坏情况下的确定性包络（deterministic envelopes）来处理压缩项之间的依赖关系，从而导致界限变松（例如 $2^{-127}$ ）。核心挑战在于提供一个能够保留由公钥矩阵以及两个压缩项（ $c_u$ 和 $c_v$ ）诱导的代数依赖性的认证上界，同时达到启发式失败规模。

方法论
本文在一个明确的 ROM/CBD 抽象框架下运行：

随机预言机模型 (ROM)： 领域分离（domain-separated）的公钥矩阵生成流被建模为独立的均匀环元素。
中心二项分布 (CBD)： 秘密多项式和噪声多项式被建模为具有 CBD2 系数的独立样本。
精确整数映射： 压缩、解压缩和解码使用 ML-KEM-768 参数集的精确审计整数映射，而非实数近似值。

证明策略避免了假设误差项之间相互独立。相反，它采用了一种**保持依赖性的传输（dependency-preserving transport）**方法：

图耦合参考 (Graph-Coupled Reference)： 作者推导出了由共享矩阵相关量诱导的 $c_u$ 和 $c_v$ 联合残差的精确二元原语。
傅里叶分析： 他们利用部分傅里叶引理（partial-Fourier lemma）来显式管理从谱界限到全变差距离（total variation distance）的跨越。这使得他们能够将“全理想”（full-ideal）参考分布（其中误差是独立的）传输到“正理想”（proper-ideal）实际分布（其中存在依赖关系）中，而不会丢失依赖结构。
分层修正 (Stratified Correction)： 证明过程通过基于瞬时向量 $r$ $r$ 生成的理想中不活跃 CRT 因子的分层来处理偏离全理想的情况。
- 对于 $|T|=1$ 且 $|T|=2$ （一个或两个不活跃因子）的情况，使用了精确的双对偶枚举器（dual enumerators）和有理谱证书（rational spectral certificates）。
- 对于 $|T| \ge 3$ 的情况，作者采用了基于 Construction-A 格的详尽三因子反集中性（anti-concentration）分析，并使用 Fincke–Pohst 枚举法来界定稀有层（rare strata）的概率。
位特定界限： 分析最后得出了 FIPS 解码映射的精确位特定安全区域，随后对 256 个消息系数进行并集界限（union bound）计算。过程中未假设这些系数之间相互独立。

核心贡献

保持依赖性的上界： 本文提供了一个经过认证的 ML-KEM-768 上界，该上界保留了 $c_u$ 与 $c_v$ 之间的代数依赖性，而不是将其替换为独立的舍入噪声或最坏情况包络。
图耦合二元传输： 作者引入了一种通过仿射理想混合进行图耦合二元群代数传输的方法，解决了联合 $c_u/c_v$ 的依赖问题。
经认证的稀有层控制： 通过详尽的三因子反集中性重演（replay）封闭了 $|T| \ge 3$ 分支，为理想结构高度退化的稀有情况提供了认证界限。
精确有理证书： 最终结果是一个通过精确整数比较和有理不等式推导出的简化有理证书，避免了在决策逻辑中使用浮点数近似。

结果
本文在所述 ROM/CBD 抽象下，确立了诚实解密失败（ $K' \neq K$ ）概率的以下上界：
$\Pr[K' \neq K] \le P^* \le 2^{-164.81}$
精确认证指数为 $-\log_2 P^* = 164.810716201343121\dots$ 。

阈值 $164.81 $是精确的但在数值上很紧凑；认证指数仅比它高出约$ \approx 0.0007162$ 位。
$2^{-164.82}$ 未被本证明认证。
该结果是一个上界，而非精确的解密失败率 (DFR)。

意义与声明
作者明确说明了该结果的内涵与局限：

它是什么： 一个在明确的 ROM/CBD 抽象内、保持依赖性的认证上界。它通过严谨地处理启发式模型经常忽略的代数依赖性，弥合了可证明正确性（通常较弱）与启发式估计之间的差距。
它不是什么：
- 它不是关于 FIPS 203 固定 SHAKE 实例化形式的信息论陈述。
- 它不是精确的 DFR。
- 它不是一种新的 IND-CCA 归约，也不是自适应 $\delta$ -正确性（即攻击者在看到公开数据后选择消息）的证明。
- 它并不声称对底层工具（理想、CRT 分层、傅里叶反集中性）拥有优先权，这些都是已有的先验技术。

其意义在于，为 ML-KEM-768 的启发式失败规模提供了第一个严谨的、具备依赖感知能力的证明，证明了即使在保留依赖关系的情况下（只要将界限略微收紧至 $2^{-164.81}$ ），该启发式数值依然成立，而非仅仅是基于独立性假设的结果。

技术摘要：面向 ML-KEM-768 的依赖感知型 ROM/CBD 正确性界限

类似论文