Hacker News Reader

Comment by tptacek | Hacker News Reader

The NSA had nothing to do with designing Kyber.

He didnt say it did, he said "The NSA likely has orders more experience with the area of cryptography Kyber comes from than everyone who worked on Kyber"

He himself (co-)submitted a lattice KEM to the NIST competition.

Yes, and strongly argued against lattice schemes generally. DJB submitted a lattice scheme under the theory that if the advocates of lattice schemes were able to win the argument about the performance properties then there should be a choice of an extremely conservatively designed one.

DJB himself has consistently advocated for Classic McEliece in any application which can accept its performance characteristics (which are excellent except for the ginormous public keys), and spent many bytes trying to convince people that the set of applications that can is wider than they suspect.

His isn't the most conservative lattice construction! This is a hell of a just-so story.

NTRU based schemes are not the most conservative. NTRU is an old design from the 90s, that had some shocking structural attacks against it appear ~2016. These attacks so far are only relevant for moduli q ~ (1/100) n^{2.3...}. This makes them worse than conventional attacks against NTRU-based PKE. But they completely killed roughly half of all NTRU-based fully homomorphic encryption schemes, and are a (major) structural issue with NTRU that RLWE/MLWE does not have.

In other words, Bernstein proposed a NTRU-based scheme under his theory it was the most conservative. The only major attacks on lattice-based schemes since his proposal have been on the hardness assumption his scheme uses. I would personally suggest this means that Bernstein is not an accurate predictor of the security of lattice-based schemes. So far his track record (with this notable example, but also many others) is remarkably bad.

The general C.W. I've heard is that if something happened that made MLKEM look theoretically shaky (pretty unlikely, but whatever), you fall back to something like FrodoKEM, which is plain LWE with no affordance for NTT or anything like it; no structure, no performance.

It really depends on what the precise details of the attack look like.

1. algebraic structure: sure use frodoKEM

2. error rates smaller than those required for worst-case to average-case reductions: idk bump error rates

3. some coding theorist ruins everyone's fun and has linear time decoding for p-ary construction A codes: probably drink a lot idk

fortunately there haven't been any "incremental" attacks in any of these directions, so it is really more an academic discussion.

Also note the primary issue with FrodoKEM isn't performance (though that is definitely worse), but size. My impression from the following

https://blog.cloudflare.com/sizing-up-post-quantum-signature...

https://blog.cloudflare.com/making-protocols-post-quantum/

was that TLS w/ FrodoKEM might have some undesirable performance characteristics, though that isn't directly stated in the articles. Iirc TLS w/ FrodoKEM

> In other words, Bernstein proposed a NTRU-based scheme under his theory it was the most conservative.

This is in fact that what I meant, and should have said: thanks.

Reply on news.ycombinator.com