An Odyssey of Lattice Cryptography with Mark Schultz-Wu

Okay, uh, teleport. Teleport ad read Uh, SCW Pod is sponsored by Teleport you should probably introduce us first still Wait. Oh, oh, we're doing the ad read during the podcast. Yes.

it. Yes. Got it. Okay and then we're gonna talk about Teleport, who's sponsoring our live event.

Well, Great. our happy hour at… I'm just gonna talk about it now. We're doing a happy hour again at 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. Um, and if you don't know what Teleport is, you probably don't have SSH.

Um, but we're very happy that they're sponsoring, and we can attest that Thomas is a Teleport user We use Teleport everywhere at Fly. Uh, we love Teleport very much. Uh, 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 Awesome I'd like to say this is Security Cryptography Whatever, and my name is David I'm Deirdre comments And today we're and we cryptog- We're talking about lattice cryptography on this very professional podcast with our special Yes Schultz. Woo, Mark, how are you? Hi. Yeah, I'm Mark Thanks for being here.

Um, Yeah. this, having me this is like lattices redux because one of our very first episodes, we talked to Chris Peikert 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 vi- uh, listeners were 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 the stuff that is the area of lattices and post-quantum cryptography, especially, privacy 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 f- 40 years of lattice cryptography? So it, it's worth clarifying up front, I am a lattice cryptographer.

uh, what was this? I think I graduated 2024. I worked with Daniele Micciancio. I was working on fully homomorphic Uh, although my So I do have some background in lattice-based KEMs, but my publications, with the exception of like one, which was talking about the of lattice-based, uh, uh, public key encryption at Yeah um, was, uh, more on the fully homomorphic encryption side Got it.

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. Um, so computation and, uh, bandwidth. Yep i-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 have to increase the dimension as well.

So kind of, you can think about like two parameters that like counteract with each other and keep getting bigger and bigger, Yeah then everything gets big, and then that's how you can get like, uh, you, uh, you get FHE papers that talk about twenty gigabyte keys, and it's like, eh, it's like Yep the sma- 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 three gigs or whatever, but it's very far from the public key thing Gosh.

Um, and I wanna get back to that when we kind of reach… We, we kind of start at the, 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, 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, or anything more complicated than that, that are FHE-like, uh, get scary.

Anyway, so thomas gets in anywhere." So it's kind of promise. Yeah, I mean, I have a specific thing here, right? Which is, uh, 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 because I don't know what I'm talking about, 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 and on for what particular applications. The NTRU cryptosystems, both of them, um, were introduced in the mid-'90s, and the NTRU cryptosystems that we see in, in, you know, these days, they're very similar to what was around in the '90s.

Like, uh, I don't wanna say exactly the same, but at least for NTRU, I should say NTRU encryption, it's, there's a lot of similarities there. Um, NTRU 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, 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 bef - uh, after fully homomorphic encryption, but it was remarkably close, where, uh, which is kind of wild to think about. You know, you would think FHE is a much harder problem. Lattice-based signatures, uh, 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. 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 Intrue and LWE or Intrue and like the f- like NewHope or somewhat that, right? Yeah and like the P curves in curve25519, right? Like everyone's fami- 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, uh, 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, um, which, uh, was in twenty eighteen. Um, when I say substantial improvement here, it's worth mentioning lattice-based attacks usually separate into two components.

There's one which is phrasing the problem as a lattice, and then the other's the other, which is solving the lattice problem. I say the substantial improvements thing here, I mean the second part, the solving the lattice problem. Hmm. There have been some iterations on the, uh, improving the phrasing thing as a lattice problem.

Uh, if you're familiar with the MAT solv attack, this is kind of in its first one difficult thing with lattice-based cryptography, which I was actually struggling with a bit today, I was asking some people and getting, uh, not that great of responses, is that it's really kind of a socially defined field in a certain sense. What do you mean? might - Yeah, so you might say, "Okay, lattice-based cryptography, what does that mean?" Well, a, a very easy answer would be it's, well, it's cryptography based on lattices.

Unfortunately, this isn't true at Yeah. Um, so as an example, the NTRU paper, the first NTRU, uh, preprint, uh, the term lattice appears in it never. Uh, 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.

I mean, okay, I get that. I get that yeah, It like, it like reduces to lattices or like can be rewritten as a lattice 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, to 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, uh, factoring, you like sort of do, but also, like, you can break RSA without breaking factoring by breaking modular disc - uh, what's called modular, uh, uh, p-eth polynomial roots.

Yeah that does not actually, uh, you do not need to break factoring to break RSA, So i-it's like, uh, naming's kind of all over the Yeah Um, in general, lattice-based schemes do get broken by lattice-based attacks, um, and that's, I'm pretty sure that's how the naming for NTRU, uh, kind of got decided. I see 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 nineteen seventy-eight 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 two thousands 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 s- uh, reducing problems to solving computational problems on lattices. But Like, other than in true, check me on this, right? Other than in true, the, the, the, 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 basically L- LWE problem yes and no.

So, uh, the, the popular ones these days are, uh, I'd say that there's two big counter examples to this, or maybe three. So as an example, one thing that you might say is lattices the only way we can get FHE. 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 twenty-tens.

Um, it kind of looks more like a number theoretic problem, like something closer to RSA. Uh, 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. Uh, and Anton Joux also has this cryptosystem he called the Mersenne prime cryptosystem. I think it was somewhere around twenty fifteen.

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, 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 everything in terms of quadratic forms, and now we're gonna do everything in terms of quadratic forms."

