4 ms·

Lattice cryptography is not in fact fairly nascent. It's new to you, which is not the same thing. That's why I raised the point about 25519's vintage: you're th

by tptacek 2mo ago

Lattice cryptography is not in fact fairly nascent. It's new to you, which is not the same thing. That's why I raised the point about 25519's vintage: you're thinking about 25519 in today's context (which, ironically, has taken some of the shine off of it!) and not in the context of 2005, when it was introduced. When TextSecure adopted Curve25519, Bernstein didn't complain and say "you should be doing hybrid triple-FFDH/triple-Curve25519". This is especially useful to know given that mainstream elliptic curve and lattice cryptography are of roughly the same vintage. As commercial propositions, things actually getting fitted into protocols, both date back to the mid-1990s. For a time, there was a question as to whether NTRU might succeed RSA rather than elliptic curves! Nobody's arguing from "both sides". You're continuing to misconstrue what's happening. It's also not true that "nobody is proposing lattice-only". The whole point of this story is that pure MLKEM is a proposal on the table. It has to be, because there are environments that need to use it (that, or not do PQC at all). None of them are environments you're ever likely to work in, and hybrids remain the default and the only PQC KEM standards-track RFC for PQC in development. I'm going to keep pointing out that a lot of the reason you don't have this context is that Bernstein doesn't want you to. He expects you to take his word for it.

vlovich123 2mo ago
We seem to be reading different history books. The first elliptic curve paper (1985) precedes the first lattice paper (1996) by 11 years. 2005 is when LWE was published which provided the first theoretical foundation to construct lattice encryption correctly with guaranteed mathematical guarantees. NTRU was plagued with a lot of problems precisely because it lacked this foundation and no one seriously used it or adopted it. 2005 is also when the NSA publicly formalized ECC in its suite B of algorithms and saw widespread standardization across NIST, IEEE, and ANSI. It was fairly well understood how to construct ECC correctly too precisely because it had already been widely studied for like 20 years. So in 2005 you’ve got ECC relying on well known mathematical problems with a solidly understood foundation having been studied for 20 years vs lattice which basically had its first description of how to do lattice. Now maybe if something like Snowden had happened prior, adoption of ECC might have looked differently and the same people would have advocated different things. Hard to tell. But trotting out NTRU like it had any chance in hell with competing with ECC or claiming that ECC and lattice are “basically the same time frame” is just a fundamental disagreement on the facts that isn’t supported by the timelines of each. But sure if lattice truly is resistant to classical attacks you generally don’t lose much from a cryptographic security perspective except that my understanding is it’s still worse on all metrics (compute and size) than ECC. And AFAIK lattice is much more complicated than ECC (both in theory and implementation) - where there’s more complexity there’s more room for mistakes (as the NIST PQ standardization effort demonstrated - very nearly adopted algorithms later proved insecure). ECC by comparison isn’t actually much worse than RSA on that front which again is why no one was proposing dual schemes in 2005,
- tptacek 2mo ago
  Regev in 2005 was hugely important, but '90s NTRU remains unbroken, and Atjai was 1996. The Suite B thing undercuts your argument! You've managed to establish 25519's publication the same year as Suite B. Again: Bernstein didn't ask people to run 25519/MODP hybrids. I think the bigger thing is that a lot of us are older than we realize, and 2005 was a very long time ago --- over 20 years. This is like the distance between Nevermind and Houses of the Holy. Finally: I'm not letting anybody, including Bernstein, get away with allusions to SIKE as a way of impeaching lattice cryptography. Supersingular isogeny cryptography was moon math, and everybody agreed at the time. It has zero relation to lattice problems. It has zero relation to anything! (Ironically, if it did relate to cryptography in use today, it'd be to elliptic curves).
  - vlovich123 2mo ago
    My point is not about a specific algorithm or application. I’m talking about the family elliptic curve vs lattice. Bernstein isn’t asking people to run hybrids because the mathematics is simple and well understood. Also Curve25519 is just a specific set of constants for ECDH. The underlying algorithm was already designed and well understood. The main advancement was selecting the constants carefully to be free of side channel attacks and to be fast. If you can’t see how that’s a very different situation I really don’t know how to help you understand the concern.
    - tptacek 2mo ago
      You know who wouldn't agree that Curve25519 is "just a specific set of constants for ECDH"? The guy who wrote SafeCurves. Also: you've lapsed into talking down all lattices, which leaves you in the position of explaining why Bernstein submitted/sponsored sntrup.
      - vlovich123 2mo ago
        All I’m saying is that lattices are newer and more complex. Bernstein is proposing a lattice scheme AND saying it should be hybrid. ALSO. The proposal is to replace cyclotomics with Gallois field precisely because they are better understood and easier to construct correctly. > The NTRU Prime project recommends switching from "cyclotomics" to "large Galois groups" to reduce the attack surface in lattice-based cryptography. After this recommendation was published, Gentry's original (STOC 2009) fully homomorphic encryption system was shown to be broken in quantum polynomial time for cyclotomics.

