> > One of the talks at Crypto 2025 last week said that none of the Kyber > > parameters meet their claimed security levels. > Details and specifics, please?
The paper is a recent update of https://eprint.iacr.org/2022/1750: "the security levels for Kyber-512/768/1024 are 3.5/11.9/12.3 bits below the NIST requirements (143/207/272 bits) in the same nearest-neighbor cost model as in the Kyber submission". The numbers should have been reported as ranges: analyzing the costs of known lattice attacks actually involves many uncertainties that together can push the security levels up or down by >10 bits. For the same reason, I agree with a comment "there remains a few bits to be gained by cryptanalysts before the security levels would be convincingly crossed" from a member of the Kyber team in April. But the same analysis fog, together with the attack improvements, means that Kyber could have even _lower_ security levels against the paper's attack than the paper says, never mind further attack improvements. The Kyber team's last security analysis was in 2021 and claimed 151 bits plus or minus various uncertainties. This new paper just a few years later is >10 bits better. This _isn't_ from the originally identified uncertainties being resolved in a way that happened to be unlucky for Kyber. Specifically, the 2021 analysis https://web.archive.org/web/20230310174959/https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf said "Our first point is that, while the core-SVP hardness methodology suggest that the dual attack is slightly cheaper than the primal one, it is in fact significantly more expensive"; the new paper is a much faster dual attack (and avoids the disputes about some earlier dual attacks). Primal attacks have also improved by >10 bits, for example via "hybrid" attacks; the 2021 analysis had portrayed those attacks as merely threatening "very low noise" and not Kyber. Dismissing the advances here because the attack costs haven't reached the demo level yet is the same conceptual mistake as dismissing quantum computation because Shor's algorithm hasn't been demonstrated on any real examples yet. One can, of course, hope for the advances to stop, but this doesn't mean one should be blind to the advances. In any event, Kyber's original security claims are not justifiable today. For the same reason, NIST should withdraw its claims that ML-KEM is as hard to break as AES-128/192/256. ---D. J. Bernstein _______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
