We invited Mark Schultz-Wu on the podcast to talk about the history of lattice cryptography. When lattices are explained in plain english, they are actually quite simple! I don’t think any of us have ever seen Deirdre so happy. If you’re watching the video version, there’s a section that’s 6.1 minutes long with no cuts and consists just of Deirdre vigorously agreeing with what Mark is saying while smiling. What a time to be alive.
We are hosting another happy hour in Vegas between Black Hat and DEF CON! It’s sponsored by Teleport! Thank you to Teleport, and dear readers, you should go check them out.
Links:
- Mark’s IETF Post
- NTRU
- The original lattices are hard paper
- The original LWE for cryptography paper
- Entropic LWE
- Dilithium round 3 submission
- Recent attacks on Classic McEliece
- Lectures on post-quantum cryptography from Alfred Menezes (an originator of elliptic curve cryptography)
- Falcon
- Regev
- Tightness in Proofs
This rough transcript has not been edited and may have errors.
Deirdre: Okay, uh, Teleport. Teleport ad read. Uh, SCWPod is sponsored by Teleport.
David: You should probably introduce us first still.
Deirdre: Wait, oh, oh, we’re doing the ad read during the podcast?
Mark: Yes, it’s going right in.
David: We’re just gonna start the podcast and then we’re gonna talk about Teleport, who’s sponsoring our live event. Well, our, our happy hour ad. I’m just gonna talk about it now. We’re doing a happy hour again at at Vegas in the liminal space between Black Hat and DEF CON, like we have done every year for the past 3 years. And it is once again, like last year, sponsored by Teleport. And if you don’t know what Teleport is, you probably don’t have SSH. But we’re very happy that they’re sponsoring and we can attest that Thomas is a Teleport user.
Thomas: We use Teleport everywhere at Fly. We love Teleport very much. It is a very, very— if you’re a SOC 2, it is a very, very good way to get a lot of business processes Um, kind of all tucked under kind of a recorded SSH dealy. Um, Teleport is great. Use Teleport for everything.
David: And on that note, I’d like to say this is Security Cryptography Whatever, and my name is David.
Deirdre: I’m Deirdre.
David: Thomas.
Mark: And today we’re talking about lattice cryptography.
David: We’re talking about lattice cryptography. On this very professional podcast with our special guest, Mark Schultz.
Mark: Mark, how are you?
Thomas: Hi.
Mark: Yeah, I’m Mark.
Deirdre: Thanks for being here. Um, yeah, this is like Lattices Redux because one of our very first episodes we talked to Chris Piker about lattices, which was great. He also, uh, tried to show us a bunch of slides. And so we ended up talking through, uh, what our audio-only listeners we’re supposed to be seeing with like a depiction of dots on a field with vectors like that. This is another chance to lattices and try to understand all the stuff that is the area of lattices and post-quantum cryptography, especially using lattices. And you were posting on the internet recently some very, very useful history of, history of where we started with lattice cryptography, the where we started, what got broken, and how we got to things like Kyber, Dilithium, and some other fancier things you’ve done research on. So we would just have you basically talk through what you began posting elsewhere, which is like the history of over 30, maybe 40 years of lattice cryptography.
Mark: So it’s worth clarifying upfront, I am a lattice cryptographer. I, uh, what was this? I think I graduated 2024. I worked with Daniele Miciancio. I was working on fully homomorphic, although my— so I do have some background in lattice-based chemistries, but my publications, with the exception of like one which was talking about those lattice-based, uh, uh, it’s called public key encryption at least, um, was, uh, more on the fully homomorphic encryption side.
Deirdre: Yeah. Uh, and that’s the— that’s some of the fancier stuff that especially if you’re trying to do a post-quantum solution to anything that’s like slightly fancier than public key encryption or signatures, uh, sometimes you may be tempted to reach for the fully homomorphic solution because it seems to solve your problems, but it might do it, uh, computationally costly or largely.
Mark: Um, well, computation and, uh, bandwidth.
Deirdre: Yep.
Mark: So in general, the, uh, the fancier the lattice things get, the bigger you have to increase one of the parameters, the kind of the modulus, and then you also you also have to increase the dimension as well. So kind of, you can think about like 2 parameters that like counteract with each other and keep getting bigger and bigger, and then everything gets big. And then that’s how you can get like, you get FHE papers that talk about 20 gigabyte keys and it’s like, yeah, it’s like fine. It’s not the biggest keys, it’s not the smallest keys. You know, if you’re optimizing for size, maybe you get down to 3 gigs or whatever, but it’s very far from the public key thing.
Deirdre: Gosh. And I want to get back to that when we kind of reach— we kind of start at the simple beginnings, then we get over there, because then we can talk about like why some of these instances of lattice problems, like they feel a little bit more riskier in terms of we think these things when we apply them to these spaces are okay. But then occasionally a paper will show up and be like, oh, anything with parameters that are slightly this far apart, which is bigger than what they are for, for dilithium and kyber basically, or anything more complicated than that that are FHE-like, get scary. Anyway, so Thomas, I mean, I have a specific thing here, right?
Thomas: Which is like, as always, I’m just trying to reinforce things I say on Hacker News, but like a claim I make kind of regularly, which I shouldn’t be making, is that I don’t know what I’m talking about. Is that kind of lattice cryptography and elliptic curve cryptography are of, they’re not literally, I think, I think they’re not literally comparable vintage, but like they were both live ideas in the 1990s, right? I like to say, I like to say that there’s an alternate universe where lattices win over curves.
Mark: So it depends on for what particular applications. The Andrew cryptosystems, both of them, um, were introduced in the mid-‘90s, right? And the Andrew cryptosystems that we see in, in, you know, these days, they’re very similar to what was around in the ’90s. Like, I don’t want to say exactly the same, but at least for entropy, I should say entropy encryption, it’s— there’s a lot of similarities there. Entropy signatures from the ’90s got completely broken. Lattice-based signatures had a very rough going until, like, the first secure lattice-based signature was in 2008, which is rather late. The way I like to describe how late it is is that fully homomorphic encryption was in 2009. So we didn’t get signatures after fully homomorphic encryption, but it was remarkably close, which is kind of wild to think about. You know, you would think FHE is a much harder problem. Lattice-based signatures, they’re very, they’re very well understood at this point, but it took a lot longer to get there because of some additional complexities that show up with lattices for signatures in particular.
Thomas: So like, because of post-quantum cryptography, there’s like, there’s an attitude that lattice cryptography is like, you know, moon math, like whiz-bang stuff, right? And like, one of my things is just kind of pushing back on that notion that like we don’t have a good understanding of what lattice cryptography is. Another thing I like to point out is the gap in time between like in True and LWE or in True and like the, like New Hope or something like that.
David: Right.
Thomas: And like, and like the P-curves in Curve25519, right? Like everyone’s familiar.
Mark: Yeah. New Hope is a great example here. New Hope was in Chrome a decade ago. It was in experimental releases of Chrome. You had to opt in. This was a decade ago. The scheme has had no substantial cryptanalysis in the last decade, no substantial improvements to cryptanalysis in the last decade. When I say that, it’s like a decade, it’s rounding up a little bit. I think the most recent substantial improvement to lattice-based attacks, which was in 2018, when I say substantial improvement here, it’s worth mentioning lattice-based attacks usually separate into 2 components. There’s one which is phrasing the problem as a lattice, and then there’s the other which is solving the lattice problem. When I say this substantial improvements thing here, I mean the second part, the solving lattice problem. There have been some iterations on the improving the phrasing things as a lattice problem. If you’re familiar with the MatSol attack, this is kind of in this first category. One difficult thing with lattice-based cryptography, which I was actually struggling with a bit today, I was asking some people and getting not that great of responses, is that it’s really kind of a socially defined field in a certain sense. What do you mean? You might— yeah, so you might say, okay, lattice-based cryptography, what does that mean? Well, a very easy answer would be, it’s cryptography based on lattices. Unfortunately, this isn’t true at all.
Deirdre: Yeah.
Mark: Um, so as an example, the NTRU paper, the first NTRU, uh, preprint, uh, the term lattice appears in it never. Any cryptographer these days would call NTRU a lattice-based scheme. If you publish a paper on NTRU, it would get put in the lattices track, and it was described as a ring-based cryptosystem.
Deirdre: Oh, I mean, okay, I get that, I get that.
Mark: Yeah.
Thomas: So it like reduces to lattices or like can be—
Mark: it does reduce to lattices, but this is also not a satisfying way to define what lattice-based schemes are. I mean, one reason for that is like elliptic curve-based schemes don’t reduce to elliptic curves, they reduce to Pollard-Rho on a generic group, right? So maybe you call them group-based crypto, or you call them like Pollard-Rho crypto. I don’t know, like it’s— we don’t tend to define problems based on what they reduce to. Um, I mean, for factoring you like sort of do, but also like You can break RSA without breaking factoring by breaking modular, what’s called modular polynomial roots.
Deirdre: Yeah.
Mark: Like that does not actually, you do not need to break factoring to break RSA. Right. So it’s like a, the naming is kind of all over the place.
Deirdre: Yeah.
Mark: In general, lattice-based schemes do get broken by lattice-based attacks.
David: Cool.
Mark: And that’s, I’m pretty sure that’s how the naming for NTRU kind of got decided.
Deirdre: I see.
Mark: It was first ring-based and then there was a lattice attack on it and now it’s lattice-based. Um, but if we’re going based off of schemes that are based by, uh, broken by lattice-based attack, the first one was actually in 1978 with the, there was knapsack-based cryptosystems that Shamir famously broke. Um, and so maybe these knapsack cryptosystems are lattice-based. I would personally argue they are. Uh, my advisor had some papers in the early 2000s on knapsack-based cryptosystems. He’s a lattice-based cryptographer. So there’s a sense in which like lattice-based cryptography is the cryptography that lattice-based cryptographers do. And often involves in kind of reducing problems to solving computational problems on lattices, but—
Thomas: Like other than Intru, check me on this, right? Other than Intru, the schemes that we’re talking about when we think about lattice cryptography are like remarkably similar, right? Like they’re all based on the same, based on the LWE problem.
Mark: Well, yes and no. So the popular ones these days are, I’d say that there’s 2 big counterexamples to this, or maybe 3. So as an example, one thing that you might say is lattices are the only way we can get FHE. This is like sort of true if you define lattices in the right way. In particular, there’s this problem called the approximate greatest common divisor problem that was popular in the early 2010s. It kind of looks more like a number theoretic problem, like something closer to RSA, but it also kind of looks like a lattice problem if you do lattices a lot, and we can get fully homomorphic encryption from this. And Anton Zhu also has this cryptosystem he called the Mersenne prime cryptosystem. I think it was somewhere around 2015. And that also kind of looks like a lattice-based cryptosystem. And also it doesn’t, you know, it’s, it’s not LWE, it’s not NTRU, it’s its own thing. There’s also more recently, there’s these lattice isometry problem type cryptosystems, which it has lattice in the name. So maybe it’s lattice-based, but also the first part of any paper on these is always, here’s how we rewrite our things in terms of quadratic forms. And now we’re gonna do everything in terms of quadratic forms, which mathematically quadratic forms and lattices are kind of equivalent, you know, so it’s, it’s still kind of lattice-based, but kind of computationally quadratic forms end up being nicer for most crypto systems. That all being said, the predominant lattice assumptions are almost always the learning with errors problem, or an algebraically structured variant of it, or a variant with rounding, so like learning with rounding, this type of thing, or the entry problem. There are even more esoteric things than what I’ve just mentioned. In fact, like, uh, when we’re talking about, you know, kind of lattice-based cryptography, these are kind of the boring assumptions.
Deirdre: Yes.
Mark: Uh, one of my favorite things is that there’s this line of lattice-based papers which say we want to do insane stuff, we want to be crazy, and we want to be fast to make a lattice-based PRF.
Deirdre: Oh yeah.
Mark: And I think they’re within a constant factor of AES when you have AES-NI hardware assumptions.
Deirdre: Really?
Mark: Using only AVX-2. Yeah, I can’t remember the precise constant factor. It might be something big like 5 or whatever, but like you can get very fast PRFs based off of very weird lattice assumptions. These are the Spring and Leap PRFs. Okay. I don’t think anyone uses them for anything, but like they use assumptions that are much farther from kind of the boring standard lattice assumptions.
Deirdre: To cover that for our listeners, so We touched on a little bit of NTRU originating in the ’90s. So that’s the end. So let us, let us describe specifically the NTRU assumptions that those things that are consistent with what was introduced in the ’90s reduced to in terms of the security definition construction reduction and not the social construction of like, well, if I can break it using a lattice attack, then why?
Mark: Yeah, but like the NTRU, the problem underlying NTRU, I’ve heard people call it as the small decisional a polynomial ratio problem. Okay. Essentially, you have 2 polynomials, both are drawn from some small distribution, say some, like, you know, centered, some Gaussian-type distribution, discrete Gaussian, who knows. One of them you need to make sure is invertible, usually invertible mod some other prime than the prime you’re normally working with, but it’s invertible. And then you take the numerator one, the non-invertible one, and then the invertible one, invert the invertible one, multiply them together, and it looks uniformly random. That’s roughly the assumption underlying NTRU. And there’s some parameters to tweak, you know, which distributions you use. I mentioned that one might be invertible mod a different prime, what different prime you choose, but that’s kind of NTRU. And what I mentioned here doesn’t really involve lattices at all. You can reduce it to a lattice problem and attack it that way. But the kind of the standard NTRU problem, it’s about inverting polynomials and multiplying them together. Okay.
Deirdre: And then around 2005, Regev introduced, I think, did he literally call it just LWE, like the cryptosystem, or—
Mark: Learning with Errors. So, so it’s the learning with errors problem. And it actually is a very interesting history itself as well, which is like there’s this question you might ask, which is that LWE, it’s our kind of leading candidate for a post-quantum assumption. You might wonder why is that the case? And the best answer is unfortunately the most boring answer. People, very smart people have tried to break it and, you know, have failed. But LWE in particular has a very funny story in that the first person to introduce it was one of the very smart people who tried to break it and failed. So LWE originates, and Regev, he has this 2009 survey, I think, that includes this on the LWE problem that I think includes this point. But Regev was a quantum algorithms person and he was trying to create quantum algorithms for certain worst-case lattice problems. So, like the shortest vector problem.
Deirdre: I didn’t even realize that. That’s neat. That’s very cool. Yeah.
Mark: Well, so some of his— he’s kind of more recently switched over into computational biology. But some of his more recent cryptographic work was actually a faster, I think he, it was a faster factoring algorithm. So some optimizations to Shor’s stuff. Yeah. So he’s been a quantum algorithms guy for 20 years, right? Probably longer than 20 years. But so he was initially looking at these worst-case problems on lattices saying, I wanna try to find quantum algorithms for them. And he was almost able to get it to work if he knew how to solve this one problem quantumly. So if he could solve this one particular problem quantumly, he could, fully solved, you know, these quantum— sorry, these worst-case lattice problems, which were of independent interest at the time. The one problem he couldn’t solve was LWE. So he said, okay, well, instead of saying I get this algorithm for SVP, also I get a reduction from solving this very particular problem that I don’t know how to solve quantumly to— sorry, I get a reduction from SVP quantumly to solving LWE. And that’s what the paper ended up being. But LWE really came from a quantum algorithms guy not being able to solve a different problem. And that was like the isolated subset he didn’t know how to do.
Deirdre: Cool.
Mark: And it’s stood up since then. So like, I guess it’s a decent way to find a problem.
David: Yeah.
Deirdre: And now we have like a whole lineage of problems and like kind of, you know, narrow definitions of problems that all kind of nest down and reduce to different forms or slightly different variations on LWE. And like, yeah. And, um, and I think some of that, I mean, like, you have, like, a learning with errors, like, problem or game or whatever, um, that reduced to SVP, which is the shortest vector problem. Or, you know, you’ve got gap SVP, like, you’ve got, like, you know.
Mark: Yeah, well, so it’s always gap SVP. This is something that’s important to get right, um, because so SVP is an NP-hard problem, right?
David: Yeah.
Mark: So if I said that SVP reduced, uh, LWE— sorry, if I said that SVP reduces to solving LWE in the average case, that could imply that LWE is NP-hard to solve. This is not true, and it’s actually not thought to be true. Yeah. So when you mentioned gap SVP, roughly— so how it works is SVP is this problem. You have this high-dimensional kind of point cloud. It’s this structured point cloud. It’s a lattice. And you’re wondering which part of the structured point cloud is the closest part to 0. In low dimensions, it’s easy. You just do it by, like, I don’t know, looking at the thing. In high dimensions, well, high dimensions, things, you know, from recursive dimensionality, you might expect it to be much harder, and it is. So do we have any intuition as to why that’s hard?
David: Like, I get that, like, you sit down and like it turns out no one’s come up with a good answer for it, but like it just seems like—
Mark: so for SVP, right, like SVP itself, no gap, it’s just NP-hard. So it’s, you know, what’s the intuition for why it’s hard? It’s an NP-hard problem. You know, why is any NP-hard problem hard? I don’t know, they all could be easy, but if any one of them was easy, all of them would be, and we think at least some of them are hard. Right? So there is a more satisfying reason for that, for these lattice problems in particular. So these lattice problems, or lattices in general, they actually show up kind of in useful scenarios somewhere. So in particular, so coding theory wants to look at kind of high-density kind of arrangements of points that are noise tolerant, right? For standard coding theory, this is often noise tolerant in what people call the Hamming metric or pseudometric, where, you know, you get kind of bit flip errors, this type of things, you know, kind of a particular coordinate is either totally fine or totally corrupted. Another error model you could imagine, kind of instead of this digital error model, you could imagine an analog one where you might have a little bit of noise in each coordinate. This is more accurate for kind of radio communications, this type of stuff. So in this analog noise model, you might say I still want to be able to code things to get this dense point cloud so I can get efficient, say, radio communications, but I want to be able to efficiently decode things too. So in this way, kind of problems like SVP, more properly the closest vector problem, kind of have this kind of direct application. And this was actually one of the reasons that at least some of the initial computational study of lattices was occurring, was to kind of, for these kind of radio communications purposes.
Deirdre: Yeah, I could see that.
Mark: Especially since random lattices, for a suitable definition of random, are known to have very good coding theoretic properties. It’s kind of like how random linear codes, they’re kind of near optimal. Random lattices, for many definitions of lattices, are near optimal for these coding-theoretic properties. So if you could efficiently decode a random lattice, then you could get a very efficient analog communication system. This is, for fairly certain parameters, this is roughly what the LWE problem is, is kind of efficiently decoding a certain random lattice, which likely has near optimal parameters for these coding-theoretic purposes. So none of this is a satisfying reason to say why it’s hard. You know, it’s sort of close to a problem that’s NP-hard, but it’s in a kind of this parameter regime where that problem is no longer NP-hard. The problem’s in Arthur Merlin, I think. So if it was NP-hard, you would get some polynomial hierarchy collapse, one of those things that people make it— yeah, kind of, you know, cryptography still isn’t from NP-hard problems in this setting. But then also you have this other community where if they could solve these computational problems on lattices on this average case setting, or, you know, in the worst-case setting, so, uh, then they could get these better constructions, and they haven’t been able to either.
Deirdre: So, um, and we— one of the things that I sometimes hear referenced, and then, uh, if I talk to like a lattice cryptographer, they give me like a, eh, is that we have a, uh, we have like a reduction to worst-case hardness of like gap-SBP for a lot of these LWE systems. Which is like not necessarily a complexity result that we have for some of our other cryptographic constructions that we deploy in the real world.
Mark: So the answer I have to this is, which is that— so famously, we do have this reduction. This was what Regge’s 2005 paper for. It was initially a quantum reduction. It was de-quantum. It was made classical, I think, in 2009.
David: Okay.
Mark: And maybe in more generality, like since then, kind of in the more efficient settings that we tend to use lattices, there have been more and more of these reductions. The issue with these reductions is they’re what are generally called non— there’s 2 big issues with them, actually. So one is that if I wanted to use one of these reductions to build a crypto system, I would need to do 2 things. One is I would need to say, okay, now my hard problem is no longer LWE, it’s GAP-SVP in the worst case. So that’s interesting, but I would now need to figure out what worst-case instances of GAP-SVP look like.
Deirdre: Okay.
Mark: I don’t think that’s really known. So you might be able to do something. You could say like, hey, to figure out how hard gap SVP is in the worst case, I’ll sample a bunch of stuff on average and see how it is in the average case. Like, that’s a fine strategy, but then you’re not using the worst case part of it.
Deirdre: Yeah. Okay.
Mark: All right. The other bigger issue is that the reduction is highly non-tight. Oh, okay. All right. So I don’t know if people have worked out the parameters or I’ve seen a number of papers of people trying to work out the parameters, but there was a lot of debate over which papers did it right. There might have been some errors or whatever. I’ve seen estimates, I think, as high as maybe 30,000 or 60,000 lattice dimension to get appreciable security. So it’s like a—
Deirdre: and we’re nowhere, we’re nowhere using that for, for things like Kyber or Dilithium or— No.
Mark: So Kyber and Dilithium are dimension— so Kyber’s dimension’s like 512 to 1024.
Deirdre: Yeah.
Mark: The, the 60,000 dimension does actually show up sometimes in fully homomorphic encryption, but that’s more Uh, people, even then, they try to get away from that if they can. It’s more like if you can’t optimize certain parameters, you kind of have to have things that big. Yeah.
Deirdre: Okay.
Mark: Um, but the trend there is trying to get them smaller as well.
David: Okay.
Deirdre: So basically we have a thing that could be a nice, like, security, like, lower bound, except we don’t know how to use it to actually give us real-world security parameters that are actually useful, that are of any relation to that mathematical lower bound.
Mark: It’s these 2 things. It’s one, it’s this non-tightness that you’re mentioning. But then the other is that it’s not at all clear to me, or I think to other people, that it’s easier to worst-case cryptanalyze GAP-SVP than it is to average-case cryptanalyze LWE. Because at some point you need somebody to say, I have a computer, you know, I have these algorithms, I tried running them, it took a while, and this is my estimate how much longer it would take for bigger parameters, right? This kind of explicit work trying to extract concrete parameters from these kind of abstract algorithms.
David: Okay.
Mark: And if someone could write down, this is what the worst-case gap SVP instance looks like, and this is how long it takes to solve, then we would have something very interesting. But— and then also if everything was tight, I should say. But that work is also like a— I don’t know if anybody’s looked into it. It seems unclear how to characterize the worst-case gap SVP instances that you’d be reducing from.
David: Got it.
Deirdre: Okay. So in the ’90s, we had our— well, we’ve had our very early, uh, you know, social, uh, instances of lattice cryptography, uh, before the ’90s. We’ve got NTRU, which is still kind of floating around in some form since the ’90s. We get the introduction of LWE, uh, in the mid-aughts, uh, and since then we’ve gotten these other flavors of LWE. Uh, including ring LWE, module LWE, and we’ve seen these unstructured lattices. Uh, one of the crypto systems that uses that is FrodoChem.
Mark: Um, that’s just plain LWE. So that’s the initial version.
Deirdre: Okay. All right. I, for, for some reason I didn’t, I didn’t clock that. I don’t know. Uh, I’ve—
Mark: yeah. So there, there are, so, so yeah. So essentially what happens is any LWE instance can roughly be phrased as the following. You have this integer matrix, you have a secret, and you multiply them together and you add some error.
Thomas: Yes.
Mark: Uh, it’s worth mentioning this error should also be kept secret, so you might think of it as kind of a, kind of a static secret and an ephemeral secret.
Deirdre: Yeah.
Mark: But that’s like the rough shape of it. All the algebraic structure is saying is that this integer matrix— well, matrices take n squared parameters, and that can be a big number. So can we shrink that somehow?
David: Yes.
Mark: You could say, hey, instead of being this n squared matrix thing, I want this to be a matrix that is determined by one of its rows, and then maybe kind of some kind of simple transformation you apply to that row. I might want it to be some sort of topless matrix, some cyclic matrix, these types of things. The algebraic structure, it’s all a way of saying that this matrix, instead of being this fully dense one, it’s going to be this one with some interior structure. As an example for RLWE, RLWE is usually done over a negacyclic— sorry, a cyclotomic ring of power 2. This matrix ends up being what’s called negacyclic. So you have one diagonal and, sorry, you have the vector in a column, and then each time you move it over, you kind of cyclically permute it.
David: Yeah.
Mark: Except when you go off one end, you introduce a minus sign.
Deirdre: Yep.
Mark: So there is this very concrete way to describe it. The downside is that the very concrete way to describe it kind of can hide some security concerns.
David: Yes.
Mark: I said you introduce a minus sign. That sounds like extra work. Why do that? Why just avoid introducing a minus sign? Everything breaks. So that might sound like a very small reason, like, like issue you can make that would make everything break. In kind of the fancier math thing, it ends up making a lot more sense. Roughly, you have a polynomial, and if you don’t introduce this minus sign, the polynomial has this degree 1 factor, and you can kind of stunt everything down to this degree 1 factor to get a 1-dimensional instance that’s very easy to break. So the minus sign—
David: yeah.
Thomas: For people who like aren’t in their happy place when they hear the term cyclotomic field, we’re starting with like original Coke Zero LWE with what’s now called FrodoChem, right?
Deirdre: Yeah.
Thomas: And then we’re going to structured lattices where like instead of what, like a uniform random lattice or whatever, we have, you know, structure inside of the— that, that matrix, right? Why did we do cyclotomics there?
Mark: So why we do cyclotomics there, um, so it’s a, it’s a good question. You could do other forms of structure. In fact, there was this NIST submission, maybe it was called Titanium, that roughly, like, there’s this thing that was called middle product LWE. It’s its own thing. It’s like, there’s more esoteric assumptions, but it essentially said that, like, we get hardness if any of these very large set of structures is fine. So in some senses, maybe it was more conservative, but it’s also, I don’t remember all the downsides of titanium. It’s at least a lot— the middle product stuff’s a lot harder to work with. But why do we use cyclotomics there? Roughly speaking, the initial thing that was introduced was these cyclic lattices. It’s kind of the most obvious thing to do. They had antecedents and— sorry, they had precedence in coding theory. My advisor actually, I think in 2001, he— not for LWE, but for a different problem, the short integer solution problem— he said we can kind of have this cyclic structure, we can get benefits from it. But then there were these papers that said essentially that the cyclic structure means that when you view things in terms of polynomials, you get this degree 1 factor and everything can break. So you have to split off that degree 1 factor and then you get these cyclotomics. Like, it kind of— what cyclotomics are is you take the polynomial x to the n minus 1, which, uh, and then you kind of factor it and you keep the highest degree piece, very roughly. So this x to the n minus 1, very roughly, is kind of the generator of this cyclic transformation. So you start with kind of the easiest thing possible, and then you kind of keep the biggest component of it that’s secure.
Deirdre: And the primary motivation is to take a secure crypto system but make the things that you’re shuttling around on the wire smaller while keeping— while reducing to the same problem.
Mark: Well, so it’s not exactly reducing the same problem. So the idea is that now you only have to pass around one row or column of this matrix. So you get a big size win. But now it is going to be like you’re working over this structured family of instances. Yeah. So there are these concerns. Is this structure useful for attackers? Yeah. It’s plausibly true.
David: Yeah.
Mark: Um, and so RLWE, um, so R-CIS, so it’s, uh, kind of the short integer, uh, solution, uh, version of this was introduced in 2001. RLWE, I think, was roughly 2011. The structure has finally helped attackers this February, maybe. Oh, I think they got a times 4 speedup, and it seems kind of limited to that. So it is— there now finally appears to be a very small gain from the structure, but it has taken a while to materialize. It is worth mentioning, for kind of adjacent lattice problems, the structure can help. So I mentioned you have this matrix and you have a single column and you kind of apply this transformation. You can think about like having this one structured block in it. Kyber does something different. Roughly, it has smaller structured blocks, say 256 by 256 structured blocks, and then it builds the block matrix out of that.
Deirdre: Right.
Mark: This is module LWE.
David: Yep.
Mark: The reason why we often prefer module LWE versus ring LWE, and I say often because this is only true in public key cryptography, in fully homomorphic encryption, everyone uses RLWE. But the reason for public key cryptography, why we do that, is that in 2016, there were some improved quantum attacks against kind of these single block instances, not of ring learning with errors. So the attacks, I think to this day, don’t really say anything for the deployed schemes.
Thomas: Wait, wait, wait, wait, wait, wait, wait, wait, wait, wait, wait, wait.
Deirdre: Yeah.
Thomas: Modular LWE is just LWE with block matrices?
Mark: Roughly.
Thomas: Yeah.
Mark: So it’s module here. Module.
Thomas: Module. Module.
David: Module.
Mark: Sorry.
Thomas: Yeah, yeah, yeah.
David: Yes.
Mark: Yeah. But it’s roughly just you have block matrices and they all share the same structure.
Thomas: So this is this thing where you look up, you look up like modules in Wikipedia and you get—
Mark: Yeah, no, it’s impossible.
Deirdre: Right.
Thomas: Like the actual thing that’s going on here is it’s just block matrices.
Mark: It’s block matrices. Yeah. So it’s block matrices and then it’s instead of fully materializing that, you only ever materialize like the single rows you need. And then you need to have an efficient way to multiply these block matrices by a vector. And that’s where like NTT stuff can show up.
Deirdre: Yeah.
Mark: You know, so it’s a lot of it can be easier in terms of polymath, but it’s block matrices.
Thomas: This was, this was my understanding, which is now like devastated by the last 15 minutes that you two have been talking, right? My understanding before, because I’m an idiot, was that all of the complexity in these systems, all the structure that was being introduced was about something like NTT, was just about like speeding up the multiplication.
Mark: Well, so that also shows up. So it’s not independent because if I just have this dense matrix and I have a vector and I want to multiply them, that’s N squared time, right?
Thomas: Yeah.
Mark: But if I have a structured matrix here and then I will have— if it’s structured in the right way, say it’s an NTT matrix, and then I have a vector here, now I can do something N log N. Yeah. Right?
Thomas: Yeah.
Mark: So roughly speaking, It kind of does both in that we get the compactness because you only need the single row or column. And then also we get this kind of NTT-friendly form.
Thomas: Yeah.
Mark: So we can also get some computation speedups.
Deirdre: Yeah.
Thomas: Okay. So like module LWE has become, for reasons, very salient in like discussions about risk in lattice systems. But yeah, I interrupted you to say, you know, for fuck’s sake about modules and block matrices, right as you were going to say, we now prefer block matrices, or we now prefer modular LWE. I would like to hear more about the thing you were originally going to say.
David: Yeah, yeah.
Mark: So, so what happened is in 2016 there were quantum attacks, I think, against ideal SVP. Yeah, so I mentioned before that SVP is what reduces— worst-case SVP reduces to LWE. So you might think, oh, these quantum attacks against SVP, that’s concerning for LWE. Well, not really, because the reduction goes the wrong way. So if you want to solve LWE, you have to reduce to actually what’s called a rank 2 instance, kind of a block structure with like a 4 squares instead of 1, right? You have to reduce to a rank 2 instance of ideal SVP. And the quantum attacks don’t help in that setting. So in 2016, these quantum attacks in a very, in a relevant but adjacent context showed up. People were like, hey, it’s not that much worse to just use this block structure. And then we’re kind of farther away from the issue. And things have been fine since then, but also for, RLWE-based schemes, things have been fine as well. So as I mentioned, fully homomorphic encryption still uses RLWE everywhere, uses RLWE with insanely more speculative parameter sets. Like there, when I mentioned there was this times 4 speedup from the algebraic structure that appeared recently, I think you get much bigger ones in FHE.
David: Yeah.
Mark: I think that there was maybe a 15-bit speedup. I don’t remember, I’d have to check again, but that’s because FHE people do much, much more speculative things, uh, kind of, uh, to try to get things to be, uh, more efficient.
Deirdre: Yeah. And this, this kind of leads into, this is like the, there’s the boring, the boring crypto stuff, which is literally like the primitives that are basically public key encryption that you, you know, twiddle with an FO transform and turn into, uh, something that looks like key exchange, but it’s not, it’s a KEM. Uh, and then your regular schmegular, you know, signatures to give you like unforgeability or whatever you want to do. Um, but things that get more complicated than that, um, have to go into these settings that have, uh, a little bit, uh, more exotic assumptions if you want to do—
Mark: well, yeah, so I would actually say lattice-based signatures do tend to be a little bit harder than fully homomorphic encryption to get right. Oh, which again is a very funny sentence.
Deirdre: Tell me why, because I would never even have like that, that notion wouldn’t have even entered my head.
Mark: So there’s roughly 2 families of lattice-based signatures. One of them I’m more familiar with. Roughly what they do is they say, okay, so lattices looks a little bit like Diffie-Hellman. If you think of it as AS plus E, if you just ignore the error AS, it’s like, I don’t know, it’s like a one-sided group action. It’s like Diffie-Hellman, right? So you can do Diffie-Hellman type things. In fact, Kyber and things like this, they can be thought of as a Diffie-Hellman type thing that adjusts for this noise being here. Yeah. So if you’re doing Diffie-Hellman type things for encryption, you could say, hey, for signatures, I also wanna do not Diffie-Hellman type things, but I wanna do standard things. So maybe I’ll do Schnorr signatures or something like that. And a lot of people try to do this and all of them break because this noise here ends up being much more devastating. In particular, I mentioned before that the noise, you can think of it as an ephemeral part of the secret. So the noise is security sensitive. A lot of space signatures, until they started to be done properly, would often leak this noise. There would be attacks that would allow attacker to recover part of the noise. If you recover part of the noise, you can almost always break the scheme pretty easily.
Thomas: Can I just ask real quick what that attack looks like? Because this is like one of the rare instances where I have like a bit of an intuition for what that would be.
Mark: Yeah.
Thomas: But like, okay, so like I can see immediately why leaking any of the error bits in an LWE computation, like the whole reason why the system isn’t just Gaussian elimination is the error, right? So like obviously bad to leak it. But like, what does that attack look like?
Mark: So I’m pretty sure they ended up being machine learning-ish type attacks where the idea is that, uh, if done improperly, you get part— so lattices, they’re these, I mentioned they’re these point clouds. And you might imagine for these points, um, there’s kind of this initial block and then everything is a translate of that, right? So the kind of the inside of this initial block, you might call the fundamental parallel pipe, or at least lattice-based cryptographers do. So, um, so the attacks roughly would say that we can identify leakage somewhere within this fundamental parallel pipette, and then maybe it was some sort of like gradient descent-ish type attack on top of this with enough signatures to recover the actual secret, and then from there you win. It’s something along these lines. Um, there’s been—
Thomas: it’s, it’s much more interesting, interesting than the hidden number problem then, right? It’s not like we have a bit of bias and then I can literally just do like a, you know, a BKZ or something like that.
Mark: I think that there is this kind of averaging step you have to do. I don’t think you just create a lattice and I think you do need many signature samples.
Deirdre: Okay. Oh, so you do, you do need like one key and then are we doing—
Mark: I don’t know if there are attacks with a single signature. It’s not a huge amount you need. I think there are papers I’ve seen that have been like on the order of 500, but it’s, it’s something that like a, You know, it’s devastating attacks. You need to get this part right with lattice-based signatures. But that’s why if you look at stuff like Dilithium, Dilithium describes itself as kind of a Fiat-Shamir with aborts scheme.
Deirdre: Yes.
Mark: The Fiat-Shamir is as part of creating the Schnorr signature. The aborts is to say that, hey, if we would leak part of this error, we try again until we don’t leak it.
Deirdre: Oh, that’s, that’s fascinating. That’s where that comes from.
Thomas: This is still, this is getting more. So what is, What, what, what’s happening when we’re doing the Fiat-Shamir in the Schnorr signature that’s causing us to leak the error? This is like, ‘cause I don’t do signature stuff.
Mark: Well, I’m pretty sure it’s that the errors get too large. The rejection conditions in Dilithium are bounding the size of the error. I think there’s 2 rejection conditions actually, but I think that there was this paper a couple years ago that said that you only really need one of them, but that one is load-bearing. Although this wasn’t for Dilithium specifically, it was for Fiat-Shamir with the Borch type schemes.
Deirdre: Neat.
Thomas: Neat. That’s my contribution.
Deirdre: Okay, so for more exotic settings like FHE, why do you have to get more exotic and why are your parameters slightly different than the things that we might see in kyber and dilithium? And why are your assumptions more exotic as well?
Mark: So there’s a number of reasons for this. So the first thing is, I said FHE always uses ring learning with errors, not module. The reason for this is because of something people often call, like, I don’t know, seed compression, where an RLWE ciphertext has 2 components, A and B, and the A part is uniformly random. So you can just store a small seed there and you can use like an XOF or something like that to expand it. For MLWE, you kind of pick up more of these components in the front. So you would need kind of more of them. You could all generate them from a single seed. So in this setting where you can expand things from seeds, it doesn’t really matter. The issue is this expanding from seeds thing does not survive any homomorphic operations.
Deirdre: Wow. Okay.
Mark: So even something as simple as adding together 2 ciphertexts, well, now you have that, you know, an XOF of seed 1 plus XOF of seed 2. You can’t find a seed that really expands to that target. So, you now have to store the full 2 polynomials here, and in the MLWE setting, you have to store even more, right? So that’s kind of the— for FHE, you end up taking this big size hit, or sorry, this big bandwidth size hit, if you end up using MLWE versus RLWE. Okay. But there’s other more exotic things people use— do as well. And it’s worth mentioning, when I say for FHE, there’s 2 broad classes of FHE schemes. There’s what’s often called few or TFHE-based schemes, And then there is generally CKKS, BGV, BFE, they’re all kind of tensor product multiplication schemes. Okay. So for this first class, you get a lot more flexibility. You can do things much closer to public key type crypto. But the second class is the one that I’m describing that has less flexibility. In particular, for the second class, you get these weird assumptions about the error. So for, in public key cryptography, The error vector, you can kind of choose to be from any distribution you like, as long as it’s not too concentrated. If it’s too concentrated, there are these attacks from 2011, the reward-gate attacks, that start being applicable and concerning. But even things like, often people do Gaussian-type noise with standard deviation 3, that’s not too small, right? Gaussians are a little bit hard to generate, especially if you need to have a masked implementation of the generator. So instead you can actually just sum up a bunch of bits. It’s a binomial random variable. If you center it, it looks kind of Gaussian and it’s good enough for encryption. So the issue with this is that there’s this one component of FHE that’s very key where kind of a certain parameter scales with the sum of all these, the sum of the absolute values of all these coefficients. So instead FHE likes to have this noise be kind of sparse ternary noise. They want to make this as small as possible, which is a much more aggressive assumption for a particular reason. In particular, the error distribution and the secret distribution for LWE, they tend to be fine with anything. We have these proofs that like, as long as they have enough entropy, you can get— so there’s this thing called entropic LWE, where, well, there’s 2 relevant things to say, I should say. The secret distribution and error distribution, they can be the same. And then as long as the error distribution has enough entropy, things are mostly fine. But the worst-case to average-case reductions aren’t true in this setting. So even though we don’t use them for any choice of parameters, moving to settings where the worst-case to average-case reductions are no longer true is still often seen as something that’s very concerning. Okay. Just because, Uh, because you’re never quite sure how your, your parameters may be—
Deirdre: may break down, and then like at least— well, it’s more kind of deal.
Mark: It’s not like that. It’s more that in— if you’re in a regime where the worst-case to average-case reductions hold, then you kind of have this understanding that it’s hard for there to be atypical structure there that wouldn’t also help in the gap SVP world. Okay, it might help with much smaller gap SVP instances But an algorithm here is concretely an algorithm for gap-SVP, right? With the caveat of this tightness being bad. But if you start falling outside of this worst-case to average-case setting, then there could start being non-trivial attacks that wouldn’t also imply an attack for gap-SVP.
Deirdre: Okay.
Mark: So, so yeah, so in FHE, the secret distribution can often end up getting much weirder with much more aggressive assumptions. I’ve seen papers that suggest Hamming weight 32 and Hamming weight 64 secret keys, which are very small numbers, although I don’t think there have been attacks on these schemes. So, but there’s also the ciphertext modulus can get very large in FHE. Roughly, for Kyber, ciphertext modulus is 14 bits. It’s relatively small. In FHE, each, for at least these tensor product-based schemes that I was mentioning I was focusing on, Each time you do a multiplication, you kind of have to shave off 50 bits from your ciphertext modulus, very roughly. So if you have this complicated circuit you need to compute, say a bootstrapping circuit, then you might need to support 800-bit, 1,500-bit modular, things that are much larger than the 14 bits that Kyber uses.
Deirdre: Yeah, yeah. I would need some like big limb arithmetic and all of this has to be prime.
Mark: So you can usually— no, it doesn’t have to be prime. That’s one of the benefits of all of these LWE-based schemes is that the number theoretic structure of the moduli does not really matter at all.
Deirdre: Oh, good.
Mark: So as an example, Kyber is— I think Kyber is prime, but it doesn’t have to be. I mean, Sabre was another NIST finalist and it’s 2^32, right? So it doesn’t really matter. For FHE, they take a bunch of word-sized primes and they multiply them together. So they do CRT-based things, but you could do plenty of other things. It doesn’t really matter. Cool. Wow.
Deirdre: Okay. So we’ve basically done a whole tour of the history of lattice-based cryptography, including some of the whiz-bang stuff that, depending on your field, you may see some FHE stuff or things that use FHE constructions under the hood, such as like BLIND.
Mark: They are being deployed practically, generally not full FHE schemes.
Deirdre: Yeah.
Mark: But I think Apple’s Caller ID uses Uh, it uses homomorphisms of lattices. So it’s like a—
Deirdre: I wouldn’t be surprised.
Mark: It uses very weak, uh, homomorphic, uh, lattice-based stuff.
Thomas: Yeah.
Mark: And I think Google might have something as well, but I forgot.
Deirdre: Yeah, those are, those are the areas that I expect more things to kind of trickle out because like things that we might have used, uh, blinded commitments, uh, or other, other things using elliptic curves basically a write-out if you’re trying to deploy anything that might be quantum resilient into the future. And then you start reaching for lattice things that generally might have something FHE-ish under the hood. You’re just not doing a full, you know, like fully homomorphic computation with a bunch of other fancy stuff. But under the hood, that’s, you know, if you’re trying to do anything with homomorphic commitments and doing anything with that, like that’s secretly fully, you know, Uh, homomorphic reductions underneath, underneath it, and I expect more of those to show up.
Mark: Um, yeah, it’s also worth mentioning it’s not purely a quantum, pre-quantum thing, right? So a lot of FHE applications actually don’t particularly care about the quantum security aspect of things. It’s like, even in these kind of relatively simple settings, lattice-based things tend to be very fast.
Deirdre: Oh yeah, that too. Yeah, yeah, yeah.
Mark: I mean, they’re the only real cryptography we have that I’ve seen some people describe this, you know, quasi-linear time where, you know, the, the, the compute kind of almost scales linearly with just the size of the things you’re operating on. Yeah, it’s not common.
Deirdre: And like, you could make an argument that in terms of trying to find quantum-resistant, you know, replacements for the stuff that’s like the boring crypto that’s deployed a lot all over the place, like key agreement or the equivalent of key agreement and signatures, that’s kind of why they win is because they’re very fast and they’re quantum-resistant. Um, and they generally are small enough, uh, to fit in a lot of places. And a lot of the other, uh, problem— other cryptographic problem lineages just don’t seem to fit for one reason or another. Um, but yeah, there’s other problems that like there just isn’t— it isn’t even equivalent, like the fully homomorphic stuff.
Thomas: Like when you, when you, when you put quantum into that mix there, it’s kind of obvious why it’s so attractive right now. But like there’s There’s a— I don’t know the answer to this question, but there’s a reason that we ended up using curves and not nTrue back in the ’90s, right? Like, and part of it is that we didn’t care about quantum then, but like, I mean, so if it’s in the ’90s, so you’ve got like an almost 10-year head start.
Mark: Yeah, so nTrue was mid-‘90s, so it was a little bit later. It had some patent encumbrances. I think, what’s it called, elliptic curves did as well, but the entropy ones would have been earlier. Sorry, not earlier. There would have been— the patents would expire later in the future, I should say. I think, how to say, it probably also didn’t help that the entropy-based signatures were broken pretty quickly.
Deirdre: Yeah.
Mark: So I think they were broken before 2000, so that would make And true encryption looked a lot more suspect these days. It seems mostly fine, but there have been non-trivial attacks against NTRU that are not possible against RLWE. So there are some concerns to have against NTRU, but it hasn’t impacted the public protocol feed parameter chain.
David: Sure.
Thomas: Like, also, the vibe I have is that, like, just LWE has, like, a clear kind of theoretical basis for it. Like, LWE is a cleaner abstraction.
Deirdre: Right?
Thomas: I’m more— I think I’m more just like, there’s, there’s sure, like, we had reasons to trust curves more than we had, you know, and true or whatever, like, that now happened to be considered lattice. But like, there’s practical reasons, I assume, right? Like, nobody was thinking this, like, no one was thinking this carefully. I was there in 1998. Yeah.
Mark: So the main things that I would say for practical reasons, or at least why lattices are more appealing now, Lattices, there are a bunch of, you know, this matrix-vector arithmetic, or rephrasing in terms of polynomials. So they, with vectorized multipliers and vectorized adders, they kind of take advantage of that vectorization very well. That probably wasn’t as relevant in the ’90s. Lattices are bigger, so that’s, you know, a clear downside. And yeah, like those are the big downsides that I know have— sorry, that I know. Like I don’t know how fast lattices are compared to elliptic curves if you remove AVX instructions.
Deirdre: Oh, they’re faster. They’re, at least the, the, the Kyber LWE stuff, you don’t even need speedup. Like maybe, maybe you would speed up your hash function, but that’s independent of the, of the lattice.
Mark: Is this on, is this on architectures? Like, look, lattices auto-vectorize relatively straightforwardly. In many settings as well. So this is ensuring no AVX instructions.
Deirdre: Yeah, like even, yeah, even naive implementations with no vectorization, um, are very fast. Um, and you might have to do some tricks, uh, maybe in like 128 versus 512, uh, for, sorry, for like if you do Kyber 512 versus, uh, say P256 or something like that, or x25519. The x25519 might go faster than you, um, but you’ve had, uh, some good, uh, optimization tricks, uh, added on to that for a while. Um, it’s not— it’s not difficult to do a very fast naive non-vectorized assembly or intrinsics, uh, uh, LWE Kyber.
David: Sure.
Thomas: And we’re also— we’re fully Curve committed before Curve type— before 25519 happens. We’re already like, the P-Curve’s won, like Yeah. One other relevant point though.
Mark: I don’t remember the initial parameter sizes from NTRU, but so there’s— NTRU wasn’t initially phrased as a lattice-based cryptosystem, but quickly it was determined you could reduce it to a lattice problem and then attack the lattice problem. Algorithms for attacking lattice problems did have substantial advances between 2000 and maybe 2015, 2018, somewhere around there. So The security story for NTRU, like, probably didn’t look that great as those advances were happening. I don’t know. Again, I don’t know what parameters they initially chose, but if they chose parameters aggressively enough, they probably would have been broken, even if current parameters are probably fine.
Deirdre: I mean, yeah, I’m seeing some sample params. Yeah, go ahead.
David: Timing just doesn’t work out. The NIST curves were being standardized in like ‘98, ‘99, and you have NTRU coming out in like ‘96, right? That’s just not going to fucking happen. Like on that timeline, no matter how good it was, to say nothing of the fact that we couldn’t do signatures with it. Like, and a little bit because we tried signatures and they broke at the time too.
Thomas: So which again, I could do a full hour just on attacks on naive Schnorr LW signatures or lattice signatures because those attacks are really neat. So I’m going to short circuit this a little bit and just say Simplified and true prime. So SN True P versus original and true, where are we?
Mark: So I, so how to say this, I’m SN True P, I would describe the following way, but I, I haven’t looked at the original and true scheme as much. So SN True P is roughly the following. And what I’m saying here, this story also was replicated in the, like, the LWE land. Like, roughly there are 3 ways to build lattice-based KEMs. You kind of start with your pseudorandom component. It could be the NTRU assumption, it could be LWE assumption. That pseudorandom component kind of has this secret part. It’s not good for anything public key. The initial thing people did, at least in LWEs, you would take this randomized subset sum of it, and then the random coefficients from the subset sum, you would have that be another secret, and then this kind of is roughly the 2 secrets, sort of. So this you might call leftover hash lemma-based construction, because for its security you need to appeal to something called the leftover hash lemma. The other thing that you can do, at least in LW land, I don’t know if this works for Andrew, is instead of doing this randomized subset sum that needs these leftover hash lemma type constructions, which the downside for them they obtain this stronger form of security. They obtain kind of a statistical indistinguishability of— they don’t obtain that form of security, I should say. But applying this step to kind of make this randomized sum look uniform again, that this requires— this single part of the reduction is statistically secure. So the parameters chosen for it are maybe a little bit larger than you might want without impacting positively your total end security that you get. So instead of doing that, you can actually do this other second application of the LWE assumption to get something that uses slightly smaller parameters. Both of these, they create this kind of random pad that’s agreed to up to these low-order errors, and you can add messages to it, do a one-time pad type thing. The final thing you could do is you could just say, hey, I just wanna build a KEM. I don’t actually care about messages. So you could have this random pad and you could just apply some shared function to it that will agree on a key. So this type of third thing, this is closest to what sNTRU-P does. Although from NTRU, you can also build directly public key encryption, so you could do these other constructions as well, at least the variant of the leftover hash lemma thing, I think. So there initially were these LWE-based things that looked closer to sNTRU-P that didn’t have this explicit message and followed this paradigm. But they ended up not being as popular in the NIST scheme, as I’m sorry, in the NIST competition. I think New Hope initially was of this form, but they changed it. And I don’t think any finalists ended up being of this form. For LWE in particular, it’s hard to make the resulting KEM CCA secure. For NTRU, it ends up being easier to do. So you can get SNTRU-P CCA secure based off of kind of taking this NTRU assumption and then What’s it called? I think, I’m assuming they don’t do this leftover hash format type thing, but you don’t include this message, you apply this decoding stuff to get the shared quantity and then to get CCA security because it’s, there isn’t any, it has a straighter, more straightforward path to CCA security.
Thomas: So like the subtext of that is kind of like, obviously if you’re a nerd, right, is that like in the IETF and in NIST and all that, there is basically a drama between module-LWEE and Kyber and sNTP, right? Like sNTP was implemented in SSH originally, uh, you know, New Hope, which is RLWEE, I guess, was, uh, you know, browsers before that. But there’s like, there’s key implementations of all these things. And then like module-LWEE is like the standard now, right? And s-entropy is like, I don’t know, I don’t know what you would call it, like, but it’s the, it’s the other system that people think about or advocate for. And so like, like the big debate, especially among people who, you know, don’t do this professionally, is like, is, are we taking a huge risk flyer on using module LWE as opposed to using something like simplified NTRU prime?
Mark: I’m biased being a fully homomorphic encryption person. NTRU is not secure in fully homomorphic encryption anymore. It is for these TFHE few-type schemes, but in 2017 there was a non-trivial attack that applies only to NTRU that breaks it in every parameter regime I care about. So maybe it’s more conservative, but that’s only from a certain definition of the word conservative. In applications that I care about, I can no longer use NTRU even though it has appealing computational properties, ‘cause it’s explicitly insecure.
Deirdre: So, but, uh, but non-FHE for, for just regular public encryption?
Mark: Like, well, the thing is, non-FHE, this attack did not get down further, right?
Thomas: Okay.
Mark: But it’s like, it’s this type of thing where it’s like, let’s say McEliece. People like McEliece. I mean, people like McEliece. Some people advocate for McEliece, right? And one of the justifications people give is that it showed up, you know, in 1978 and it’s been secure ever since. But in the last few years, it’s not been true. There’ve been this series of papers that have said, hey, there’s maybe this additional structure in McEliece that can be exploited. And it’s, uh, I’m not sure the current status of the papers, but at least the abstracts are getting pretty concerning, right? So whenever there’s this like additional structure showing up, it’s something that gets a little bit concerning. Arguably this happened for NTRU in 2017 with these additional attacks on FHE. It also arguably did happen for RLWE with these attacks, these quantum attacks on the sig figs.
Deirdre: Scheme, right?
Mark: Or on this adjacent assumption on kind of ideal SVP, but not the rank 2 version that you would need to break RLWE.
David: Right.
Mark: So there are like these things where it’s like, whenever I see one of these kind of non-trivial attacks on something adjacent, it’s like, well, can it move over? You know, is it something to be worried about? So I would be a little bit worried about RLWE and a little bit worried about NTRU for both of those reasons.
Thomas: So I mean, that’s also like, that’s literally, that’s literally the logic of safe curves, right? It’s like, here are adjacent attacks on specific curve structures that only matter in specific regimes, ergo never use these curves, right? And it’s like, it seems like that’s essentially the same argument here.
Deirdre: It’s like, yeah, so it’s, I mean, it is in this, in the year of our Lord 2026, but are, Mark, are you trying to like hint towards Yeah, I don’t know if I want to use those assumptions anymore because what if they keep moving? What if those attacks keep getting better?
Mark: It’s mostly that. Well, it’s in my day-to-day job, I just explicitly can’t use NTRU. Right.
Deirdre: Okay.
Mark: Right. And it’s that if I— a lot of this is kind of vibes-based in the sense that if you look at the threshold—
Deirdre: A lot of cryptography is vibes-based, honestly.
David: Yeah.
Mark: But if you look at the threshold for where we currently think it’s safe to use NTRU versus not NTRU, I think it’s if you have this ciphertext modulus q, I think of its q being roughly less than 1 over 100 n to the 3.2 something, or maybe it’s some arbitrary number. And arbitrary numbers appear plenty of places. The best lattice attacks have arbitrary numbers in the exponent. So it’s not like arbitrary numbers should totally disqualify a scheme from being used. But then also it’s like, I would feel more confident if there was some clean number and being like, oh, the attacks can’t go below that. Yeah, it’s this clean number.
Deirdre: So, okay.
David: I want to just compare and contrast a little bit back with elliptic curves, just in terms of like timelines and analysis. Like you have Kobletz and Miller being like, let’s do elliptic curve Diffie-Hellman in ‘87.
Deirdre: 1985. I always thought it was ‘85.
David: ‘85 when they wrote the paper, ‘87 when it was published.
Mark: Right.
David: And then NIST standardizes that in ‘99, 2000, meaning there was some sort of lead-up to that. Now, we’re much, much better nowadays at writing cryptographic standards than we were then, despite the best efforts of NIAF. And, but like, if you go back and you look at like, what were all the problems with like cryptography in the 2000s and 2010s, they were by and large not with the primitives of that era. They were like, these standards all are written poorly and like some of these protocols were dumb or like the way in which we chained AES together was a bad way to chain AES. But like primitives more or less held and you like look at, you know, P-256 like we’re still using today. It’s not quantum secure, but, you know, that takes 10 to 15 years to get standardized and then another 10 years for adoption. You look at, you know, lattice-based cryptography starting in the ’90s, 10 years later, looking at RingLWE, and 20 fucking years after that is where we’re at now. Right? Like, I don’t, I’m not a primitives person. I’m not picking parameters for these things. My job in the last basically decade plus has been to listen to people who do work on primitives, then figure out how to use them in the real world. And if they’re being used correctly. And the answer is people have been like looking at this stuff for longer than elliptic curves, like at the time that they were deployed. These are, these are a safer thing to move to. Um, and like if you are, um, you know, familiar with like Diffie-Hellman and, and, and, um, cyclic group based like cryptography, like I encourage you to go to like your preferred AI chatbot and say, I understand Diffie-Hellman, explain to me enough like algebra to understand Kyber, it will do it very good.
Mark: I did it earlier today.
Thomas: Literally, this is literally what David did before this episode.
David: I did it like earlier today because like, again, actually understanding like all the details of the crypto systems is like not relevant for day-to-day use a lot of the time.
Thomas: Yeah, I’m just waiting for the IETF post where they say David Adrian, who just learned how Kyber worked 5 minutes before shooting this episode, because it turns out that like part of this is like evaluating, you know, experts on various serious things than making decisions.
David: And like, that, that’s the way it goes. And I think we’re actually at like a very conservative point of using lattice cryptography. Like post-quantum cryptography.
Mark: Yeah, I think something, I think something that’s not appreciated often by people who are concerned about lattices, like I’ve seen a lot of arguments that I have a hard time following. Like people have mentioned Dual EC was bad, so we should be concerned about LMLKEM.
Deirdre: Everyone knew Dual EC was bad. But when they first suggested it—
Mark: but so this is true, you know, if, uh, the potential for backdoor was known. And then also, not only that, like, if default parameters weren’t published, I don’t know if DualCEC had any issues. I think the issue was both the potential for backdoor and default parameters being published that were the backdoor parameters. But even ignoring that, if for Lattices, very early on in the— I think it was in Lattice Cryptography: The Internet, there’s this section that says, hey, backdoors are bad. This particular component of the scheme could be a backdoor. We’re gonna throw away some efficiency to make sure that it can’t be leveraged. And every scheme since has always done this. Like, it’s, you know, lattice-based cryptographers also want to build secure systems and it shows up in the constructions. But not only that, like, there’s this, like, the concerns over the NSA and potentially backdooring or, you know, subverting cryptography with lattices, are a little bit confusing just because it seems like everyone else is moving over to Lattices too. So Europe, for the most part, has also chosen lattice-based schemes, not always the same schemes. The BSI, so the German InfoSec government group, have chosen FrodoKEM, I think. The Chinese are not, they have not yet announced what schemes they’re gonna be moving over to. They’re rather early in their process. I think a couple of weeks ago they had the final submission period for their schemes closed down. But the comments that you can see from certain Chinese cryptographers make it seem like they’re gonna be going for lattice-based schemes. They’re gonna be lattice-based schemes with Chinese characteristics, which for Chinese lattice-based schemes, there’s, there was a NIST submission, LAC, which is maybe good to look at. It was doing something roughly Kyber-like, except it chose a very small modulus, 8 bits instead of 14 bits. And it tried to argue that by doing some error correction argument, you could get things to work. It got broken. So the issue for why it got broken is somewhat technical, but roughly the Chinese response to it appears to be that we’re not going to do LAC again, it got broken. Instead, we’re going to switch to an unstructured lattice-based thing, maybe because they’re worried about the algebraic structure, but also because the algebraic structure is specifically what made this error correction component of LAC break. So another way to fix that is just use a larger modulus like Kyber does. So It’s, it might be that either one, it’s hard to tell.
Thomas: But like in the BSI case, and I guess in the Chinese case, if they do unstructured lattices, right?
Mark: Like if you’re using ProtoChem, there really is an argument there that they wouldn’t use ProtoChem exactly. I think they’ve—
Thomas: right, what is it?
Mark: I think it’s S-Cloud Plus. It’s really like, it’s more like a ProtoChem version of this black scheme, which had some roughly— how to just describe it. So in lattice-based schemes, you have this error, And when you decrypt, you get the message plus the error back and you have to remove the error. Almost every scheme, you just round off the low-order bits. That’s where the error was, you’re fine. You could say, hey, handling errors, that’s like what error correcting codes do, or that’s what these types of things do. I can do something fancier to be able to tolerate more error and then choose smaller parameters. This is roughly what LAC did and it is roughly what SCLAW+ does versus FERDECAIN. Okay, so it’s a little bit different.
Thomas: But like, if you collapse it down to just like the German case, right? Like the, the, the, like the Fortikam decision there really is more conservative than the Kyber thing.
Mark: So it depends on what you mean by conservative, ‘cause it’s like, if, if I wanted to make AES more conservative, would I design a new block cipher or would I say AES with 1,000 rounds?
David: Right.
Mark: Well, the new block cipher, I mean, it, it might be good, but AES with 1,000 rounds, you know, AES would have to be really weak before 1,000 rounds is broken. Right. So conservative usually in cryptography means within a certain efficiency budget, right? So for FrodoKEM, is it more conservative or is doing Kyber but doing Kyber with modular rank 15 more conservative? I mean, it’s hard for me to say, you know, you, if you’re saying downside for FrodoKEM is the large ciphertext and I have this large ciphertext budget for conservative, being conservative, is it better to use an LWU-based scheme versus MLW?
Deirdre: I just don’t know. Yeah.
Thomas: Oh, that’s good. That’s a really good way of framing it. That makes sense.
David: Yeah.
Deirdre: Yeah.
David: And I will say, if you are a country and you are trying to get me to care about your cryptographic standard, you need to have at least twice the GDP of California for me to start reading your standard. We’re just going to set that as the bar. Looking at you, Germany.
Deirdre: Also, I wanted to— I wanted to also shout out South Korea that also did a PQ competition and they also selected lattice-based. Uh, KEMs and signatures, I think. I think there was Smaug and, um, another one. Um, but they’re slightly different. They have slightly other assumptions, but it was kind of like looking at what, uh, came out of the NIST competition and we’re like, oh, we can make some tweaks to some of these things and learn some stuff. Uh, we’ll, we’ll see. We’ll see if they get implemented and deployed in anywhere.
Mark: Yeah, it’s There are many different choices that you can make with lattices. I mean, even in this competition, like the final 3 lattice schemes, you really could have chosen most of them and gotten something mildly different and probably fine. But it does seem like essentially every country I’ve seen that runs a standardization, or at least every appreciably large country that runs a standardization, is kind of converging on lattice-based things. And this, I’m sure this has some downsides. If lattices end up being weak, you know, that’s bad for everyone. But it also like for this kind of argument that the NSA is trying to standardize weak Cryptography, it’s like, okay, well, why is China going along with it? You know, why is it’s it makes it a little bit more confusing of an argument.
Thomas: Right? Although the the freaky argument online, or the the freak argument online, is just that like lattices are fine, modules are the problem.
Mark: Yeah, but in that case, if if the NSA is saying, hey, China is doing unstructured lattices and we’re going to do modules, it seems like they’re intentionally doing bad things in like that. Geopolitical fight, you know.
Deirdre: Um, I’d be remiss to not forget about, uh, Falcon, uh, the future FN-DSA, which we’re totally gonna get a draft standard for any day now out of the Department of Commerce. Um, do you have anything to comment on these, uh, floating point-based lattice schemes?
Mark: I, I, I’m uncomfortable with it. I don’t know, like, it’s, it’s really small signatures.
David: That’s great.
Mark: I’m sure some people will do it right. I, it feels like something that’s very easy to get wrong, uh, but maybe I’m pessimistic.
Deirdre: Um, you’re not, you’re not the only one that’s, uh, just feeling a little about, uh, implementing Falcon securely.
David: Um, floating point numbers aren’t real. They can’t hurt you.
Deirdre: I mean, they can hurt me and secure implementations of my cryptographic software, so Wait, how do you even handle constant-time Falcon with subnormal?
David: So it was just DOA. There is maybe one person in the world that understands how to handle constant-time floating points, and it’s not clear if anyone else understands what they’re saying or will be able to duplicate that.
Deirdre: Yep, uh, yep, exactly that. You literally clone like One person. Stick them in your mouth.
Thomas: Okay, so what have we learned today? I’ve learned that Oded Regev, who is the godfather of all lattice cryptography, is now a computational biologist. Yeah, he saw this coming and exited the field.
Mark: Yeah, I have no clue why he switched over. And it’s not purely computational biology. He actually writes mathematical lattices papers as well. That like he had a paper that got into the Annals of Mathematics recently. So it’s like, you know, one of the best math journals in the world. So he still writes lattice papers and he still does quantum papers and computational biology and it’s a ton of stuff.
David: He’s just excluded us, the terrible group of people. Like, I don’t want to be at these NIST things.
Thomas: Yeah, my son is a grad student and an aspiring computational biologist.
David: So this is—
Thomas: I don’t know, it gives me— it gives me a thing to talk about with my son. So you, you’ve healed my family.
Mark: It’s fun to hear.
Deirdre: I’ve learned that you really, really need to get a quantum algorithmist to build your cryptography because that’s gonna stand the test of at least 20 years where other people fail. Um, and you just have to catch them before they turn into a computational biologist.
David: I’ve had a couple hours ago.
Thomas: So I learned you should definitely ask chat.
David: Cyberworks. So, you know, we’re all learning something today.
Thomas: I also, I think everybody should go on ChatGPT and just ask it to spell out how an attack on a naive LWE Schnorr signature works. Oh yeah, it’s a neat attack. It’s a neat, like just the blueprint or the schematic of that attack is pretty neat.
Deirdre: Well, we want to talk a little bit more about that in a second. I want to give a shout out to Alfred Menezes. Who is, you know, one of the OGs of elliptic curve cryptography, has been cranking out a whole series of lectures free on YouTube on his YouTube channel. We’ll put the link in the, in the notes on post-quantum cryptography, on a whole bunch of cryptography, free and available. It’s amazing and it’s pretty cool. So if you’d want to learn how Kyber works and how a lot of these crypto, last crypto schemes work, Um, that’s a good place to learn if you don’t want to turn to your local large language model to do it. Um, cool. Anything else?
Mark: It’s also worth mentioning, uh, so Menzies, uh, Armen Menzies, his, uh, the paper showing that regabs reduction, um, is not highly non-tight.
Deirdre: Yeah.
Mark: So could never really be possibly useful for setting parameters. It was one of his papers.
Deirdre: I didn’t know that. Oh my gosh.
Mark: It was one of his Another Look papers.
Deirdre: Oh my goodness, I have to read that one now. All right, um, is there anything else, Mark, that you wanted to, to bring up before, before we wrap?
Mark: I don’t think so. It’s— yeah, like lattices, like, uh, people seem very concerned that they might break in surprising ways, and I can’t unfortunately guarantee anything about the future in any context. But if you want to see a lot of examples of lattices breaking in surprising ways you can look 20 or 30 years ago because there were many very funny ones.
Deirdre: Yeah. So yeah, that’s a good place to do it.
David: Okay. It is a little funny that when we were an audio-only podcast, we did a very visual discussion of lattices. And now that we are a video podcast, we did an entirely audio discussion of lattices where some visuals probably would have helped a lot.
Deirdre: Yeah.
Mark: Sorry about that.
David: That’s not your fault.
Deirdre: You know, you were, you were, you were doing a great job with the, with the linear algebra, actually. And I mean, I understand. Yes.
Thomas: The rotations.
Deirdre: Exactly.
Thomas: This is the most fun that Deirdre has had on one of these episodes where we weren’t just talking about isogenies.
Deirdre: Yeah, well, oh, and that’s another one where you’re like, oh, you— lattices are not— don’t just show up in lattice-based cryptography, they show up in a bunch of cryptography, such as isogeny-based cryptography like ski sign.
David: We all know it worked out great.
Deirdre: It’s totally great. It’s fine. Nothing— don’t worry.
Mark: I mean, even like, this is something Trying to define what lattice-based cryptography is was something I was thinking about today because it’s like, well, cryptography like based on lattices, any elliptic curve over the complex numbers is a lattice. Yes. Or rank 2 lattice. So it’s like, is elliptic curve cryptography lattice-based cryptography? No, that’s very stupid, but it’s complicated terminology.
Thomas: This is why you can’t look anything up on Wikipedia because everything on Wikipedia is written that generally.
Deirdre: Yeah.
Thomas: You’re the problem.
Deirdre: All right.
Mark: I think— for the record, I, I would, if anybody has a good definition of lattice-based cryptography, I’d be very interested in hearing it because I’ve been trying to think through it and I keep running into these weird cases where it’s like, oh, you know, if Schnorr’s factoring algorithm worked out, would RSA be lattice-based because the best attacks are lattice attacks? You know, are elliptic curves lattice-based because elliptic curves are lattices? So it’s, there’s gotta be some definition somewhere, but I haven’t found something. That makes sense to me. Yeah.
Deirdre: Besides it being like this socially defined research area, you might need to write that blog post.
Mark: Cool.
Deirdre: Thank you. Thank you, Mark. Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. You can find the podcast online at SCWPod and the hosts online at DurhamCrestlum, @TQBF, and @DAdrian. He’s got the new handle. You can buy merch online at merch.securitycryptographywhatever.com. If you like the pod, give us a 5-star review wherever you rate your favorite podcasts. Thanks again to Teleport, who is sponsoring our event in Las Vegas between Black Hat and DEF CON. There are links on our website about trying to find us in the liminal space between Black Hat and DEFCON in Vegas this year in a couple of weeks. Thank you for listening. All right, let’s hit the button.
Thomas: That was awesome. Deirdre: Okay. Teleport. Teleport ad read. SCW Pod is sponsored by Teleport.
David: You should probably introduce us first.
Deirdre: Wait — oh, we’re doing the ad read during the podcast?
David: Yes.
Deirdre: Got it. Okay.
David: And then we’re going to talk about Teleport, who’s sponsoring our live event — well, our happy hour. I’m just going to talk about it now. We’re doing a happy hour again in Vegas, in the liminal space between Black Hat and DEF CON, like we have done every year for the past three years, and it is once again, like last year, sponsored by Teleport. If you don’t know what Teleport is, you probably don’t have SSH. We’re very happy that they’re sponsoring, and we can attest that Thomas is a Teleport user.
Thomas: We use Teleport everywhere at Fly. We love Teleport very much. If you’re SOC 2, it is a very, very good way to get a lot of business processes all tucked under a recorded SSH dealy. Teleport is great. Use Teleport for everything.
Deirdre: Awesome.
David: I’d like to say this is Security Cryptography Whatever, and my name is David.
Deirdre: I’m Deirdre.
David: And today we’re talking about lattice cryptography on this very professional podcast, with our special guest, Mark Schultz-Wu. Mark, how are you?
Mark: Hi. Yeah, I’m Mark. Thanks for having me.
Deirdre: Thanks for being here. This is lattices redux, because on one of our very first episodes we talked to Chris Peikert about lattices, which was great. He also tried to show us a bunch of slides, so we ended up talking through what our audio-only listeners were supposed to be seeing — a depiction of dots on a field with vectors, that kind of thing. So this is another chance to get into lattices and try to understand the area of lattices and post-quantum cryptography.
And you were posting on the internet recently some very, very useful history of where we started with lattice cryptography, what got broken, and how we got to things like Kyber, Dilithium, and some of the fancier things you’ve done research on. So we’d basically just like to have you talk through what you began posting elsewhere — the history of over 30, maybe 40 years of lattice cryptography.
Mark: It’s worth clarifying up front: I am a lattice cryptographer. I graduated in 2024, I think, and I worked with Daniele Micciancio. I was working on fully homomorphic encryption. I do have some background in lattice-based KEMs, but my publications — with the exception of one, on lattice-based public key encryption — were more on the fully homomorphic encryption side.
Deirdre: Got it. And that’s some of the fancier stuff. Especially if you’re trying to do a post-quantum solution to anything slightly fancier than public key encryption or signatures, sometimes you may be tempted to reach for the fully homomorphic solution, because it seems to solve your problems — but it might do it in a way that’s computationally costly, or large.
Mark: Computation and bandwidth. In general, the fancier the lattice things get, the bigger you have to make one of the parameters, the modulus, and then you also have to increase the dimension as well. So you can think about two parameters that counteract each other and keep getting bigger and bigger, and then everything gets big. And that’s how you get FHE papers that talk about twenty-gigabyte keys. It’s not the biggest keys, it’s not the smallest keys — if you’re optimizing for size, maybe you get down to three gigs or whatever — but it’s very far from the public key thing.
Deirdre: Gosh. And I want to get back to that. Let’s start at the simple beginnings and then get over there, because then we can talk about why some of these instances of lattice problems feel a little bit riskier. Occasionally a paper will show up and say, oh, anything with parameters that are slightly this far apart — which is bigger than what they are for Dilithium and Kyber, basically, or anything more complicated than that, that’s FHE-like — gets scary. Anyway. Thomas.
Thomas: I mean, I have a specific thing here, right? Which is that, as always, I’m just trying to reinforce things I say on Hacker News. A claim I make kind of regularly — which I shouldn’t be making, because I don’t know what I’m talking about — is that lattice cryptography and elliptic curve cryptography are of… they’re not literally comparable vintage, I think, but they were both live ideas in the 1990s, right? I like to say that there’s an alternate universe where lattices win over curves.
Mark: It depends on the particular application. The NTRU cryptosystems, both of them, were introduced in the mid-‘90s, and the NTRU cryptosystems that we see these days are very similar to what was around in the ’90s. I don’t want to say exactly the same, but at least for NTRU encryption there are a lot of similarities.
NTRU signatures from the ’90s got completely broken. Lattice-based signatures had a very rough going until — the first secure lattice-based signature was in 2008, which is rather late. The way I like to describe how late it is: fully homomorphic encryption was in 2009. So we didn’t get signatures before fully homomorphic encryption, but it was remarkably close, which is kind of wild to think about. You would think FHE is a much harder problem. Lattice-based signatures are very well understood at this point, but it took a lot longer to get there because of some additional complexities that show up with lattices for signatures in particular.
Thomas: So, because of post-quantum cryptography, there’s an attitude that lattice cryptography is moon math, whiz-bang stuff, right? And one of my things is just pushing back on that notion — that we don’t have a good understanding of what lattice cryptography is. Another thing I like to point out is the gap in time between NTRU and LWE, or NTRU and NewHope or something like that, versus the P curves and Curve25519, right?
Mark: NewHope is a great example here. NewHope was in Chrome a decade ago. It was in experimental releases of Chrome — you had to opt in. This was a decade ago. The scheme has had no substantial cryptanalysis in the last decade, no substantial improvements to cryptanalysis in the last decade. When I say a decade, I’m rounding up a little bit.
I think the most recent substantial improvement to lattice-based attacks was in 2018. When I say substantial improvement here, it’s worth mentioning that lattice-based attacks usually separate into two components. There’s one which is phrasing the problem as a lattice, and the other is solving the lattice problem. When I say the substantial improvements thing here, I mean the second part, solving the lattice problem. There have been some iterations on improving the phrasing thing as a lattice problem — if you’re familiar with the MATZOV attack, this is kind of in that first bucket.
One difficult thing with lattice-based cryptography, which I was actually struggling with a bit today — I was asking some people and getting not that great of responses — is that it’s really kind of a socially defined field, in a certain sense.
Deirdre: What do you mean?
Mark: You might say, “Okay, lattice-based cryptography, what does that mean?” A very easy answer would be, well, it’s cryptography based on lattices. Unfortunately, this isn’t true at all. As an example, in the NTRU paper — the first NTRU preprint — the term “lattice” appears never. Any cryptographer these days would call NTRU a lattice-based scheme. If you published a paper on NTRU, it would get put in the lattices track. And it was described as a ring-based cryptosystem initially.
Deirdre: I mean, okay, I get that.
Thomas: It reduces to lattices, or it can be rewritten as a lattice.
Mark: But this is also not a satisfying way to define what lattice-based schemes are. One reason for that is that elliptic curve-based schemes don’t reduce to elliptic curves. They reduce to Pollard rho on a generic group, right? So maybe you call them group-based crypto, or you call them Pollard rho crypto. I don’t know. We don’t tend to define problems based on what they reduce to. I mean, factoring, you sort of do — but also, you can break RSA without breaking factoring, by breaking modular pth polynomial roots. You do not need to break factoring to break RSA. So naming’s kind of all over the place.
In general, lattice-based schemes do get broken by lattice-based attacks, and I’m pretty sure that’s how the naming for NTRU got decided. It was ring-based, and then there was a lattice attack on it, and now it’s lattice-based.
But if we’re going based off of schemes that are broken by lattice-based attacks, the first one was actually in 1978, with the knapsack-based cryptosystems that Shamir famously broke. So maybe these knapsack cryptosystems are lattice-based. I would personally argue they are. My advisor had some papers in the early 2000s on knapsack-based cryptosystems, and he’s a lattice-based cryptographer. So there’s a sense in which lattice-based cryptography is the cryptography that lattice-based cryptographers do, and often involves reducing problems to solving computational problems on lattices.
Thomas: Other than NTRU — check me on this — the schemes that we’re talking about when we think about lattice cryptography are remarkably similar, right? They’re all based on basically the same LWE problem.
Mark: Yes and no. The popular ones these days, I’d say there are two big counterexamples to this, or maybe three.
As an example, one thing that you might say is that lattices are the only way we can get FHE. That’s sort of true if you define lattices in the right way. In particular, there’s this problem called the approximate greatest common divisor problem that was popular in the early 2010s. It kind of looks more like a number theoretic problem, something closer to RSA, but it also kind of looks like a lattice problem if you do lattices a lot, and we can get fully homomorphic encryption from it.
Antoine Joux also has this cryptosystem he called the Mersenne prime cryptosystem — I think it was somewhere around 2015 — that also kind of looks like a lattice-based cryptosystem, and also doesn’t. It’s not LWE, it’s not NTRU, it’s its own thing.
More recently, there are these lattice isometry problem type cryptosystems. It has “lattice” in the name, so maybe it’s lattice-based, but also the first part of any paper on these is always, “Here’s how we rewrite everything in terms of quadratic forms, and now we’re going to do everything in terms of quadratic forms.” Mathematically, quadratic forms and lattices are kind of equivalent, so it’s still kind of lattice-based, but computationally quadratic forms end up being nicer for most cryptosystems.
That all being said, the predominant lattice assumptions are almost always the learning with errors problem, or an algebraically structured variant of it, or a variant with rounding — learning with rounding, that type of thing — or the NTRU problem.
There are even more esoteric things than what I’ve just mentioned. In fact, when we’re talking about lattice-based cryptography, these are kind of the boring ones. One of my favorite things is that there’s this line of lattice-based papers which say, “We want to do insane stuff, we want to be crazy, and we want to be fast — let’s make a lattice-based PRF.”
Deirdre: Oh yeah.
Mark: I think they’re within a constant factor of AES when you have AES-NI hardware —
Deirdre: Really?
Mark: — or AVX2. Yeah. I can’t remember the precise constant factor. It might be something big, like five or whatever. But you can get very fast PRFs based off of very weird lattice assumptions. These are SPRING and LEAP. I don’t think anyone uses them for anything, but they use assumptions that are much farther from the boring standard lattice assumptions.
Deirdre: To cover that for our listeners: we touched on a little bit of NTRU originating in the ’90s. So let us describe specifically the NTRU assumptions — the things that are consistent with what was introduced in the ’90s — what they reduce to, in terms of the security definition and the construction reduction. And not the social construction of, well, if I can break it using a lattice attack, then…
Mark: The problem underlying NTRU — I’ve heard people call it the small decisional polynomial ratio problem. Essentially, you have two polynomials. Both are drawn from some small distribution, say some Gaussian type distribution, a discrete Gaussian, who knows. One of them you need to make sure is invertible — usually invertible mod some other prime than the prime you’re normally working with, but it’s invertible. Then you take the numerator one, the non-invertible one, and the invertible one, invert the invertible one, multiply them together, and it looks uniformly random.
That’s roughly the assumption underlying NTRU. There are some parameters to tweak — which distributions you use, and I mentioned that one of them might be invertible mod a different prime, and what different prime you choose. But that’s kind of NTRU. And what I mentioned here doesn’t really involve lattices at all. You can reduce it to a lattice problem and attack it that way, but the standard NTRU problem is about inverting polynomials and multiplying them together.
Deirdre: Okay. And then around 2005, Regev introduced — did he literally call it just LWE, like the cryptosystem, or…?
Mark: Learning with errors. So it’s the learning with errors problem, and it has a very interesting history itself. There’s this question you might ask: LWE is our leading candidate for a post-quantum assumption. You might wonder why that’s the case. And the best answer is unfortunately the most boring answer — very smart people have tried to break it and have failed.
But LWE in particular has a very funny story, in that the first person to introduce it was one of the very smart people who tried to break it and failed. LWE originates — Regev has this 2009 survey, I think, on the LWE problem that includes this point. Regev was a quantum algorithms person, and he was trying to create quantum algorithms for certain worst-case lattice problems, like the shortest vector problem.
Deirdre: Oh no, I didn’t even realize that. That’s neat. That’s very cool.
Mark: Yeah. More recently he’s kind of switched over into computational biology, but some of his more recent cryptographic work was actually a faster factoring algorithm — some optimizations to Shor. So he’s been a quantum guy for probably longer than twenty years.
He was initially looking at these worst-case problems on lattices, saying, “I want to try to find quantum algorithms for them.” And he was almost able to get it to work, if he knew how to solve one particular problem quantumly. If he could solve that one problem quantumly, he could fully solve these worst-case lattice problems, which were of independent interest at the time. The one problem he couldn’t solve was LWE.
So he said, “Okay, well, instead of saying I get this algorithm for SVP, I get a reduction from solving SVP quantumly to solving LWE.” And that’s what the paper ended up being. But LWE really came from a quantum algorithms guy not being able to solve a different problem, and that was the isolated subset he didn’t know how to do. And it’s stood up since then, so I guess it’s a decent way to find a problem.
Deirdre: Yeah. And now we have a whole lineage of problems, and narrow definitions of problems, that all nest down and reduce to different forms or slightly different variations on LWE. You have a learning with errors problem or game or whatever that reduces to SVP, the shortest vector problem — or, you know, you’ve got gap SVP, you’ve got —
Mark: Yeah. Well, it’s always gap SVP. This is something that’s important to get right, because SVP is an NP-hard problem, right? If I said that SVP reduces to solving LWE in the average case, that could imply that LWE is NP-hard, which is not true, and it’s actually not thought to be true.
So, gap SVP. Roughly, how it works: SVP is this problem where you have this high-dimensional point cloud. It’s a structured point cloud — it’s a lattice — and you’re wondering which part of this structured point cloud is the closest part to you. In low dimensions, it’s easy. You just do it by, I don’t know, looking at the thing. In high dimensions, from the curse of dimensionality, you might expect it to be much harder, and it is.
David: Do we have any intuition as to why that’s hard? I get that you sit down and it turns out no one’s come up with a good answer for it. But it just seems like it shouldn’t be hard, right?
Mark: For SVP itself, no gap, it’s just NP-hard. So what’s the intuition for why it’s hard? It’s an NP-hard problem. Why is any NP-hard problem hard? I don’t know. They all could be easy. But if any one of them was easy, all of them would be, and we think at least some of them are hard, right?
So there is a more satisfying reason for these lattice problems in particular. These lattice problems, or lattices in general, actually show up in useful scenarios. Coding theory wants to look at high-density arrangements of points that are noise tolerant, right? For standard coding theory, this is often noise tolerant in what people call the Hamming metric or pseudo-metric, where you get bit flip errors — a particular coordinate is either totally fine or totally corrupted.
Another error model you could imagine, instead of this digital error model, is an analog one, where you might have a little bit of noise in each coordinate. This is more accurate for radio communications, this type of stuff. So in this analog noise model, you might say, I still want to be able to code things to get this dense point cloud so I can get efficient radio communications, but I want to be able to efficiently decode things too. In this way, problems like SVP — more properly, the closest vector problem — have this direct application. And this was actually one of the reasons that at least some of the initial computational study of lattices was occurring: for these radio communications.
Deirdre: Yeah, I could see that.
Mark: Especially since random lattices, for a suitable definition of random, are known to have very good coding theoretic properties. It’s kind of like how random linear codes are near optimal. Random lattices, for many definitions of lattices, are near optimal for these coding theoretic properties. So if you could efficiently decode a random lattice, then you could get a very efficient analog communication system. For certain parameters, this is roughly what the LWE problem is — efficiently decoding a certain random lattice which likely has near optimal parameters for these coding theoretic purposes.
None of this is a satisfying reason to say why it’s hard. It’s sort of close to a problem that’s NP-hard, but it’s in a parameter regime where that problem is no longer NP-hard. The problem’s in Arthur-Merlin, I think. So if it was NP-hard, you would get some polynomial hierarchy collapse. Cryptography still isn’t from NP-hard problems in this setting. But then also you have this other community where, if they could solve these computational problems on lattices in this average-case setting, or in the worst-case setting, they could get these better constructions — and they haven’t been able to either.
Deirdre: One of the things that I sometimes hear referenced — and then if I talk to a lattice cryptographer, they give me a sort of “ehh” — is that we have a reduction to worst-case hardness of gap SVP for a lot of these LWE systems, which is not necessarily a complexity result that we have for some of our other cryptographic constructions that we deploy in the real world.
Mark: The answer I have to this is “ehh,” which is: famously, we do have this reduction. This is what Regev’s 2005 paper was for. It wasn’t initially a quantum reduction — it was made classical, I think, in 2009, and maybe in more generality since then. In the more efficient settings where we tend to use lattices, there have been more and more of these reductions.
The issue with these reductions — there are two big issues with them, actually. One is that if I wanted to use one of these reductions to build a cryptosystem, I would need to do two things. One, I would need to say, “Okay, now my hard problem is no longer LWE, it’s gap SVP, in the worst case.” That’s interesting, but I would now need to figure out what worst-case instances of gap SVP look like. I don’t think that’s really known.
So you might be able to do something. You could say, “Hey, to figure out how hard gap SVP is in the worst case, I’ll sample a bunch of stuff on average and see how it is in the average case.” That’s a strategy, but then you’re not using a worst-case anything.
The other, bigger issue is that the reduction is highly non-tight. I don’t know if people have worked out the parameters — I’ve seen a number of papers of people trying to work out the parameters, but there was a lot of debate over which papers did it right. There might have been some errors or whatever. I’ve seen estimates, I think, as high as maybe thirty or sixty thousand lattice dimension to get appreciable security.
Deirdre: And we’re nowhere near using that for things like Kyber or Dilithium.
Mark: No. Kyber’s dimension is like 512 to 1024. The sixty thousand dimension does actually show up sometimes in the fully homomorphic setting, but even then they try to get away from that if they can. It’s more like, if you can’t optimize certain parameters, you kind of have to have things that big. The trend there is trying to get them smaller.
Deirdre: Okay. So basically we have a thing that could be a nice security lower bound, except we don’t know how to use it to actually give us real-world security parameters that are of any relation to that mathematical lower bound.
Mark: It’s these two things. One, it’s this non-tightness that you’re mentioning. But the other is that it’s not at all clear to me, or I think to other people, that it’s easier to worst-case cryptanalyze gap SVP than it is to average-case cryptanalyze LWE. Because at some point you need somebody to say, “I have a computer, I have these algorithms, I tried running them, it took a while, and this is my estimate for how much longer it would take for bigger parameters.” This kind of explicit work trying to extract concrete parameters from these abstract algorithms.
If someone could write down, this is what the worst-case gap SVP instance looks like, and this is how long it takes to solve, then we would have something very interesting. And also if everything was tight, I should say. But that work is also — I don’t know if anybody’s looked into it. It seems unclear how to characterize the worst-case gap SVP instances that you’d be reducing from.
Deirdre: Got it. Okay. So in the ’90s we had our very early social instances of lattice cryptography. In the ’90s we’ve got NTRU, which is still kind of floating around in some form. Since the ’90s we get the introduction of LWE, in the mid-aughts. And since then we’ve gotten these other flavors of LWE, including Ring LWE and Module LWE, and we’ve seen these unstructured lattices. One of the cryptosystems that uses that is FrodoKEM.
Mark: That’s just plain LWE.
Deirdre: Okay. All right. For some reason I didn’t clock that. I forgot.
Mark: So, essentially what happens is, an LWE instance can roughly be phrased as the following. You have this integer matrix, you have a secret, you multiply them together, and you add some error. It’s worth mentioning this error should also be kept secret, so you might think of it as a static secret and an ephemeral secret. But that’s the rough shape of it.
All the algebraic structure is saying is that this integer matrix — well, matrices take N squared parameters, and that can be a big number. So can we shrink that somehow? You could say, hey, instead of being this N squared matrix thing, I want this to be a matrix that is determined by one of its rows, and then maybe some simple transformation you apply to that row. I might want it to be some sort of Toeplitz matrix, these sorts of things. The algebraic structure is all a way of saying that this matrix, instead of being fully dense, is going to be one with some interior structure.
As an example, RLWE is usually done over a cyclotomic ring of power of two. This matrix ends up being what’s called negacyclic. You have the vector in a column, and then each time you move it over you cyclically permute it, except when you go off one end you introduce a minus sign. So there is this very concrete way to describe it.
The downside is that the very concrete way to describe it can hide some security concerns. I said you introduce a minus sign. That sounds like extra work. Why do that? Why not just avoid introducing a minus sign? Everything breaks. So that might sound like a very small issue you could make that would make everything break. In the fancier math thing, it ends up making a lot more sense. Roughly, you have a polynomial, and if you don’t introduce this minus sign, the polynomial has this degree-one factor, and you can hunt everything down to this degree-one factor to get a one-dimensional instance that’s very easy to break.
Thomas: So for people who aren’t in their happy place when they hear the term “cyclotomic field”: we’re starting with Coke Zero LWE, with what’s now called FrodoKEM, right?
Deirdre: Correct, yeah.
Thomas: And we’re going to structured lattices, where instead of a uniform random lattice or whatever, we have structure inside of that matrix, right? Why did we do cyclotomics there?
Mark: It’s a good question. You could do other forms of structure. In fact, there was this NIST submission, maybe it was called Titanium, that roughly did what’s called middle product LWE. It’s its own thing. There are more esoteric assumptions, but it essentially said that we get hardness if any of these very large set of structures is fine. So in some senses maybe it was more conservative, but also — remember all the downsides of Titanium. The middle product stuff’s a lot harder to work with.
But why do we use cyclotomics there? Roughly speaking, the initial thing that was introduced was these cyclic lattices. It’s the most obvious thing to do. They had precedents in coding theory. My advisor actually, I think in 2001 — not for LWE, but for a different problem, the short integer solution problem — said we can have this cyclic structure, we can get benefits from it. But then there were these papers that said, essentially, that the cyclic structure means that when you view things in terms of polynomials, you get this degree-one factor, and everything can break. So you have to split off that degree-one factor, and then you get these cyclotomics.
What cyclotomics are is: you take the polynomial X to the N minus one, and then you factor it, and you keep the highest degree piece, very roughly. This X to the N minus one, very roughly, is the generator of this cyclic transformation. So you start with the easiest thing possible, and then you keep the biggest component of it that’s secure.
Deirdre: And the primary motivation is to take a secure cryptosystem but make the things that you’re shuttling around on the wire smaller, while reducing to the same problem?
Mark: Well, it’s not exactly reducing to the same problem. The idea is that now you only have to pass around one row or column, so you get a big size win. But now you’re working over this structured family of instances. So there are these concerns: is this structure useful for attackers? Plausibly.
RLWE — so the Ring-SIS, the short integer solution version of this, was introduced in 2001. RLWE, I think, was roughly 2011. The structure has finally helped attackers, this February maybe. I think they got a times-four speedup, and it seems kind of limited to that. So there now finally appears to be a very small gain from the structure, but it has taken a while to materialize.
It is worth mentioning that for adjacent lattice problems, the structure can help. So I mentioned you have this matrix, and you have a single column, and you apply this transformation. You can think about having this one structured block in it. Kyber does something different. Roughly, it has smaller structured blocks — say, 256 by 256 structured blocks — and then it builds the block matrix out of that, and this is module LWE.
The reason why we often prefer module LWE versus ring LWE — and I say “often” because this is mostly for public key cryptography; in fully homomorphic encryption everyone uses RLWE — the reason for public key cryptography is that in 2016 there were some improved quantum attacks against these single block instances, not of ring learning with errors. So the attacks, I think to this day, don’t really say anything for the deployed schemes. But —
Thomas: Wait, wait, wait, wait, wait, wait, wait, wait, wait. Module LWE is just LWE with block matrices?
Mark: Roughly, yeah.
Thomas: Okay.
Mark: If you hear “module” —
Thomas: Module. Module. Yeah.
Mark: But it’s roughly just that you have block matrices, and they all share the same structure.
Thomas: It’s that thing where you look up “modules” on Wikipedia and get —
Mark: No, it’s impossible. Yeah.
Thomas: Right, but the actual thing that’s going on here is it’s just block matrices.
Mark: It’s block matrices, yeah. So it’s block matrices, and then instead of fully materializing that, you only ever materialize the single rows you need, and then you need an efficient way to multiply these block matrices by a vector, and that’s where NTT stuff can show up.
Thomas: This is my thing. This was my understanding — which is now devastated by the last fifteen minutes that you two have been talking. My understanding before, because I’m an idiot, was that all of the complexity in these systems, all of the structure that was being introduced, was about something like NTT. Was just about speeding up the multiplication.
Mark: Well, that also shows up. It’s not independent. Because if I just have this dense matrix and I have a vector and I want to multiply them, that’s N squared time, right? But if I have a structured matrix, and if it’s structured in the right way — say it’s an NTT matrix — and then I have a vector here, now I can do something N log N, right? So roughly speaking, it does both: we get the compactness, because you only need the single row or column, and we also get this NTT-friendly form, so we can get some computation speedups too.
Thomas: So module LWE has become, for reasons, very salient in discussions about risk in lattice systems. But I interrupted you to say, you know, “for fuck’s sake” about modules and block matrices, right as you were going to say, “We now prefer block matrices,” or, “We now prefer module LWE.” So I would like to hear more about the thing you were originally going to say.
Mark: Yeah. So what happened is, in 2016 there were quantum attacks, I think, against ideal SVP.
Deirdre: Yeah, that rings a bell.
Mark: I mentioned before that worst-case SVP reduces to LWE. So you might think, oh, these quantum attacks against SVP, that’s concerning for LWE. Well, not really, because the reduction goes in the wrong way. To solve LWE, you have to reduce to what’s called a rank-two instance — kind of a block structure with four squares instead of one, right? You have to reduce to a rank-two instance of ideal SVP, and the quantum attacks don’t help in that setting.
So in 2016, these quantum attacks showed up in a relevant but adjacent context. People were like, “Hey, it’s not that much worse to just use this block structure, and then we’re kind of farther away from the issue.” And things have been fine since then — but also for RLWE-based schemes, things have been fine as well. As I mentioned, fully homomorphic encryption still uses RLWE everywhere. It uses RLWE with insanely more speculative parameter sets. When I mentioned there was this times-four speedup from the algebraic structure that appeared, you get much bigger ones in the FHE setting. I think there was maybe a fifteen-bit speedup — I don’t remember, I’d have to check again. But that’s because FHE people do much, much more speculative things to try to get things to be more efficient.
Deirdre: And this leads into — there’s the boring crypto stuff, which is literally the primitives that are basically public key encryption that you twiddle with an FO transform and turn into something that looks like key exchange, but it’s not, it’s a KEM. And then your regular schmegular signatures, to give you unforgeability or whatever you want to do. But things that get more complicated than that have to go into settings that have a little bit more exotic assumptions.
Mark: I would actually say lattice-based signatures do tend to be a little bit harder than fully homomorphic encryption to get right.
Deirdre: Oh, okay.
Mark: It’s a very funny sentence, but —
Deirdre: Tell me why, because that notion wouldn’t have even entered my head.
Mark: There are roughly two families of lattice-based signatures. One of them I’m more familiar with. Roughly what they do is they say, okay, lattices look a little bit like Diffie-Hellman. If you think of it as A times S plus E, and you just ignore the error — A times S, it’s like a one-sided group, like Diffie-Hellman, right? So you can do Diffie-Hellman type things. In fact, Kyber and things like this can be thought of as a Diffie-Hellman type thing that adjusts for this noise being here.
If you’re doing Diffie-Hellman type things for encryption, you could say, hey, for signatures I also want to do standard things. So maybe I’ll do Schnorr signatures or something like that.
Deirdre: Oh.
Mark: A lot of people try to do this, and all of them break, because this noise ends up being much more devastating. In particular, I mentioned before that the noise you can think of as an ephemeral part of the secret. The noise is security sensitive. So lattice-based signatures, until they started to be done properly, would often leak this — attacks that would allow an attacker to recover part of the noise. And if you recover part of the noise, you can almost always break the scheme pretty easily.
Thomas: Can I just ask real quick what that attack looks like? Because this is one of the rare instances where I have a bit of an intuition for what that would be. I can see immediately why leaking any of the error bits in an LWE computation is bad — the whole reason why this system isn’t just Gaussian elimination is the error, right? So, obviously bad to leak it. But what does that attack look like?
Mark: I’m pretty sure they ended up being machine learning-ish type attacks, where the idea is that if done improperly, you get part of it. Lattices, as I mentioned, are these point clouds, and you might imagine for these points this initial block, and then everything is a translate of that, right? The inside of that initial block you might call the fundamental parallelepiped — or at least lattice-based cryptographers do. So the attacks roughly would say that we can identify leakage somewhere within this fundamental parallelepiped, and then maybe some sort of gradient descent-ish type attack on top of this, with enough signatures to recover the actual secret, and then from there you win. It’s something along these lines.
Thomas: But it’s much more interesting than the hidden number problem, then, right? It’s not like we have a bit of bias and then I can literally just do a BKZ or something like that.
Mark: I think there is this kind of averaging step you have to do. I don’t think you just create a lattice, and I think you do need many signature samples.
Deirdre: Oh, so you do need one key and then —
Mark: I don’t know if there are attacks with a single signature. It’s not a huge amount you need. I think there are papers I’ve seen that have been on the order of five hundred. But these are devastating attacks — you need to get this part right.
That’s why, if you look at stuff like Dilithium, Dilithium describes itself as Fiat-Shamir with aborts. Fiat-Shamir is part of creating the Schnorr signature. The aborts is to say that, hey, if we would leak part of this error, we try again until we don’t leak it.
Deirdre: Oh, that’s fascinating, that that’s where that comes from.
Thomas: Hold on, this is getting more — so what’s happening when we’re doing the Fiat-Shamir in the Schnorr signature that’s causing us to leak the error? Because I don’t do signature stuff.
Mark: I’m pretty sure it’s that the errors get too large. The rejection conditions in Dilithium are bounding the size of the error. I think there are two rejection conditions, actually, but there was this paper a couple years ago that said you only really need one of them, but that one is load-bearing. Although this wasn’t for Dilithium specifically, it was for Fiat-Shamir with aborts type schemes.
Thomas: Nyet. Nyet. That’s my contribution.
Deirdre: Okay. So in more exotic settings like FHE, why do you have to get more exotic, why are your parameters slightly different than the things that we might see in Kyber and Dilithium, and why are your assumptions more exotic as well?
Mark: There are a number of reasons. The first thing is, I said FHE always uses ring learning with errors, not module. The reason for this is because of something people often call seed compression, where an RLWE ciphertext has two components, A and B, and the A part is uniformly random. So you can just store a small seed there, and you can use an XOF to expand it. For module LWE, you pick up more of these components in the front, so you would need more of them — you could generate them all from a single seed. So in this setting where you can expand things from seeds, it doesn’t really matter.
The issue is that this expanding-from-seeds thing does not survive any homomorphic operations. Even something as simple as adding together two ciphertexts — well, now you have an XOF of seed one plus an XOF of seed two. You can’t find a seed that really expands to that target. So you now have to store the full two polynomials here, and in the module LWE setting you have to store even more. So for FHE, you end up taking this big bandwidth size hit if you end up using module LWE versus RLWE.
There are other more exotic things people do as well. And it’s worth mentioning, when I say “for FHE,” there are two broad classes of FHE schemes. There’s what’s often called the TFHE-based schemes, and then generally CKKS, BGV, BFV — they’re all tensor product multiplication schemes. For this first class, you get a lot more flexibility. You can do things much closer to public key type crypto. But the second class is the one that I’m describing, that has less flexibility.
In particular, for the second class, you get these weird assumptions about the error. In public key cryptography, the error vector you can choose to be from any distribution you like, as long as it’s not too concentrated. If it’s too concentrated, there are these attacks from 2011, the Arora-Ge attacks, that start being applicable and concerning. But even things like — often people do Gaussian type noise with standard deviation three. That’s not too small, right? Gaussians are a little bit hard to generate, especially if you need to have a masked implementation of the generator. So instead you can just sum up a bunch of bits. It’s a binomial random variable. If you center it, it looks kind of Gaussian, and it’s good enough for encryption.
The issue with this is that there’s this one component of FHE that’s very key, where a certain parameter scales with the sum of the absolute values of all these coefficients. So instead, FHE likes to have this noise be sparse ternary noise. They want to make it as small as possible, which is a much more aggressive assumption.
In particular, the error distribution and the secret distribution for LWE, they tend to be fine with anything. We have these proofs that as long as they have enough entropy — there’s this thing called entropic LWE. The secret distribution and error distribution can be the same, and then as long as the error distribution has enough entropy, things are mostly fine. But the worst-case to average-case reductions aren’t true in this setting. So even though we don’t use them for any choice of parameters, moving to settings where the worst-case to average-case reductions are no longer true is still often seen as something that’s very concerning.
Deirdre: Because you’re never quite sure how your parameters may break down, and at least you have that as a backstop kind of deal?
Mark: It’s not like that. It’s more that if you’re in a regime where the worst-case to average-case reductions hold, then you have this understanding that it’s hard for there to be atypical structure there that wouldn’t also help in gap SVP. It might help with much smaller gap SVP instances, but an algorithm here is concretely an algorithm there — with the caveat of this tightness being bad. But if you start falling outside of this worst-case to average-case setting, then there could start being non-trivial attacks that wouldn’t also imply an attack for gap SVP.
So in FHE, the secret distribution can often end up getting much weirder, with much more aggressive assumptions. I’ve seen papers that suggest Hamming weight 32 and Hamming weight 64 secret keys, which are very small numbers. Although I don’t think there have been attacks on these schemes.
There’s also the ciphertext modulus, which can get very large in FHE. For Kyber, the ciphertext modulus is fourteen bits. It’s relatively small. In FHE — at least for these tensor product-based schemes I was focusing on — each time you do a multiplication, you have to shave off fifty bits from your ciphertext modulus, very roughly. So if you have this complicated circuit you need to compute, say a bootstrapping circuit, then you might need to support eight-hundred-bit or fifteen-hundred-bit moduli. Things that are much larger than the fourteen bits that Kyber uses.
Deirdre: Yeah. And we need some big limb arithmetic, and all of this has to be prime?
Mark: No, it doesn’t have to be prime. One of the things about all of these LWE-based schemes is that the number theoretic structure of the moduli does not really matter at all.
Deirdre: Oh, good.
Mark: As an example, I think Kyber is prime, but it doesn’t have to be. Saber was another NIST finalist and it’s two to the thirty-two, right? So it doesn’t really matter. For FHE, they take a bunch of word-sized primes and multiply them together — so they do CRT-based things — but you could do plenty of other things. It doesn’t really matter.
Deirdre: Cool. Wow. Okay. So we’ve basically done a whole tour of the history of lattice-based cryptography, including some of the whiz-bang stuff that, depending on your field, you may see — FHE stuff, or things that use FHE constructions under the hood, such as blind —
Mark: The things that are being deployed practically are generally not full FHE. I think Apple’s caller ID uses homomorphisms of lattices. So it’s a very weak homomorphic lattice-based thing. And I think Google might have something as well, but I forget.
Deirdre: I wouldn’t be surprised. Those are the areas where I expect more things to trickle out, because things that we might have used blinded commitments for, or other things using elliptic curves, are basically right out if you’re trying to deploy anything that might be quantum resilient into the future. And then you start reaching for lattice things that generally might have something FHE-ish under the hood.
You’re just not doing a full, fully homomorphic computation with a bunch of other fancy stuff. But under the hood, if you’re trying to do anything with homomorphic commitments, that’s secretly homomorphic reductions underneath it, and I expect more of those to show up.
Mark: It’s also worth mentioning it’s not purely a quantum, pre-quantum thing. A lot of FHE applications actually don’t particularly care about the quantum security aspect of things. Even in these relatively simple settings, a lot of these things tend to be very fast. It’s the only real cryptography we have that I’ve seen some people describe as quasi-linear time, where the compute almost scales linearly with just the size of the things you’re operating on.
Deirdre: Yeah. And you could make an argument that, in terms of trying to find quantum-resistant replacements for the boring crypto that’s deployed all over the place — key agreement, or the equivalent of key agreement, and signatures — that’s kind of why they win. Because they’re very fast, and they’re quantum-resistant, and they generally are small enough to fit in a lot of places. And a lot of the other cryptographic problem lineages just don’t seem to fit for one reason or another. But there are other problems where there just isn’t an equivalent, like the fully homomorphic stuff.
Thomas: When you put quantum into that mix, it’s kind of obvious why it’s so attractive right now. But there’s a reason that we ended up using curves and not NTRU in the ’90s, right? I don’t know the answer to this question. Part of it is that we didn’t care about quantum then, but —
David: I mean, Koblitz and Miller was like late ’80s. Curves got almost a ten-year head start.
Mark: NTRU was mid-‘90s, so it was a little bit later. It had some patent encumbrances. Elliptic curves did as well, but the NTRU ones would have expired later in the future, I should say.
It probably also didn’t help that the NTRU-based signatures were broken pretty quickly. I think they were broken before 2000, so that would make NTRU encryption look a lot more suspect. It seems mostly fine, but there have been non-trivial attacks against NTRU that are not possible against RLWE. So there are some concerns to have about NTRU.
Thomas: Sure. Also, the vibe I have is that LWE has a clearer theoretical basis for it. LWE is a cleaner abstraction, right? We had reasons to trust curves more than we had for NTRU or whatever now happens to be considered lattice. But there are practical reasons, I assume, right? Because nobody was thinking this carefully. I was there in 1998.
Mark: Yeah, so the main things that I would say for practical reasons — or at least why lattices are more appealing now — lattices are a bunch of matrix-vector arithmetic, or rephrasing in terms of polynomials. So with vectorized multipliers and vectorized adders, they take advantage of vectorization very well. That probably wasn’t as relevant in the ’90s. Lattices are bigger, so that’s a clear downside. Those are the big downsides that I know of. I don’t know how fast lattices are compared to elliptic curves if you remove AVX instructions.
Deirdre: They’re faster. At least the Kyber LWE stuff — you don’t even need the speedup. Maybe you would speed up your hash function, but that’s independent of the lattice math.
Mark: On what architectures? Lattices auto-vectorize relatively straightforwardly in many settings as well. So this is assuming no AVX.
Deirdre: Yeah, even naive implementations with no vectorization are very fast. You might have to do some tricks. If you do Kyber-512 versus, say, P-256 or X25519 — the X25519 might go faster, but that’s had some good optimization tricks added onto it for a while. It’s not difficult to do a very fast, naive, non-vectorized, no-assembly, no-intrinsics LWE Kyber.
Thomas: Sure. And we were also fully curve-committed before Curve25519 happens. We’re already on the P curves.
Mark: I don’t remember the initial parameter sizes for NTRU. NTRU wasn’t initially phrased as a lattice-based cryptosystem, but quickly it was determined you could reduce it to a lattice problem and then attack the lattice problem. Algorithms for attacking lattice problems did have substantial advances between 2000 and maybe 2018, somewhere around there. So the security story for NTRU probably didn’t look that great as those advances were happening. I don’t know what parameters they initially chose, but if they chose parameters aggressively enough, they probably would have been broken, even if current parameters are probably fine.
Deirdre: I’m seeing some sample params. Yeah, go ahead.
David: The timing just doesn’t work out. When the NIST curves were being standardized in like ‘98, ‘99, and you have NTRU coming out in like ‘96 — that’s just not going to fucking happen on that timeline, no matter how good it was. To say nothing of the fact that we couldn’t do signatures with it. And elliptic curves were like the hottest thing in the world because of Wiles at the time, too.
Thomas: Which — again, I could do a full hour just on attacks on naive Schnorr lattice signatures, because those attacks are really neat. I’m going to short-circuit this a little bit and just say Streamlined NTRU Prime. So sNTRUp versus original NTRU. Where are we?
Mark: How to say this? I would describe sNTRUp the following way, but I haven’t looked at the original NTRU scheme as much. And what I’m saying here, this story also was replicated in LWE land.
Roughly, there are three ways to build lattice-based KEMs. You start with your pseudorandom component. It could be the NTRU assumption, it could be the LWE assumption. That pseudorandom component has this secret part. It’s not good for anything public key. The initial thing people did, at least in LWE, is you would take a randomized subset sum of it, and then the random coefficients from the subset sum, you would have that be another secret. And then this is roughly the two-secrets sort of thing. This you might call a leftover hash lemma-based construction, because for its security you need to appeal to something called the leftover hash lemma.
The other thing you can do — at least in LWE land, I don’t know if this works for NTRU — is, instead of doing this randomized subset sum that needs these leftover hash lemma type constructions, whose downside is that they don’t obtain this stronger form of security, statistical indistinguishability… but applying this step makes this randomized sum look uniform again. This single part of the reduction is statistically secure, so the parameters chosen for it are maybe a little bit larger than you might want, without positively impacting the total end security that you get. So instead of doing that, you can do this other second application of the LWE assumption, to get something that uses slightly smaller parameters.
Both of these create a random pad that’s agreed to, up to these lower-order errors, and you can add messages to it, do a one-time pad type thing. The final thing you could do is just say, “Hey, I just want to build a KEM. I don’t actually care about messages.” So you could have this random pad, and just apply some shared function to it that will agree on a key. This third thing is closest to what sNTRUp does.
Although from NTRU you can also build public key encryption directly, so you could do these other constructions as well — at least the variant of the leftover hash lemma thing, I think. There initially were these LWE-based things that looked closer to sNTRUp, that didn’t have this explicit message and followed this paradigm, but they ended up not being as popular in the NIST competition. I think NewHope initially was of this form, but they changed it, and I don’t think any finalists ended up being of this form. For LWE in particular, it’s hard to make the resulting KEM CCA secure. For NTRU, it ends up being easier to do. So you can get sNTRUp CCA secure based off of taking this NTRU assumption — I think they don’t do this leftover hash lemma type thing, and you don’t include this message. You apply this decoding stuff to get a shared quantity, and it has a more straightforward path to CCA security.
Thomas: So the subtext of that, obviously, if you’re a nerd, is that in the IETF and in NIST and all that, there’s basically a drama between module LWE and Kyber, and sNTRUp, right? sNTRUp was implemented in SSH originally; NewHope, which is RLWE I guess, was in browsers before that. There are key implementations of all these things, and then module LWE is the standard now, right? And sNTRUp is — I don’t know what you would call it, but it’s the other system that people think about or advocate for. And so the big debate, especially among people who don’t do this professionally, is: are we taking a huge risk flyer on using module LWE as opposed to using something like Streamlined NTRU Prime?
Mark: I’m biased, being a fully homomorphic encryption person. NTRU is not used in fully homomorphic encryption anymore. It is for these TFHE type schemes, but in 2017 there was a non-trivial attack that applies only to NTRU that breaks it in every parameter regime I care about. So maybe it’s more conservative, but that’s only from a certain definition of the word “conservative.” In applications I care about, I can no longer use NTRU, even though it has appealing computational properties. It’s explicitly insecure.
Deirdre: But non-FHE, for just regular public key encryption?
Mark: Well, the thing is, non-FHE, this attack did not get down further, right? But it’s this type of thing where — let’s say McEliece. People like McEliece. Some people advocate for McEliece, right? And one of the justifications people give is that it showed up in 1978 and it’s been secure ever since. But in the last few years, that’s not been true. There have been these series of papers that have said, “Hey, there’s maybe this structure in McEliece that can be exploited.” I’m not sure of the current status of the papers, but at least the abstracts are getting pretty concerning, right?
So whenever there’s additional structure showing up, it’s something that gets a little bit concerning. Arguably, this happened for NTRU in 2017 with these additional attacks on FHE. It also arguably did happen for RLWE with these quantum attacks on this adjacent assumption — ideal SVP, but not the rank-two version that you would need to break RLWE. So there are these things where, whenever I see one of these attacks on something adjacent, it’s like, well, can it move over? Is it something to be worried about? So I would be a little bit worried about RLWE and a little bit worried about NTRU, for both of those reasons.
Thomas: That’s literally the logic of SafeCurves, right? It’s like, here are adjacent attacks on specific curve structures that only matter in specific regimes, ergo never use these curves. It seems like that’s essentially the same argument here.
Deirdre: I mean, it is, in this the year of our Lord 2026. But Mark, are you trying to hint towards, “Yeah, I don’t know if I want to use those assumptions anymore, because what if they keep moving? What if those attacks keep getting better?”
Mark: Mostly that. Well, in my day-to-day job I just explicitly can’t use NTRU. And a lot of this is kind of vibes-based, in the sense that if you look at —
Deirdre: A lot of cryptography is vibes-based, honestly.
David: That’s why Claude’s so good at it.
Mark: — where we currently think it’s safe to use NTRU versus not NTRU: I think it’s if you have this ciphertext modulus Q, and it’s Q being roughly less than one over a hundred times N to the three point two something. Or maybe — it’s some number, and arbitrary numbers appear plenty of places. The best lattice attacks have arbitrary numbers in the exponent. So it’s not like arbitrary numbers should totally disqualify a scheme from being used. But then also, I would feel more confident if there was some clean number, and being like, “Oh, an attack can’t go below this clean number.”
David: I want to just compare and contrast a little bit back with elliptic curves, in terms of timelines. You have Koblitz and Miller being like, “Let’s do elliptic curve Diffie-Hellman,” in ‘87.
Deirdre: 1985. I always thought it was ‘85, but —
David: — when they wrote the paper, and ‘87 when it was published, right? And then NIST standardizes in ‘99, 2000, meaning there was some sort of lead-up to that.
Now, we’re much, much better nowadays at writing cryptographic standards than we were then, despite the best efforts of the NSA. But if you go back and look at what were all the problems with cryptography in the 2000s and 2010s, they were by and large not with the primitives of that era. They were: these standards are all written poorly, and some of these protocols were dumb, or the way in which we chained AES together was a bad way to chain AES. But the primitives more or less held. You look at P-256, which we’re still using today — it’s not quantum secure, but that takes ten to fifteen years to get standardized, and then another ten years for adoption. Then look at lattice-based cryptography starting in the ’90s, ten years later looking at Ring LWE, and twenty fucking years after that is where we’re at now, right?
I’m not a primitives person. I’m not picking parameters for these things. My job in the last basically decade plus has been to listen to people who work on primitives, then figure out how to use them in the real world and whether they’re being used correctly. And the answer is, people have been looking at this stuff for longer than they had been looking at elliptic curves at the time that elliptic curves were deployed. These are a safer thing to move to.
And if you are familiar with Diffie-Hellman and cyclic group-based cryptography, I encourage you to go to your preferred AI chatbot and say, “I understand Diffie-Hellman. Explain to me enough algebra to understand Kyber.” It will do it very well. I did it earlier today.
Thomas: Before this?
David: I did it earlier today, because, again, actually understanding all of the details of the cryptosystems is not relevant for day-to-day use a lot of the time.
Thomas: I’m just waiting for the IETF post where they say, “David Adrian, who just learned how this works five minutes before shooting this —”
David: Yes. Because it turns out that part of this is evaluating experts on various things and making decisions, and that’s the way it goes. And I think we’re actually at a very conservative point of using post-quantum cryptography. Post-quantum cryptography is a type of math. Lattice cryptography is a type of math.
Mark: Something that’s not appreciated often by people who are concerned about lattices — I’ve seen a lot of arguments that I have a hard time following. People have mentioned Dual EC was bad, so we should be concerned about ML-KEM.
Deirdre: We knew Dual EC was bad, though. When they first suggested it —
Mark: This is true. The potential for a backdoor was known, and then also, if default parameters weren’t published, I don’t know if Dual EC had any issues. I think the issue was both the potential for a backdoor and default parameters being published that were the backdoor parameters.
But even ignoring that: for lattices, very early on — I think it was in Lattice Cryptography for the Internet — there’s this section that says, “Hey, backdoors are bad. This particular component of the scheme could be a backdoor. We’re going to throw away some efficiency to make sure that it can’t be leveraged.” And every scheme since has always done this. Lattice-based cryptographers also want to build secure systems, and it shows up in the constructions.
And not only that, the concerns over the NSA potentially backdooring or subverting cryptography with lattices are a little bit confusing, just because it seems like everyone else is moving over to lattices too. Europe for the most part has also chosen lattice-based schemes. Not always the same schemes — the BSI, the German InfoSec government group, have chosen FrodoKEM, I think.
The Chinese have not yet announced what schemes they’re going to be moving over to. They’re rather early in their process. I think a couple of weeks ago they had the final submission period for their schemes close down. But the comments that you can see from certain Chinese cryptographers make it seem like they’re going to be going for lattice-based schemes. They’re going to be lattice-based schemes with Chinese characteristics.
For Chinese lattice-based schemes, there was a NIST submission, LAC, which is maybe good to look at. It was doing something roughly Kyber-like, except it chose a very small modulus — eight bits instead of fourteen bits — and it tried to argue that by doing some error correction argument, you could get things to work. It got broken. The reason why it got broken is somewhat technical, but roughly the Chinese response to it appears to be: we’re not going to do LAC again, it got broken; instead we’re going to switch to an unstructured lattice-based thing. Maybe because they’re worried about the algebraic structure, but also because the algebraic structure is specifically what made this error correction component of LAC break. Another way to fix that is just to use a larger modulus like Kyber does. So it might be either one — it’s hard to tell.
Thomas: But in the BSI case, and I guess in the Chinese case if they do unstructured lattices — if you’re using FrodoKEM, there really is an argument there that that’s more conservative.
Mark: FrodoKEM exactly, they have — what is it? I think it’s SCloud+. It’s really more like a FrodoKEM version of the LAC scheme. How would you describe this? In lattice-based schemes you have this error, and when you decrypt you get the message plus the error back, and you have to remove the error. In almost every scheme, you just round off the low-order bits. That’s where the error was. You’re fine. But you could say, “Hey, handling errors, that’s what error-correcting codes do. I can do something fancier to be able to tolerate more error, and then choose smaller parameters.” This is roughly what LAC did, and it is roughly what SCloud+ does, over FrodoKEM.
Thomas: Okay. But if you collapse it down to just the German case — the FrodoKEM decision there really is more conservative than the Kyber thing.
Mark: It depends on what you mean by conservative. If I wanted to make AES more conservative, would I design a new block cipher, or would I say AES with a thousand rounds, right? Well, the new block cipher might be good, but AES with a thousand rounds — AES would have to be really weak before a thousand rounds is broken, right? So “conservative” usually in cryptography means within a certain efficiency budget, right? So for FrodoKEM: is it more conservative, or is doing Kyber with module rank 15 more conservative? It’s not for me to say. If you’re saying the downside for FrodoKEM is the large ciphertext, and I have this large ciphertext budget for being conservative, is it better to use an LWE-based scheme versus module LWE? I just don’t know.
Thomas: Oh, that’s good. That’s a really good way of framing it. That makes sense.
David: And I will say: if you are a country and you are trying to get me to care about your cryptographic standard, you need to have at least twice the GDP of California for me to start reading your standard. We’re just going to set that as the bar. Looking at you, Germany.
Deirdre: I wanted to also shout out South Korea, which also did a post-quantum crypto competition, and they also selected lattice-based KEMs and signatures, I think. I think there was SMAUG and another one. They’re slightly different — they have slightly other assumptions — but it was kind of like looking at what came out of the NIST competition and saying, “Ooh, we can make some tweaks to some of these things and learn some stuff.” We’ll see if they get implemented and deployed anywhere.
Mark: There are many different choices that you can make with lattices. Even in this competition, of the final three lattice schemes, you really could have chosen most of them and gotten something mildly different and probably fine. But it does seem like essentially every country I’ve seen that runs a standardization — or at least every appreciably large country that runs a standardization — is converging on lattice-based things.
And I’m sure this has some downsides. If lattices end up being weak, that’s bad for everyone. But also, for this argument that the NSA is trying to standardize weak cryptography: okay, well, why is China going along with it? It makes it a little bit more confusing of an argument.
Thomas: Although the freak argument online is just that lattices are fine, modules are the problem.
Mark: Yeah, but in that case, if the NSA is saying, “Hey, China is doing unstructured lattices and we’re going to do modules,” it seems like they’re intentionally doing badly in that geopolitical fight, you know?
Deirdre: I’d be remiss not to bring up Falcon — the future FN-DSA — which we’re totally going to get a draft standard for any day now out of the Department of Commerce. Do you have anything to comment on these floating point-based schemes?
Mark: I’m uncomfortable with it. I don’t know. It’s really small signatures, that’s great. I’m sure some people will do it right. It feels like something that’s very easy to get wrong. But maybe I’m pessimistic.
Deirdre: You’re not the only one that’s feeling a little something about implementing Falcon securely.
David: Floating point numbers aren’t real. They can’t hurt you.
Deirdre: I mean, they can hurt me, in secure implementations of my cryptographic software.
Mark: Wait, how do you even handle constant-time Falcon with subnormals?
Deirdre: That’s a good question.
David: You don’t. It was just DOA. There is maybe one person in the world that understands how to handle constant-time floating point, and it’s not — nobody else understands what they’re saying, or will be able to duplicate it.
Deirdre: Yep. Exactly that. You literally clone one person and stick ‘em in your lab.
Thomas: So what have we learned today? I’ve learned that Oded Regev, who is the godfather of all lattice cryptography, is now a computational biologist. He saw this coming and exited the field.
Mark: I have no clue why he switched over. And it’s not purely computational biology. He actually writes mathematical lattices papers as well — he had a paper that got into the Annals of Mathematics recently, one of the best math journals in the world. So he still writes lattices papers, and he still does quantum papers, and computational biology.
David: That makes a lot of sense. He’s just excluded us, the terrible group of people. Like, I don’t want to be at these NIST things.
Thomas: My son is a grad student and an aspiring computational biologist, so this gives me a thing to talk about with my son. You’ve healed my family.
Deirdre: I’ve learned that you really, really need to get a quantum algorithmicist to build your cryptography, because that’s going to stand the test of at least twenty years where other people fail. And you just have to catch them before they turn into a computational biologist.
David: And a couple hours ago I learned how Kyber works. So, you know, we all learned something today.
Deirdre: Yay!
Thomas: I also think everybody should go on ChatGPT and just ask it to spell out an attack on a naive LWE Schnorr signature. Just the blueprint, or the schematic, of that attack is pretty neat.
Deirdre: Well, we want to talk a little bit more about that in a second. I want to give a shout-out to Alfred Menezes, who is one of the OGs of elliptic curve cryptography, and has been cranking out a whole series of lectures free on YouTube on his YouTube channel — we’ll put the link in the notes — on post-quantum cryptography, on a whole bunch of cryptography, free and available. It’s amazing, and it’s pretty cool. So if you want to learn how Kyber works and how a lot of these lattice crypto schemes work, that’s a good place to learn, if you don’t want to turn to your local large language model to do it. Cool. Anything else?
Mark: Also worth mentioning: Alfred Menezes — the paper showing that Regev’s reduction is highly non-tight, so it could never really possibly be useful for setting parameters, was one of his, with Koblitz.
Deirdre: I didn’t know that! Oh my gosh. I’m learning so many things. Oh my goodness. I have to read that one now. All right. Is there anything else, Mark, that you wanted to bring up before we wrap?
Mark: I don’t think so. People seem very concerned that lattices might break in surprising ways, and I can’t unfortunately guarantee anything about the future in any context. But if you want to see a lot of examples of lattices breaking in surprising ways, you can look twenty or thirty years ago, because there were many very funny ones.
Deirdre: Yeah. That’s a good place to do it. Okay.
David: It’s a little funny that when we were an audio-only podcast, we did a very visual discussion of lattices, and now that we are a video podcast, we did an entirely audio discussion of lattices, where some visuals probably would’ve helped a lot.
Deirdre: No, you were doing a great job with the linear algebra, actually.
Thomas: This is the most fun that Deirdre has had on one of these episodes where we weren’t just talking about isogenies.
Deirdre: Yeah. Well — and that’s another one, where you’re like, “Oh, lattices don’t just show up in lattice-based cryptography. They show up in a bunch of cryptography, such as isogeny-based cryptography, like SQIsign.”
Mark: This is something like trying to define what lattice-based cryptography is. It was something I was thinking about today, because it’s like, well, is cryptography based on lattices? Any elliptic curve over the complex numbers is a lattice — a rank-two lattice. Is elliptic curve cryptography lattice-based cryptography? No, that’s very stupid.
Thomas: This is why you can’t look anything up on Wikipedia, because everything on Wikipedia is written that generally. You’re the problem.
Mark: For the record, if anybody has a good definition of lattice-based cryptography, I’d be very interested in hearing it. I’ve been trying to think through it, and I keep running into these weird cases where it’s like: oh, if Schnorr’s factoring algorithm worked out, would RSA be lattice-based, because the best attacks are lattice attacks? Are elliptic curves lattice-based, because elliptic curves are lattices? There’s got to be some definition somewhere, but I haven’t found something that makes sense to me yet, besides it being this socially defined research area.
Deirdre: You might need to write that blog post. Cool. Thank you. Thank you, Mark.
Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. You can find the podcast online at scwpod, and the hosts online at @durumcrustulum, @tqbf, and @dadrian. He’s got the new handle.
You can buy merch online at https://merch.securitycryptographywhatever.com. If you like the pod, give us a five-star review wherever you rate your favorite podcast. Thanks again to Teleport, who is sponsoring our event in Las Vegas between Black Hat and DEF CON. There are links on our website about trying to find us in the liminal space between Black Hat and DEF CON in Vegas this year, in a couple of weeks.
Thank you for listening. All right, let’s hit the button.
Thomas: Awesome.