Which, uh, mathematically, quadratic forms and lattices are kind of equivalent, you know. Uh, so it's, it's still kind of lattice-based, but kind of 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, um, or an algebraically structured variant of it, or a variant with rounding, so like learning with rounding is type of thing, Mm-hmm. or the NTRU 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 Yes. Mm-hmm. one of my favorite things is that there's this line of lattice-based papers which say, "We wanna do insane stuff, we wanna be crazy, and we wanna be fast to make a lattice-based PRF."

Oh yeah I think they're within a constant factor of AES when you have AES-NI hardware assump - uh, Really? AVX-2. Yeah, I, I don't - I can't remember the precise constant factor. It might be something big like five or whatever.

But like, you can get very fast PRFs based off of very weird lattice assumptions. Um, these are the Spring and Leap Okay. I don't think anyone uses them for anything, but like, uh, they use assumptions that are much farther from kind of the boring standard lattice assumptions, uh, that, to cover, to cover that for our listeners, so, uh, we, we touched on, uh, a little bit of, uh, end true originating in the '90s, so that's the e- so let us, let us describe specifically the end true assumptions that those things that are v- consistent with what was introduced in the '90s, uh, reduced to in terms of the security definition construction reduction.

Like and not, and not the s- and not the social construction of like, well, if I can break it using a lattice attack, then why, Yeah. know, b- but like the NTRU, the problem underlying NTRU, I've heard people call it as the small decisional polynomial ratio problem. Okay Essentially, you have two polynomials. Both are drawn from some small distribution, say some like, you know, center, uh, some Gaussian type distribution, discrete Gaussian, who, who knows.

Uh, one of them you need to make sure is invertible. Uh, usually invertible mod some other prime than the prime you're normally working with, but it's invertible. then you take the, 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 of them might, 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, uh, the, kind of the standard NTRU problem, it's about inverting polynomials and multiplying them together Okay. And then, uh, around 2005, Regev introduced, uh, I think, did he literally call it just LWE, like the cryptosystem, or, you know- with errors.

So I - 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 two thousand and nine, um, survey, I think, that includes this, uh, on the LWE problem that I think includes this, uh, point. But Regev was a quantum algorithms person, and he was trying to create quantum algorithms for certain worst case lattice problems. So Oh no, I called like the shortest vector I didn't even realize that.

That's neat. That's very cool Yeah. Well, so some of his - he's kind of re - more recently he switched over into computational biology, but some of his more recent cryptographic work was actually a faster, um… I think he, it was a faster, uh, factoring algorithm. So some optimizations to Shor stuff.

Yeah. Oh, I saw that. Yeah, a quantum yeah. guy for Yeah.

right? Um, probably longer than twenty years. But so, um, 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 solve, you know, uh, these quantum, uh, sorry, these, uh, worst case lattice problems, which were of independent interest at the time. 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, uh…" Sorry. "I get a reduction from SVQT - SVP quantumly to solving LWE."

Mm-hmm. 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. And it's stood up since then, so, like, I guess it's a decent way to find a problem Yeah.

And now we have like a whole lineage of, uh, problems and like kind of, you know, narrow definitions of problems that all kind of nest down and, and reduce to different forms or, or slightly different variations on L- LWE. And like, Yeah and, um, and I think some of that, I mean, like you have like an, a learning with errors like problem or game or whatever, um, that reduce to SVP, which is the shortest vector problem, or, you know, you've got gap SVP, like you've got like, you know Yeah.

Well, so, 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? Yeah that SVP redu - um, LWE - Sorry. If I said that SVP reduces to solving L, uh, WE in the average case, that could imply that LWE is NP hard to Right is not true, and it's actually not thought to be Yeah so when you mention a gap SVP, roughly, uh, 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 this structured point cloud is the closest part to Yes. Yes low dimensions, it's easy.

You just do it by like, I don't know, looking at the thing. Um, in high dimensions - Well, high dimensions things, you know, from cursive dimensionality, you might expect it to be much harder, and it is. So do we have any intuition as to why that's hard? Like, like I get that like, 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 it shouldn't be hard, right? Like 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 NP, 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, um, so coding theory wants to look at kind of high density, uh, kind of arrangements of points that are noise tolerant, right? Uh, for standard coding theory, this is often noise tolerant in what people call the Hamming metric or pseudo-metric, where, you know, you get kind of bit flip errors, this type of things.

You know, uh, 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 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 it's, uh, so in this analog noise model, you might say, I still wanna be able to code things to get this dense point cloud so I can get efficient, say, radio communications.

Uh, but I wanna be able to efficiently decode things too. So in, in this way, uh, kind of problems like SVP, more properly the closest vector problem, uh, kind of have this kind of direct application. Uh, and this was actually one of the reasons that at least some of the initial computational study of lattices was occurring, was, uh, to kind of for these kind of, uh, radio communications Yeah, I could see that especially since random lattices for a suitable definition of random are known to be - 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, uh, get a very efficient analog communication system. Um, this is, uh, for really certain parameters, this is roughly what the LWE problem is, is kind of efficiently decoding, uh, a certain, uh, random lattice which likely has near optimal parameters for these coding theoretic purposes.

th - 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 s - uh, 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 Yeah that people make it, uh, kind of… know, cryptography still isn't from NP-hard problems, uh, in this setting. But then also you have this other community where, uh, if they could solve these computational problems on lattices on this average case setting or, you know, in the worst case setting, s - uh, then they could get these better constructions, and they haven't been able to either. Um, so Um, and we, one of the things that I s- 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, gapSVP for a lot of these LWE systems, which is, like, not necessarily a, a complexity result that we have for some of our other cryptographic constructions that we deploy in the real world So the, the answer I have to this is, eh, which is that we - so famously, we do have this reduction.

This was what Regev's two thousand and five paper for. It wasn't initially a quantum reduction. Uh, it was dequant - uh, it was made classical, I think, in two thousand and nine. Okay and maybe in more generality, like, uh, since then, kind of in the more efficient settings that we tend to use lattices, there have been more and more of these reductions.

Mm-hmm. The issue with these reductions is they're what are generally called non… There's two big issues with them, actually. So one is that if I wanted to use one of these reductions to build a cryptosystem, I would need to do two things. One is I would need to say, "Okay, now my hard problem is no longer LWE, it's, it's GapSVP."

In the worst case, so that's interesting, but I would now need to figure out what worst case instances of GapSVP look Okay Um, I don't think that's really known. Uh, so you might be able to do something. You could say like, "Hey, to figure out how hard GapSVP is in the worst case, I'll sample a bunch of stuff on average and see how it is in the average case." Mm-hmm.

But then, strategy, but then you're not using a worst-case Yeah. Okay. All right other bigger issue is that the reduction is highly non-tight. okay.

All right don't know if people have worked out the parameters or I, 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've been some errors or whatever. Um, I've seen estimates, I think, as high as maybe thirty or sixty thousand lattice dimension to get appreciable security. Um, so it, it's like a and we're nowhere, we're nowhere using that for, for things like, uh, Kyber or Dilithium or No.

So Kyber and Dilithium are all 256 So, uh, Kyber's dimension's like five twelve to ten twenty-four. Yeah. Um, the, the sixty thousand dimension does actually show up sometimes in the poly homomorphic Yeah. that's more, uh, people's - 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. Okay. the trend there is trying to get them smaller as Okay.

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 it's these two 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 gapSVP Okay is to average case cryptanalyze LWE.

'Cause 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 for 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. Yeah.

Okay if, if, someone could write down, this is what the worst case gapSVP instance looks like, and this is how long it takes to solve, then we would have something very interesting. But - and, 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, it seems unclear how to characterize the worst case gapSVP instances that you'd be reducing from Got it.

Okay, so in the '90s we had our, well, we've had our very early, uh, you know, sos- social, uh, instances of lattice cryptography. Uh, before the '90s we've got NTRU, which is still kind of, uh, floating around in some form. Since the '90s, we get the introduction of the LWE, uh, in the mid, 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 cryptosystems that uses that is FrodoKEM. Um, That's just plain Aldeburyl. So okay. All right.

I for, for some reason I didn't, I didn't clock that. I don't know. Uh, I forgot So th-there are - So, so yeah. So essentially what happens is 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. Uh, it's worth mentioning this error should also be kept secret, so you might think of it as kind of a s - kind of a static secret and an ephemeral secret, 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?

Yes 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, uh, kind of simple transformation you apply to that row. I might want it to be some sort of Toeplitz matrix, some matrix, these sorts of things. algebraic structure is 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. Um, as an example for RLWE, um, RLWE is usually done over a negacyclic, uh, cycl - sorry, a cyclotomic, uh, ring of power two.

This matrix ends up being what's called negacyclic. So you have s - one diagonal and, uh, sorry, you have the vector in a, in a column, and then each time you move it over, you kind of 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 kind of can hide some security concerns.

I said you introduce a minus sign. That sounds like extra work. Why do that? Why just avoid introducing a minus sign?

Uh, everything breaks. So that might sound like a very small reas - 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 one factor, and you can kind of hunt everything down to this degree in one factor to get a one-dimensional instance that's very easy to break.

So So like minus people, yeah for people who like aren't in their happy place when they hear the term cyclotomic field, we're starting with like Coke Zero LWE with what's now called FrodoKEM, right? Correct, yeah 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? did we do cyclotomics there? 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, uh, there's this thing that they - what's called middle product LWE. It's this, it's its own thing.

It's like you're - There's more esoteric assumptions, but it, it's essentially said that like, uh, we get hardness if any of these very large set of structures is fine. Um, so in some senses, maybe it was more conservative, but it's also, uh, 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, um, the, the initial thing that was introduced was these cyclic lattices. It's kind of the most obvious thing to do. They had antecedents in, uh, sorry, pre - uh, they had precedence in coding theory. Uh, my advisor actually, I think in two thousand and one, 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, uh, 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. Like, it, it kind of - What cyclotomics are is you take the polynomial X to the N minus one, which, uh, uh, and then you kind of factor it, and you keep the highest degree piece very roughly. this X to the N minus one very roughly i-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 And the primary motivation is to take s- a secure crypto system, but make the things that you're shuf- shuttling around on the wire smaller while keeping, while reducing to the same problem Well, so i-it's not exactly reducing the same problem. Okay. Yeah idea is that now you only have to pass around one r- uh, row or column Yes so you get a big size one. But now it is going to be like you're working over this structured family of instances.

So there are these concerns, is this structure useful for Yes. plausibly Yeah Um, and so RLWE, um, so the RXES, so it's, uh, kind of the short integer verse, uh, solution, version of this was introduced in two thousand and one. RLWE, I think, was roughly twenty eleven. Um, the structure has finally helped attackers, um, this February maybe.

Oh? Uh, I think they got a times four speed up, and it seems kind of limited to that. So it is, uh, there, it, there now finally appears to be a very small gain from the structure, but, um, 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, Mm-hmm. 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 two hundred and fifty-six by two hundred and fifty-six structured blocks, and then it builds the block matrix out of that, and this is module yeah. Yep Um, the reason why we often prefer module LWE versus ring LWE, and I say often because this is mostly trained public key cryptography and, uh, fully homomorphic encryption, everyone uses RLWE. Mm-hmm. But the reason for public key cryptography, why we do that, is that in twenty sixteen, 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, uh, schemes. But wait, wait, yeah. wait, wait, wait, wait, wait, wait, wait. Yeah Modular LWE is just LWE with block matrices Roughly, yeah.

