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.

This publication has 52 references indexed in Scilit: