💻 computer science

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

This paper establishes a certified upper bound of $2^{-164.81}$ for the honest-decapsulation failure probability of ML-KEM-768 within a dependency-aware random-oracle and centered-binomial abstraction, utilizing a novel graph-coupled analysis and exhaustive anti-concentration techniques to rigorously justify the scheme's heuristic failure scale.

Original authors: Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

Published 2026-09-10✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, security often relies on mathematical problems that are easy to use in one direction but extremely difficult to reverse without the right secret information. ML-KEM is a post-quantum key-establishment mechanism designed to remain secure even against future quantum computers. Like other lattice-based cryptographic systems, it has an extremely small probability of what is called an honest decapsulation failure: even when both parties behave correctly, the two sides could in principle derive different keys. Estimating how rarely this can happen is an important correctness question. Previous analyses have largely relied on heuristic estimates of the failure scale, while obtaining a rigorous bound that preserves the relevant mathematical dependencies between the different error terms is substantially more difficult.

A new study by Aurélie Duriez and Christophe Tommasini tackles this problem by developing a rigorous mathematical analysis of ML-KEM-768 within an explicit idealized random-function / centered-binomial, or ROM/CBD, abstraction. The work is not a simulation and does not attempt to calculate the exact failure rate. Instead, the authors derive a certified upper bound on the probability of an honest decapsulation failure while preserving important dependencies between the different error terms. In particular, the analysis keeps track of dependencies induced by the public matrix and by both ciphertext-compression terms rather than simply treating them as independent. The resulting certified upper bound is smaller than one in 2 to the power of 164.81.

This finding is significant because it replaces a heuristic failure-scale estimate, within the explicit model studied, with a dependency-aware certified upper bound. The analysis does not simply assume that the relevant errors are independent; it preserves the mathematical dependencies that arise between them. The certified bound reaches essentially the same scale as earlier heuristic estimates, but this should not be interpreted as proving that those estimates are the exact failure probability. The result is deliberately narrower: within the explicit ROM/CBD abstraction studied in the paper, the probability of an honest decapsulation failure is rigorously bounded above by an extremely small value. The paper also makes clear that this is not an exact decapsulation-failure rate and is not an information-theoretic statement about the fixed SHAKE instantiation of FIPS 203.

The work required a different way of approaching the problem. Simplified heuristic analyses can become much easier if some error terms are treated as independent, but the actual algebraic structure creates dependencies that a rigorous analysis must preserve. The authors therefore developed a method that follows these dependencies through the calculation instead of discarding them. The research process also used an AI-assisted methodology to explore candidate approaches, identify critical cases, and structure the analysis. This exploratory use of AI was combined with exhaustive computer-verified checks, exact or certified arithmetic, and independently checkable computations to close the most difficult parts of the argument. The final mathematical claims therefore rest on explicit, reproducible evidence rather than on AI output itself.

The result is a rigorous and transparent certified correctness bound within the stated abstraction. The researchers made their code, data, and supporting artifacts available so that the computations can be checked independently. This level of reproducibility is particularly important in cryptography, where mathematical claims should be open to independent verification. The study shows that, within the explicit ROM/CBD abstraction considered, the probability of an honest decapsulation failure is bounded at an extremely small level. It should not, however, be interpreted as a general certificate of safety for ML-KEM-768, as a proof of all security properties of the standardized scheme, or as a statement covering every hardware or software implementation.

This result advances the rigorous understanding of one specific aspect of ML-KEM-768 correctness by moving from a heuristic failure-scale estimate to a dependency-aware certified upper bound within a clearly defined abstraction. It shows that a bound at the heuristic scale can still be established while preserving important dependencies between the relevant error terms. The number 164.81 is the certified exponent of this upper bound: within the stated ROM/CBD abstraction, the honest-decapsulation failure probability is bounded above by 2 to the power of -164.81. This number should therefore be understood as a precise property of the certified bound proved in the paper, rather than as a general measure of the safety or security of ML-KEM-768 as a whole.

The researchers also took care to explain the limits of their work. They noted that their proof applies to a specific abstraction of the system, not necessarily to every possible implementation of the software. They did not claim to have solved the problem for all variations of the encryption standard, nor did they suggest that the system is immune to all types of attacks. Their focus was strictly on the correctness of the decryption process under honest conditions. By being clear about what they proved and what they did not, they ensured that their findings are not misinterpreted. The study stands as a testament to the power of careful, detailed analysis in a field where small errors can have huge consequences. It shows that with enough rigor and the right tools, even the most complex mathematical systems can be understood and verified.

In the end, the paper delivers a precise but deliberately scoped result: within the stated ROM/CBD abstraction, the honest-decapsulation failure probability is rigorously bounded above by 2 to the power of -164.81. This is an extremely small certified upper bound, but it is not an exact failure rate and it is not a blanket proof that the complete deployed ML-KEM-768 system works without failure under every real-world condition. The contribution lies in replacing a heuristic failure-scale estimate with a dependency-aware, reproducible, and independently checkable bound inside a clearly defined model. Its strength comes not from claiming certainty beyond that model, but from being explicit about both what has been proved and what remains outside the scope of the result.

