Probabilistic modeling of decryption-failure bounds in CRYSTALS-Kyber under the post-quantum threat model

Abstract We present a probabilistic modeling framework for quantifying decryption-failure probability (DFP) in CRYSTALS–Kyber , the lattice-based key encapsulation mechanism standardized by National Institute of Standards and Technology as module-lattice-based key-encapsulation mechanism. 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mrow> <mml:mi>DFP</mml:mi> </mml:mrow> <mml:mtext>⩽</mml:mtext> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>−</mml:mo> <mml:mi>λ</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>λ</mml:mi> <mml:mo>∈</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>128</mml:mn> <mml:mo>,</mml:mo> <mml:mn>192</mml:mn> <mml:mo>,</mml:mo> <mml:mn>256</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> </mml:math> . 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.