Friday, April 17, 2026 10:30 am
-
11:30 am
EDT (GMT -04:00)
Abstract: Decryption errors play a crucial role in the security of KEMs based on
Fujisaki-Okamoto because the concrete security guarantees provided by
this transformation directly depend on the probability of such an event
being bounded by a small real number. In this paper we present an
approach to formally verify the claims of statistical probabilistic
bounds for incorrect decryption in lattice-based KEM constructions. Our
main motivating example is the PKE encryption scheme underlying ML-KEM.
We formalize the statistical event that is used in the literature to
heuristically approximate ML-KEM decryption errors and confirm that the
upper bounds given in the literature for this event are correct. We
consider FrodoKEM as an additional example, to demonstrate the wider
applicability of the approach and the verification of a correctness
bound without heuristic approximations. We also discuss other
(non-approximate) approaches to bounding the probability of ML-KEM
decryption.
|