[kibwen]

This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.

[tptacek]

There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.

[mswphd]

With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.

In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.

So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey

https://cims.nyu.edu/~regev/papers/lwesurvey.pdf

[tptacek]

I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem.

I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc; things were wackier in the early aughts too) just as there is a diversity of implementation strategies for lattice KEMs.

The notion I'm hostile to is the one that poses lattices as moon math.

[mswphd]

Yes I know. That was what my initial paragraph was about.

And yes, our formal understanding of LWE is much better than the original NTRU problem. NTRU itself

1. admits non-trivial attacks if the ciphertext modulus is too large, as well as

2. had a signature algorithm (NTRU-sign) that was completely broken.

Lattice-based signatures were actually a relatively thorny thing to develop. The first non-broken lattice-based signature was proposed in 2009 iirc. I think this was after Gentry developed fully homomorphic encryption (though his initial scheme is now broken as well). Even in modern treatments, it's a fair statement to say that constructing a secure lattice-based signature is of similar complexity to constructing a secure fully homomorphic encryption scheme (although there are some relatively-simple ones these days).

You can make stronger statements about our understanding of LWE though. I would say that it is relatively uncontentious to state that LWE and elliptic-curve DLOG are the two problems we understand the best theoretically in public-key cryptography, and it is not particularly close. The only remote contenders would be

1. finite-field DH, though arguably our understanding of this is still not great (are CDH and DDH equivalent? well sort of, but the details become quite messy).

2. RSA. There are still many basic questions about it that are wide-open, namely is it equivalent to factoring? There are other questions that are unknown as well, for example how hard it is to attack. "Everyone knows" that you just use GNFS, with L[1/3, c] complexity. But other index calculus attacks were improved to L[1/4, c] complexity in the 2010s. Can those attacks extend to factoring? Things get even worse when you consider the veritable zoo of attacks on RSA when you get a small detail wrong (Coppersmith-style attacks in the presence of some leaked key bits, improved attacks depending on what particular RSA exponents you've chosen, etc).

I think you could even go farther and say that we understand LWE better than elliptic curve DLOG. This would of course be contentious, but is meant to communicate just how good of a (theoretical) understanding we have of the LWE problem.

Of course, the main point in EC DLOG's favor is that, when correctly parameterized (which is a thorny point itself, but mostly fine these days), there are the generic group lower bounds (2^n time, poly space), and attacks have never beaten them. While for LWE attacks have always been of the form (exp time, exp space) (or 2^{n\log n} time, poly space), but the exponent in the "exp"'s doesn't have as clean of a conjectured lower bound, and has been reduced some over time.

[tptacek]

Sure, two things:

(1) Cards on the table I don't pay attention to PQ signatures.

(2) I'm mostly just saying that LWE schemes and 90s NTRU are pretty closely related, more closely related than RSA and FFDH were (but less closely related than a binary Koblitz curve is to 25519).

[mswphd]

They are, my point is that this only became obvious later. The initial NTRU preprint frames it as a scheme based on modular polynomial arithmetic, rather than anything related to lattices. At the end of section 4 they even explicitly describe it as a “ring based cryptosystem” (contrasted with “group based cryptosystems”). As you say, now we would call it a lattice-based cryptosystem (over an algebraically structured lattice).

https://www.ntru.org/f/hps96.pdf