On Thu, Sep 25, 2025 at 11:41 AM D. J. Bernstein <[email protected]> wrote:
> > “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. > Thanks for the expanded discussion. It seems to me that the relevant question for the purposes of this document is whether the client should do anything in this case other than just report a connection failure and handle it like any other connection failure. -Ekr
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