by tptacek 2mo ago

vlovich123 2mo ago

We seem to be reading different history books. The first elliptic curve paper (1985) precedes the first lattice paper (1996) by 11 years. 2005 is when LWE was published which provided the first theoretical foundation to construct lattice encryption correctly with guaranteed mathematical guarantees. NTRU was plagued with a lot of problems precisely because it lacked this foundation and no one seriously used it or adopted it. 2005 is also when the NSA publicly formalized ECC in its suite B of algorithms and saw widespread standardization across NIST, IEEE, and ANSI. It was fairly well understood how to construct ECC correctly too precisely because it had already been widely studied for like 20 years. So in 2005 you’ve got ECC relying on well known mathematical problems with a solidly understood foundation having been studied for 20 years vs lattice which basically had its first description of how to do lattice. Now maybe if something like Snowden had happened prior, adoption of ECC might have looked differently and the same people would have advocated different things. Hard to tell. But trotting out NTRU like it had any chance in hell with competing with ECC or claiming that ECC and lattice are “basically the same time frame” is just a fundamental disagreement on the facts that isn’t supported by the timelines of each. But sure if lattice truly is resistant to classical attacks you generally don’t lose much from a cryptographic security perspective except that my understanding is it’s still worse on all metrics (compute and size) than ECC. And AFAIK lattice is much more complicated than ECC (both in theory and implementation) - where there’s more complexity there’s more room for mistakes (as the NIST PQ standardization effort demonstrated - very nearly adopted algorithms later proved insecure). ECC by comparison isn’t actually much worse than RSA on that front which again is why no one was proposing dual schemes in 2005,

tptacek 2mo ago
Regev in 2005 was hugely important, but '90s NTRU remains unbroken, and Atjai was 1996. The Suite B thing undercuts your argument! You've managed to establish 25519's publication the same year as Suite B. Again: Bernstein didn't ask people to run 25519/MODP hybrids. I think the bigger thing is that a lot of us are older than we realize, and 2005 was a very long time ago --- over 20 years. This is like the distance between Nevermind and Houses of the Holy. Finally: I'm not letting anybody, including Bernstein, get away with allusions to SIKE as a way of impeaching lattice cryptography. Supersingular isogeny cryptography was moon math, and everybody agreed at the time. It has zero relation to lattice problems. It has zero relation to anything! (Ironically, if it did relate to cryptography in use today, it'd be to elliptic curves).
- vlovich123 2mo ago
  My point is not about a specific algorithm or application. I’m talking about the family elliptic curve vs lattice. Bernstein isn’t asking people to run hybrids because the mathematics is simple and well understood. Also Curve25519 is just a specific set of constants for ECDH. The underlying algorithm was already designed and well understood. The main advancement was selecting the constants carefully to be free of side channel attacks and to be fast. If you can’t see how that’s a very different situation I really don’t know how to help you understand the concern.
  - tptacek 2mo ago
    You know who wouldn't agree that Curve25519 is "just a specific set of constants for ECDH"? The guy who wrote SafeCurves. Also: you've lapsed into talking down all lattices, which leaves you in the position of explaining why Bernstein submitted/sponsored sntrup.
    - vlovich123 2mo ago
      All I’m saying is that lattices are newer and more complex. Bernstein is proposing a lattice scheme AND saying it should be hybrid. ALSO. The proposal is to replace cyclotomics with Gallois field precisely because they are better understood and easier to construct correctly. > The NTRU Prime project recommends switching from "cyclotomics" to "large Galois groups" to reduce the attack surface in lattice-based cryptography. After this recommendation was published, Gentry's original (STOC 2009) fully homomorphic encryption system was shown to be broken in quantum polynomial time for cyclotomics.