So Okay If you hear module, it me- uh, Module. Module. Yeah, Hacı o, yeah Yes But it, it's roughly just you, you have block matrices, and they all share the same structure. So thing where, like, you look up, you look up, like, modules in Wikipedia Yeah.

get no, it's impossible. Yeah. Right, but the, the, the actual thing that's going on here is it's just block matrices It, it's block matrices, yeah. Yeah so it's block matrices, and then it's you - instead of fully materializing that, you only ever materialize like the single rows you need, and then, um, 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, you know.

So it's - is, this is my thing. easier in terms Y- it's block matrices this was my understanding, which is now, like, devastated by the last 15 minutes that, 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 of the structure that was being introduced, was about something like NTT. Was just about, like, speeding up the multiplication Well, so, so that also shows up.

So it, it, it's not independent. 'Cause if I just have this dense matrix and I have a vector and I wanna multiply them, that's N squared time, right? 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, um, and then I have a vector here, now I can do something N log N, Yeah. right?

So roughly speaking, um, 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. So we can also get some computation speed ups. so like module LWE has become, for reasons, very salient in like discussions about risk in lattice systems. But Yeah, inter- 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 gonna say Yeah. Yeah. So, so what happened is in 2016, there were quantum attacks, I think, against ideal SVP. Yeah, that rings a bell I mentioned before that SVP is what reduces, uh, worst case SVP reduces to LWE.

So you might think, oh, these quantum attacks against SVP, that's concerning for LWE. Well, not really, 'cause the reduction goes in the wrong way. So if you yeah solve LWE, you have to reduce to actually what's called a rank two instance, kind of a block structure with like 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 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." Uh, and, uh, 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. It uses RLWE with insanely more speculative parameter sets. Um, like, uh, there… When I mentioned there was this times four speed up, um, from the algebraic structure that appeared Yeah. you get much bigger ones in the FHE setting.

I think that there was maybe a fifteen-bit speed up. I, I, I don't remember. I'd have to check again. Uh, but that's because FHE people do much, much more speculative things, uh, kind of, uh, try to get things to be, uh, more efficient.

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 FL 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 wanna 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, yeah I, I would actually say lattice-based signatures do tend to be a little bit harder than fully homomorphic encryption to get right. Oh, okay. a very funny sentence, but tell me why, because I would never even have, like, that, that notion wouldn't have even entered my head So there's roughly two families of lattice-based signatures. Uh, one of them I'm more familiar with.

Um, roughly what they do is they say, okay, so lattices looks a little bit like Diffie-Hellman. If you think of it A 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 Yeah 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.

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. Oh a lot of people try to do this, and all of them break because this noise here ends up being much more devastating. Ha particular, I, I mentioned before that the noise, you can think of it as an ephemeral part of the Yeah noise is security sensitive.

so lattice-based signatures, uh, until they started to be done properly, would often leak this Ah. attacks that would l- allow attacker to recover part of the noise. If you recover part of the noise, you can almost always break the scheme pretty What's, uh, So just ask real quick what that attack looks like? 'Cause this is like one of the rare instances where I have like a bit of an intuition for what that would be.

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 this 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? I'm pretty sure they ended up being machine learning-ish type attacks where the idea is that, 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, kind of this initial block, and then everything is a translate of that, right?

So the kind of inside of this initial block, you might call the fundamental parallel pipid, or at least lattice-based cryptographers do. um, so the attacks roughly would say that we can identify leakage somewhere within this fundamental parallel pipid, 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 but it's m- 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 I, I think that there is this kind of like averaging step you have to do. I don't think you just create a lattice, and I think you do need many signature samples. Yep Oh, so you do, you do need like one key and then are we doing I, I don't know if there are attacks with a single signature. Right I, I've - It's not a huge amount you need.

I think there are papers I've seen that have been, like, on the order of five hundred, but it's, Okay. something that like, uh, you know, it's devastating attacks. You need to get this part right with a lot of space signatures. But that's why, um, if you look at stuff like Dilithium, Dilithium describes itself as kind of a Fiat-Shamir with Yes.

Yes Fiat-Shamir is, is part of creating the Schnorr signature. The aborts is to say that, hey, uh, if we would leak part of this error, we try again until we don't leak it Oh, that's, that's fascinating that that's where that comes from. Hold, ho- 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 pretty sure it's that the, the errors get too large, the rejection conditions in Dilithium are bounding the size of the error.

I think there's two rejection conditions actually, but I think that there was this paper a couple years ago that said you only really need one of them, but that one is load-bearing. Um, although this wasn't for Dilithium specifically, it was for Fiat-Shamir, uh, with a Borse type scheme. Niet. Niet Oh.

I'm That's my contribution. Okay, so for in more exotic settings like FHE, why, why do you have to get more exotic, and why are your parameters, uh, slightly, slightly different than the things that we might see in Kyber and Dilithium? Um, and why are your assumptions more exotic as well? So there's a number of for this.

So the, 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 the, I don't know, the, uh, seed compression, where, uh, an RLE cyber text 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 like an XOF Yeah. that to expand it.

Yeah For ML-LWE, 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.

Um, so even something as simple as adding together two ciphertexts, well, now you have, you know, an XOF of seed one plus XOF of seed two. You can't find a seed that really expands to that target. you now have to store the full two polynomials here, and in the ML-LWE setting, you have to store even more, So that's kind of the, uh, for FHE, you end up taking this big size hit, or sorry, this big, uh, bandwidth size hit, uh, if you end up using ML-LWE versus RLE. there's other more exotic things people use, do as well.

Um, and it's worth mentioning, when I say for FHE, there's two broad classes of FHE schemes. There's what's often called PU or TFHE-based schemes, Yeah generally, uh, CKKS, BGV, BFE. They're all kind of tensor product multiplication schemes. So for this first class, you get a lot more flexibility.

You can do things much closer to public key type crypto. Uh, but the second class is the one that I'm describing that has less flexibility. Um, in particular for the second class, uh, you get these weird assumptions about the error. So for, uh, 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's these attacks from twenty eleven, the Rohatgi attacks that, um, start being applicable and, uh, concerning. But even things like, uh, often people do, uh, you know, Gaussian type noise with standard deviation three, that's not too small, right? Uh, Gaussians are a little bit hard to generate, especially if you need to have a masked imple- uh, implementation of the generator. mm-hmm.

So instead you can actually just sum up a bunch of bits. It's a, 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, uh, very key, where kind of a certain parameter scales with the sum of all these co - 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 wanna make this as small as possible, um, which is a much more aggressive assumption be - uh, for a particular reason. In, in particular, the error distribution and the secret distribution for LWE, they tend to be fine with anything. We have these proofs that like, uh, long as they have enough, uh, entropy, uh, you can get, so there's, there's, there's this thing called entropic LWE, where… Well, there's two Robin Hoods in a second, I should say. Uh, the secret distribution and error distribution, uh, they can be the same, and then as long as the error distribution has enough entropy, uh, things are mostly fine.

Um, 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, uh, 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 because, uh, uh, 'Cause you're never quite sure how N your perimeters may be- may break down, and then, like, at least you have that as a backstop kind of deal It, 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 Okay might help with much smaller GAP-SVP instances, but an algorithm here is concretely an algorithm Got it.

Okay. All 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 be, start being non-trivial attacks that wouldn't also imply an attack for GAP-SVP. Okay So, um, so yeah.

So in FHE, the secret distribution can often end up getting much weirder with much more aggressive assumptions. Uh, I've seen papers that suggest, uh, Hamming weight thirty-two and Hamming weight sixty-four, sixty, uh, secret keys, which are very small numbers. Uh, although I don't think there have been attacks on these schemes, so. Mm-hmm.

Um, but there's also, um, the ciphertext modulus can get very large in FHE. Mm. uh, in, for Kyber, the ciphertext modulus is fourteen bits. It's relatively small.

In FHE, each, for at least these tensor product-based schemes that I was mentioning I was focusing on, um, each time you do a multiplication, you kind of 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, uh, support eight hundred bits, fifteen hundred bit, uh, moduli. Mm-hmm. Things that are much larger than the fourteen bits that Kyber uses Yeah, yeah.

And we need some like big LIM arithmetic and all of this has to be prime, prime you can usually… No, it doesn't have to be prime. oh oh good of all of these LWE-based schemes, is that the number theoretic structure of the moduli does not really matter at Oh, good so as an example, Kyber is, I think Kyber is prime, Yes to be. I mean, Saber was another, uh, NIST finalist and it's two to the thirty-two, right? So it, it doesn't really matter.

Okay for FHE, they take a bunch of word-sized primes and they multiply them together. Um, so they do CRT-based things, but you could do plenty of other things. It doesn't really matter Cool. Wow, okay.

So we've basically done a whole tour of the history of, of lattice-based cryptography, um, including some of the whiz-bang stuff that, depending on your field, you may see some, uh, FHE stuff or things that use, uh, FHE constructions under the hood such as like, uh, blind are being deployed practically, generally not full FHE Yeah think Apple's caller ID uses, uh, it uses homovers- homomorphisms of lattices. So it's like a… I wouldn't be surprised very weak, uh, homomorphic, uh, lattice-based stuff.

And I think Google might have something as well, but I forgot 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, um, basically are right out if you're trying to deploy anything that might be quantum resilient into the future, and then you start reaching for, uh, lattice things that generally might have something, uh, FHE-ish under the hood.

Um, you're just not doing a full, you know, f- f- 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, uh, and, and doing anything with that, like, that's secretly full, you know, uh, homomorphic reductions underneath, underneath it, and, uh, I expect more of those to show up. Um It's also worth mentioning it, it's not purely a quantum, pre-quantum thing. Right 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, a lot of space things tend to be very Oh yeah, that too. Yeah, yeah. Yeah, because the only real cryptography we have that I've seen some people describe as, 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 Yeah. It's, not and like you could make an argument that in terms of trying to find, uh, quantum-resistant, you know, replacements for the stuff that's like dep- the boring crypto that's deployed, uh, on, on, a lot, all, all over the place, like key agreement or the equivalent of key agreement and signatures, um, 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 cr- um, cryptographic problem lineages just don't seem to fit for one reason or another. Um, but yeah, there, there's other problems that, like, there just isn't e- e- isn't even equivalent, like the fully homomorphic stuff 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 Intrue in the '90s, right?

Like, and it, so I'm not entirely of it is, did part of it is that we didn't care about quantum then, but like I mean, uh, uh, Koblitz and Miller was like late '80s, '90s… got like a almost 10-year head start was mid-'90s, so it was, uh, a little bit later. It had some patent, uh, encumbrances. I think, uh, what's it called? Elliptic curves did as well, but I did, but ones would have been earlier.

Uh, sorry, not earlier. They would have been, the, the patents would be, uh, expired later in the future, I should say. Um, I think… How to say? Um it probably also didn't help that the Entru-based signatures were broken pretty quickly, Yeah I think they were broken before 2000, so that would, uh, make Entru encryption look a lot more suspect these days.

It seems mostly fine, but there have been non-trivial attacks about En- against Entru that, uh, are not possible against RLWE. So there, there are some concerns to have against Entru, but it hasn't impacted o- original, chain sh- sure. Like, a- also, uh, the vibe I have is that like just LWE has like a clearer kind of theoretical basis for it. Like LWE is a, it's a cleaner abstraction, right?

I, I'm more, I, I think I'm more just like there's, I, there's… like w- we had reasons to trust curves more than we had, you know, NTru or whatever, like now happen to be considered lattice. But like there's practical reasons, I assume, right? Like 'cause nobody was thinking this, like no one was thinking this carefully. I was there in 1998 yeah, so, 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, if - with, uh, vectorized multipliers and vectorized adders, they kind of take advantage of that vector issues - vectorization very well. That probably wasn't as relevant in the nineties. Um, lattices are bigger, so that's, you know, a clear downside. Um, and yeah, I, I… Like, those are the big downsides that I know have.

Sorry, that I know. Like, I, I don't know how fast lattices are compared to elliptic curves if you remove, uh, AVX instructions. they're faster. They're, at, at least the, the, the Kyber LWE stuff, uh, you don't even need speed up.

Uh, like maybe, maybe you would speed up your hash function, uh, but that's independent of the, of the, uh, lattice math on, is this on architectures? Like, look, it - Lattice is auto vectorize relatively straightforwardly in many settings as well. So this is ensuring no AVX Yeah, like even, yeah, imple- e- 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 P56 or something like that, or X25519. The X25519 might go faster than you, um, but you've had, uh, uh, some good, uh, optimization tricks, uh, added onto that for a while. Um, it's not, it's not difficult to do, uh, a very fast, naive, non, uh, vectorized assembly or intrinsics, uh, uh, LWE Kyber Sure. And we're also, we're fully curve committed before curve type, before 25519 happens, we're already like the P curves one, Mm-hmm.

Yeah One like N- N True is not in the mix I, I don't remember the initial parameter sizes from NTRU, but so this 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 a lattice problem. Algorithms for attacking lattice problems did, uh, have substantial advances between two thousand and maybe twenty twenty eighteen, somewhere around there. Um, so the security story for NTRU, like, probably didn't look that great as those advances were happening.

Mm-hmm. I don't know, 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. Yeah, Okay, I'm seeing some sample params. Yeah, go ahead timing just doesn't work out.

When NIST curves the, were being standardized in like '98, '99, and you have Andrew coming out in like '96, right? That's just not gonna 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… Yeah elliptic curves were like the hottest thing in the world because of Wiles at the time too, so Which again, I could do a full hour just on attacks on Naïve Schnorr, LW signatures or, uh, lattice signatures, 'cause those attacks are really neat.

Um, I'm, I'm gonna short-circuit this a little bit and just say simplified and true prime Mm-hmm. So SM true P versus original and true. Where are we? So I, so how to say this?

I'm, S, N true P, I would describe the following way, but I, I haven't looked at the original N true scheme as much. So S, N true P is roughly the following, um. And when I'm saying here, this, this story also was replicated in the, like the LWE land. Like roughly there are three ways to build lattice-based KEMs.

kind of start with your pseudo-random component. It could be the N true assumption, it could be LWE assumption. Um, that pseudo-random component kind of 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 this randomized subset sum of it, and then the random coefficients from the subset sum, you would have that be, uh, another secret. And then this kind of is roughly the two secrets sort of thing So this you might call a leftover hash, uh, lemma-based construction, because for its security, you need to appeal to something called the leftover hash lemma. Um, the other thing that 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, which the downside for them, they obtain this stronger form of security.

They obtain kind of a statistical indistinguishability, um, of - or they don't obtain that form of security, I should say. But applying this step kind of make this, uh, randomized sum look uniform again, Mm-hmm. th-this requires, uh, this single part of the reduction is statistically secure, so the parameters chosen for are maybe a little bit larger than you might want, without impacting positively your total end security that you get. Mm-hmm.

Uh, so instead of doing that, you can actually do this other second application of the LWE assumption, um, to get something that uses slightly smaller parameters. Both of these, they create this kind of random pad that's a-agreed to, uh, up to these lower order errors, and you can add messages to it, do a one-time pad type thing. Uh, the final thing you could do is you could 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 you could just apply some shared function to it that will agree on a key. Uh, so this type of, uh, third thing, this is closest to what, uh, Sntrup does. Um, although from NTRU, you can also build directly public key encryption, so you could do these other constructions as well, uh, at least the, variant of the leftover hash lemma thing, I think. Um, there initially were these LWE-based things that looked closer to Sntrup that didn't have this explicit message and, uh, followed this paradigm.

but they ended up not being as popular in the NIST, uh, scheme, as, uh, 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. Uh for NTRU, it ends up being easier to do.

So you can get Sntrup CCA secure based off of, uh, uh, kind of taking this NTRU assumption and then, what's it called? I think, they don't do this leftover hash lemma type thing. But, uh, you don't include this message. You apply this decoding stuff to get a shared, uh, quantity, then y- uh, to get CCA security because it's, uh, there aren't, isn't any, uh, it, it has a straighter, more straightforward path to CCA security 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's basically a drama between module L- LWE and Kyber and sEntropy, right?

Like sEntropy was implemented in SSH originally, uh, you know, New Hope, which is RLWE 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 LWE is like the standard now, right? And sEntropy 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, th- 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 untrue prime I'm biased being a fully homomorphic encryption person. NTRU is Right in fully homomorphic encryption anymore. Um, it, it is for these TFHE few type schemes, Uh-huh 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 Mm-hmm. it's explicitly insecure, so But, uh, but non-FHE for, for just regular public encryption like, well, the thing is non-FHE, this attack did not get down further, right? 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 nineteen seventy-eight, and it's been secure ever since.

But in the last few years, it'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." And it's, uh, 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 this, like, additional structure showing up, it's something that gets a little bit concerning.

Arguably, this happened for NTRU in twenty seventeen with these additional attacks on FHE. It also arguably did happen for RLWE with these attacks, these quantum attacks on this adjacent scheme, right? Or on this adjacent assumption on, uh, kind of ideal SVP, um, but, uh, not the rank two version that you would need to break RLWE. Right So there are, like, these things where it's like, whenever I see one of these kind of attacks on something adjacent, it's like, well, can it move over?

You know, is it something to be worried about? Um, so I, I would be a little bit worried about RLWE and a little bit worried about NTRU for both of those reasons. So that's also of the, the- 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, it seems like that's essentially the same argument here. It's like- so it, it's I mean, it is in this, in the year of our Lord, 2026. But are, uh, Mark, are you trying to like hint towards, "Yeah, I don't know if I wanna use those assumptions anymore, because what if they keep moving? What if those attacks keep get- getting better?"

mostly that. It, well, it's, it's in my day-to-day job, I just explicitly can't use NTRU, great And i- and it's that if I - A lot of this is kind of vibes-based in the sense that if you look at A lot of cryptography is l- is vibes-based, honestly. But why Claude's so good at it 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 if it's Q being roughly less than one over a hundred N to the three point two something, or maybe, uh, it's, it's, 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 it's like, uh, I would feel more confident if there was some clean number and being like, " Oh, an attack can't go below Yeah clean number." So Okay I wanna just compare and contrast a little bit back with elliptic curves just in terms of, like, timelines and Yeah Like, you have Koblitz and Miller being like, "Let's do elliptic curve Diffie-Hellman," in '87.

1985. W- I always thought it was '85, but when they wrote the paper, '87 when it was published, right? Um, and then NIST standardizes in '99, 2000, meaning there was some sort of lead up to that. Now, we're, we're much, much better nowadays at writing cryptographic standards, um, than, uh, uh, we were then, despite the best efforts of NIAM.

And, um, but, like, if you go back and you look at, like, what were all the problems with, like, cryptography in the 2000s and 2010s, um, they were by and large not with the primitives of that era. They were like, these standards all are written poorly, and, like, the, 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 for more or less held, and you, like, look at, you know, P256 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. look at, you know, lattice-based cryptography starting in the '90s, 10 years later looking at Ring LWE, and 20 fucking years after that is where we're at now, right? Like, Yeah I don't… I'm, 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. 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, Mm-hmm. 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.

I did it earlier today. this is did it today. before this I did it, like, earlier today because, like, again, actually understanding, like, all of the, the, the details of the crypto systems is, like, not relevant for day-to-day use a lot of the time. Um- I'm just waiting for the IETF post where they say, "David Adrian, who just learned how Yes five minutes before shooting this Because it turns out that like part of this is like evaluating, you know, experts on various things and making decisions and like that, that's the way it goes.

And I think we're actually at like a very conservative point of, of using Yeah Like post quantum cryptography is I, a type of math. Lattice cryptography is a type of math I think something that's n-not appreciated often by people who are concerned about lattices, like I've seen a lot of arguments that have a hard time following. Like people have mentioned Dual EC was bad, so we should be concerned about ML-KEM. knew you Dual_EC was bad, but when they first suggested it but so this is true, you know, it, uh, the, the potential for a backdoor was known and then also not only that, like 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 backdoor and default parameters being published that were the backdoor parameters. even ignoring that, 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 y- leveraged."

And every scheme since has always done this. Like it's, know, lattice-based cryptographers also want to build secure systems and it shows up in the constructions. not only that, like, uh, there's this, uh, like the, 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 the most part has also, uh, chosen lattice-based schemes.

Not always the same schemes. Uh, the BSI, so the German, uh, German InfoSec government group have, uh, chosen FrodoKEM, I think. Yeah the Chinese are not, they have not yet announced what, who, uh, what schemes they're gonna be moving over to. They're rather early in their process.

I Yes couple of weeks ago they had the final submission period for their schemes closed down. But the, 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, 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. So, um, uh, the, the, the issue for why it got broken is somewhat technical, but roughly the Chinese response to it appears to be that we're not gonna do LAC again, it got broken. Instead, we're going to switch to an unstructured lattice-based thing, um, 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, uh, y- another way to fix that is just use a larger modulus like Kyber does.

So i- it's, it, it might be that, uh, either one, it's, it's hard to tell But like in the BSI case and I guess in the Chinese case if they do unstructured lattices, right? Like if you're using FrodoKEM, there really is an argument there that, that that's a more a c- a c- FrodoKEM exactly. They, I think they have, what is it? I think it's SCloud+.

The, it, it's really like, it, it's more like a FrodoKEM version of this black scheme which had some, uh, roughly… would you describe this? 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. Uh, almost every scheme, you just round off the low-order bits. That's where the error was.

You're fine. Um, you could say, " Hey, handling errors, that's like what error-correcting codes do," Okay what, like, 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 Lack did, and it is roughly what SCloud+ does BER uh, uh, FrodoKEM.

Okay, so the, colla- yeah. but yeah But like if you collapse it down to just like the German case, right? Like, the, the, the, like, the Fortecum decision there really is more conservative than the Kyber thing. So In this… depends on what you mean by conservative, because it's Yep, okay it's… If, 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, I mean, it, it might be good, but AES with a thousand rounds, you know, 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? Hmm for FrodoKEM, is it more conservative or is doing Kyber, but doing Kyber with modular rank 15 more conservative? Mm-hmm.

