> âThe failure rate for ML-KEM is
> sufficiently low that it is highly unlikely that any implementation will
> ever encounter it in practice.â
That's not known.
It's important to distinguish two different situations here. Situation 1
is _legitimately generated ciphertexts_. For that situation, Table 1 of
https://web.archive.org/web/20250907044602/https://eprint.iacr.org/2025/1562.pdf
reports proofs that the failure rate is <=2^-80, <=2^-95 for dimensions
768, 1024. Also, the failure rate is _conjectured_ to be 2^-138.8,
2^-164.8, and 2^-174.8 for dimensions 512, 768, 1024 respectively. If
this conjecture is correct then legitimate users would have to be
amazingly unlucky to generate a failing ciphertext.
Situation 2 is _ciphertexts generated by attackers_. The reason this is
different is that attackers can spend tons of computation searching for
ciphertexts that are enc outputs but more likely to fail than average
enc outputs are. As an example of how it's not obvious what the best
tradeoffs are here, page 23 of the original Kyber documentation
https://web.archive.org/web/20190214071008/https://pq-crystals.org/kyber/data/kyber-specification.pdf
claimed that a particular approach was "probably" the "best strategy";
that turned out to _not_ be the best attack. The paper
https://web.archive.org/web/20250708141344/https://eprint.iacr.org/2021/193.pdf
gives you an idea of how complicated it can be to optimize attacks using
some of the available structure.
---D. J. Bernstein
_______________________________________________
TLS mailing list -- [email protected]
To unsubscribe send an email to [email protected]
