[Pqc] Re: A New Theory on Post-quantum Migration

AI writes:
> Kyber's IND-CCA KEM security is proven via a sequence of games to the
> hardness of Module-LWE/Module-SIS in the (quantum) random-oracle
> model. This means: a Kyber break ==> MLWE/MSIS solver.

That's doubly wrong:

    * Theorem 3 in the Kyber documentation considers MLWE
      _distinguishers_. Those can be faster than MLWE search attacks,
      i.e., faster than MLWE solvers.

    * The theorem is "loose", so it doesn't rule out the possibility of
      a Kyber/ML-KEM break being even faster than an MLWE distinguisher.
      The theorem puts a limit on the gap, but the limit is gigantic.

Doing the work of quantifying the theorem arrives at questions such as
"What's the fastest MLWE distinguisher that has success probability at
least 2^-200 against the Kyber-768 parameters?". Good luck trying to
find cryptanalysis papers answering that question.

> worst-case --> average-case

No, those theorems are yet another source of looseness (piled on top of
the other sources). See generally https://eprint.iacr.org/2016/360.

> parameter choices blend these reductions with concrete attack cost
> models (BKZ/sieving, etc.).

That's outright false for Kyber. Kyber's parameter choices ignore the
theorem looseness; they're based purely on studying high-probability
attacks. (Also, those attacks have been superseded by faster attacks;
see, e.g., last month's https://eprint.iacr.org/2025/1910.)

For comparison, https://eprint.iacr.org/2023/947 chose parameters to
combine lattice theorems with a not-yet-disproven model of the cost of
lattice attacks. What that paper showed was that 2^128 QROM IND-CCA2
security for a new proposal followed from such a model of the cost of
attacking a worst-case lattice problem, approximate SIVP. The proposal
is basically FrodoKEM-79510 with a 37-bit modulus.

---D. J. Bernstein


===== NOTICES =====

This document may not be modified, and derivative works of it may not be
created, and it may not be published except as an Internet-Draft. (That
sentence is the official language from IETF's "Legend Instructions" for
the situation that "the Contributor does not wish to allow modifications
nor to allow publication as an RFC". I'm fine with redistribution of
copies of this document; the issue is with modification.)

-- 
Pqc mailing list -- [email protected]
To unsubscribe send an email to [email protected]