Technical Summary: Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768

Problem Statement
ML-KEM-768, standardized in FIPS 203, exhibits a non-zero probability that an honestly generated ciphertext decrypts to a message different from the encapsulated one (a decryption failure). While FIPS 203 reports a heuristic failure scale of approximately $2^{-164.8}$ , this value relies on simplified models that often assume independence between compression errors and lattice noise. Previous formal analyses have either provided provable correctness bounds that are significantly weaker (e.g., around $2^{-80}$ ) or have treated the heuristic scale as an open problem requiring rigorous justification. Specifically, existing rigorous methods often handle the dependency between ciphertext components by replacing the actual joint distribution with worst-case deterministic envelopes, resulting in looser bounds (e.g., $2^{-127}$ ). The core challenge is to provide a certified upper bound that preserves the algebraic dependencies induced by the public matrix and both compression terms ( $c_u$ and $c_v$ ) while reaching the heuristic failure scale.

Methodology
The paper operates within an explicit ROM/CBD abstraction:

Random Oracle Model (ROM): Domain-separated public-matrix generation streams are modeled as independent uniform ring elements.
Centered Binomial Distribution (CBD): Secret and noise polynomials are modeled as independent samples with CBD2 coefficients.
Exact Integer Maps: Compression, decompression, and decoding use the exact audited integer maps of the ML-KEM-768 parameter set, not real-number approximations.

The proof strategy avoids assuming independence between the error terms. Instead, it employs a dependency-preserving transport approach:

Graph-Coupled Reference: The authors derive an exact bivariate primitive for the joint residual of $c_u$ and $c_v$ induced by the shared matrix-dependent quantity.
Fourier Analysis: They utilize a partial-Fourier lemma to explicitly manage the step from spectral bounds to total variation distance. This allows them to transport the "full-ideal" reference distribution (where errors are independent) to the "proper-ideal" actual distribution (where dependencies exist) without losing the dependency structure.
Stratified Correction: The proof handles the deviation from the full-ideal case by stratifying based on the inactive CRT factors of the ideal generated by the ephemeral vector $r$ $r$ .
- For $|T|=1$ and $|T|=2$ (one or two inactive factors), exact dual enumerators and rational spectral certificates are used.
- For $|T| \ge 3$ , the authors employ an exhaustive three-factor anti-concentration analysis using a Construction-A lattice and Fincke–Pohst enumeration to bound the probability of rare strata.
Bit-Specific Bounds: The analysis concludes with exact bit-specific safe regions for the FIPS decoding map, followed by a union bound over the 256 message coefficients. No independence is assumed between these coefficients.

Key Contributions

Dependency-Preserving Upper Bound: The paper provides a certified upper bound for ML-KEM-768 that retains the algebraic dependencies between $c_u$ and $c_v$ , rather than replacing them with independent rounding noise or worst-case envelopes.
Graph-Coupled Bivariate Transport: The authors introduce a method to transport the full-ideal reference through the affine ideal mixture using a graph-coupled bivariate group-algebra transport, resolving the joint $c_u/c_v$ dependence.
Certified Rare-Stratum Control: The $|T| \ge 3$ branch is closed using an exhaustive three-factor anti-concentration replay, providing a certified bound for the rare cases where the ideal structure is highly degenerate.
Exact Rational Certificate: The final result is a reduced rational certificate derived from exact integer comparisons and rational inequalities, avoiding floating-point approximations for the decision logic.

Results
The paper establishes the following upper bound for the probability of honest decapsulation failure ( $K' \neq K$ ) in the stated ROM/CBD abstraction:
$\Pr[K' \neq K] \le P^* \le 2^{-164.81}$
The exact certified exponent is $-\log_2 P^* = 164.810716201343121\dots$ .

The threshold $164.81$ is exact but numerically tight; the certified exponent exceeds it by only $\approx 0.0007162$ bits.
The value $2^{-164.82}$ is not certified by this proof.
The result is an upper bound, not an exact Decryption Failure Rate (DFR).

Significance and Claims
The authors explicitly state what the result is and is not:

What it is: A dependency-preserving certified upper bound within the explicit ROM/CBD abstraction. It bridges the gap between provable correctness (which is often weaker) and heuristic estimates by rigorously accounting for the algebraic dependencies that heuristic models often ignore.
What it is NOT:
- It is not an information-theoretic statement about the fixed SHAKE instantiation of FIPS 203.
- It is not an exact DFR.
- It is not a new IND-CCA reduction or a proof of adaptive $\delta$ -correctness (where an adversary chooses the message after seeing public data).
- It does not claim priority for the underlying tools (ideals, CRT stratification, Fourier anti-concentration), which are established prior art.

The significance lies in providing the first rigorous, dependency-aware justification for the heuristic failure scale of ML-KEM-768 within a well-defined abstraction, demonstrating that the heuristic value is not merely a result of assuming independence but holds even when dependencies are preserved, provided the bound is slightly tightened to $2^{-164.81}$ .

Technical Summary: Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768

More like this