Probabilistic modeling of decryption-failure bounds in CRYSTALS-Kyber under the post-quantum threat model
Open Access
- 29 January 2026
- journal article
- Published by IOP Publishing in Machine Learning: Science and Technology
- Vol. 7 (1)
Abstract
We present a probabilistic modeling framework for quantifying decryption-failure probability (DFP) in CRYSTALS-Kyber, the lattice-based key encapsulation mechanism standardized by NIST as ML-KEM. Our method combines exact tail computation of Kyber's centered-binomial noise distribution using FFT-based convolution with principled comparisons to classical concentration inequalities such as Hoeffding and Bernstein. This hybrid analytical-computational approach yields implementation-independent upper bounds on DFP that are exponentially small in the security parameter. Specifically, we compute two-sided tails for aggregated noise variables, translate those into per-ciphertext failure probabilities through a transparent union bound, and determine the minimal reconciliation margins required to ensure DFP ≤ 2 -λ for λ ∈ 128, 192, 256. Across Kyber-like parameter regimes, Bernstein-type inequalities consistently overestimate risk compared to the exact probabilistic tails, which are several orders of magnitude smaller. The resulting gap highlights the conservatism of inequality-based analyses and clarifies the quantitative safety margins inherent to Kyber's design. These findings contribute to the broader effort of modeling reliability in post-quantum cryptographic primitives using probabilistic and computational methodologies.Keywords
This publication has 52 references indexed in Scilit:
- Probability and Moment Inequalities for Additive Functionals of Geometrically Ergodic Markov ChainsJournal of Theoretical Probability, 2024
- The Central Limit Theorem for Markov Processes that are Exponentially Ergodic in the Bounded-Lipschitz NormQualitative Theory of Dynamical Systems, 2023
- Polar coding for Ring-LWE-based public key encryptionCryptography and Communications, 2022
- Hoeffding–Serfling Inequality for U-Statistics Without ReplacementJournal of Theoretical Probability, 2022
- Central limit theorem for linear processes generated by IID random variables under the sub-linear expectationApplied Mathematics-A Journal of Chinese Universities, 2021
- Hoeffding’s inequality for Markov processes via solution of Poisson’s equationFrontiers of Mathematics in China, 2021
- Stable Polynomials and Sums of Dependent Bernoulli Random Variables: Application to Hoeffding InequalitiesBulletin of the Iranian Mathematical Society, 2020
- General Bernstein-Like Inequality for Additive Functionals of Markov ChainsJournal of Theoretical Probability, 2020
- Worst-case to average-case reductions for module latticesDesigns, Codes and Cryptography, 2014
- Secure Integration of Asymmetric and Symmetric Encryption SchemesJournal of Cryptology, 2011