Uh for me to say. Mm-hmm. know, you, if you're saying the downside for FrodoKEM is the large ciphertext, and I have this large ciphertext budget for conservative, being conservative, is it better to use an LW-ABS scheme versus MLW? I just don't know.

Oh, that's good. That's a really good way of framing it. That makes sense Yeah. 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 gonna set that as the bar. Looking at you, Germany Also can I wanted to, I wanted to also shout out South Korea that also did a PQ crypt competition, and they also selected, uh, lattice-based, uh, KEMs and signatures, I think. I think there was SMOG 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, "Ooh, 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 Yeah. It, it's - Th-there are, there are many different choices that you can make with lattices. I mean, even in this competition, like the final three lattice schemes, you really could have chosen most of them and gotten something mildly different and probably Yeah.

But it does seem like essentially every country I've seen that runs a standardization, um, or at least every appreciably large country that runs a standardization is kind of converging on lattice-based things. Yeah. And Oh 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 Yeah. uh, it's, it makes it a little bit more confusing of an argument Um Although the, the, the freaky argument online, or the, the freak argument online is just that like lattices are fine, modules are the problem Yeah, but th- th- in that case, if, if the NSA is saying, "Hey, China is doing unstructured lattices and we're gonna do modules," it seems like they're intentionally doing bad Yeah in like that geopolitical fight, you know?

Um, I'd be remiss to not forget about, uh, Falcon, uh, the future FNDSA, which we're totally gonna get a, a draft standard for any day now out of the Department of Commerce. Um, d- do you have anything to comment on these, uh, floating point-based, Yeah. schemes? I, I, I'm uncomfortable with it.

I don't know. Like, it, it's, it, it's really small signatures. That's great. I, I'm sure some people will do it right.

I… It, it feels like something that's very easy to get wrong. Uh, but maybe I'm pessimistic. Um, You're I don't you're not the only one that's, uh, just feeling a little about, uh, implementing Falcon securely. Um, Loading point numbers aren't real.

They can't hurt you I mean, they can hurt me in secure implementations of my cryptographic software, so Wait, how do you even handle constant time Falcon with sub-normals? a good question. I know that You don't. f- 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 Yep. anyone else understands what they're saying or will be able to duplicate that Yep. Uh, yep, exactly that. You literally clone, like, one person and stick 'em in your lab so w- what have we learned today?

I've learned that Oded Regev, who is the godfather of all lattice cryptography, is now a computational biologist. And pretty sure. he saw this coming and exited the field I, yeah, I have no clue why he switched over. And, and it's, it's not, 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. Um, so he still writes lattices papers, and he still does quantum papers and computational biology and, yeah, of sense. He's just excluded us, the terrible group of people.

Like, I don't wanna be at these NIST things Yeah My, my son is a grad student and an aspiring computational biologist, so this is, uh… 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 Bad here I've learned that you really, really need to get a quantum algorithmicist to build your cryptography because that's gonna s- stand the test of at least 20 years where other people fail. Um, and you just have to catch them b- before they turn into a computational biologist.

And a couple hours ago I learned how Kyber works. So, you know, we're all Yay! something today I also, I think everybody should go on ChatGPT and just ask it to spell out how a attack on a naive LWE SNORRE signature Oh, yeah. attack.

Yeah neat… Like, just the blueprint or the schematic of that attack is pretty neat Um, well, we wanna talk a little bit more about that in a second. Um, I wanna give a shout-out to, uh, 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, Horticulture in the, um, in the notes, uh, on post-quantum cryptography, on a whole bunch of cryptography, uh, free and available.

It's amazing, and it's pretty cool. Um, so if you'd want to learn how Kyber works and how a lot of these, uh, 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?

also worth mentioning, Yeah. so Menzies, uh, Armand Menzies, his, uh, the paper showing that Reg ABS reduction, um, is not highly non-tight, so could never really be possibly useful for setting parameters. It was one of his I with Goblitz. didn't know that!

Oh my gosh. yeah, learning so many things. Oh my goodness. Uh, 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? I don't think so. It's, yeah, like lattices, like, people seem very concerned that they might break in surprising ways, and I can't unfortunately guarantee anything about the future in any context.

Sure if you wanna see a lot of examples of lattices breaking surprising ways, you can look 20 or 30 years ago 'cause there were many very funny Yeah. Yeah. That's a good place to do it. Okay 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, of lattices where some visuals probably would've helped a lot Yeah.

Eh, about that That's a… No, you, no, you were, you were, you were doing a great job with the, uh, with the, uh, linear algebra actually, and I mean, I, I under- yes, ex- exactly the most fun that Deirdre has had on one of these episodes where we weren't just talking about isogenies 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."

We all I was doing… great It's totally great. It's fine. Nothing, don't worry about it uh, 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 like based on lattices?

Any elliptic curve over the complex numbers is a lattice, um, or a rank two lattice. Yes elliptic curve cryptography lattice-based cryptography? No, that's very stupid, but This is why you can't look anything up on Wikipedia, 'cause everything on Wikipedia is written that generally. You're the problem I think I, for the record, I, uh, I would l - If anybody has a good definition of lattice-based cryptography, I'd be very interested in hearing it because, uh, uh, I've been trying to think through it, and I keep running into these weird cases where it's like, oh, you know, 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? Let's… There's gotta be some definition somewhere, but I haven't found something that makes sense to me yet, besides it being like this socially defined research area. You might need to, uh, write that blog post. Um, cool.

Thank you. Thank you, Mark. Um, Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. Uh, you can find the podcast online at scwpod and the hosts online @durumcrustulum, @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 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. Um, 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.