Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale
Researchers certify a dependency-preserving upper bound of 2^-164.81 on honest decapsulation failure for ML-KEM-768 within an explicit ROM/CBD abstraction.
The paper models ML-KEM-768's domain-separated public-matrix streams as independent uniform ring elements and secret polynomials as CBD2 primitives, explicitly not claiming an information-theoretic result about the fixed SHAKE instantiation in FIPS 203. It preserves dependencies from the public matrix and both ciphertext-compression terms, using a graph-coupled reference, a proper-ideal bivariate Fourier transport, and a 256-coordinate union bound. The certified bound is Pr[K' != K] <= 2^-164.81, with the exponent 164.8107162... exceeding the 164.81 threshold by only about 0.0007162 bits; 164.82 is not certified. The bound applies to messages fixed independently of the randomness under honest encryption and decapsulation, and is not an exact DFR, a fixed-SHAKE equivalence, or a new IND-CCA reduction.
- Certified upper bound of 2^-164.81 on honest decapsulation failure for ML-KEM-768.
- Analysis preserves dependencies from the public matrix and both ciphertext-compression terms.
- Bound is numerically tight: exponent exceeds 164.81 by about 0.0007162 bits.
- Result is abstraction-specific, not an exact DFR or fixed-SHAKE equivalence theorem.
- Tags
- decapsulation-failurefips-203formal-analysislattice-cryptographyml-kem-768post-quantum-cryptography
- Vendors
- NIST
- Products
- ML-KEM-768FIPS 203SHAKE
- Organizations
- NIST
From the original article
1 min read at arxiv.orgWe certify an honest-decapsulation failure upper bound for ML-KEM-768 in an explicit random-function/centered-binomial (ROM/CBD) abstraction. Domain-separated public-matrix streams are modeled as independent uniform ring elements and secret/noise polynomials as independent CBD2 primitives; this is not an information-theoretic statement about the fixed SHAKE instantiation of FIPS 203.
By Aurélie Duriez · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.