AI Lattice Proofs with Chris Peikert

The robots are at it again, and this time they’re solving, and breaking(?), math and cryptography! Things have been happening in the lattice corner including new leapfrogging complexity results in the closest vector problem (CVP), AND a possible poly-time quantum attack against the dihedral coset problem (DCP) that made everyone freak out for about a week (UPDATE: looks like it’s busted: https://eprint.iacr.org/2026/1693). ALSO, there was an important distinguisher attack against Classic McEliece, which on its face doesn’t sound like a big deal, unless you’re familiar with the track record of efficient distinguishers in the history of code-based cryptography… 😱

To help us make sense  of all this we are joined again by OG friend of the pod Chris Peikert! We had trouble with his audio but tried our best to fix it, apologies.

Transcript: https://securitycryptographywhatever.com/2026/08/26/ai-lattice-proofs-with-chris-peikert/

Links:
- https://openai.com/index/ten-advances-in-mathematics/
- https://cdn.openai.com/pdf/ten-proofs-oai.pdf
- https://x.com/ChrisPeikert/status/2083534770403750025
- https://bsky.app/profile/chrispeikert.bsky.social/post/3msp3boueis2z
- https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
- https://knowyourmeme.com/memes/wordcel-shape-rotator-mathcel
- Chen 2024: https://eprint.iacr.org/2024/555
- https://eprint.iacr.org/2026/1630
- https://eprint.iacr.org/2026/1693
- CVP within n^(1/2-ɛ) -  : https://eprint.iacr.org/2026/1655

"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@dadrian)

Transcript

Copy Transcript Copied

0:13

Deirdre - Hello, welcome to Security Cryptography Whatever. I'm Deirdre. David - I'm David. Thomas - I'm Thomas and I'm going to good minute in this podcast. Deirdre - That's Thomas. We have a returning special guest today, Peikert. How are you, Chris? Chris - I am great. Great to be with you again tonight. Deirdre - Yeah, I think you were with us in our first year, and now we're very happy to have you come back. And now we have you on camera for the first time. There's been a lot of news in lattices. And so we had to reach out to, I think it's fair to say, our fattest favorite lattice cryptographer to ask him questions, especially about new proofs about closest vector problem, new proofs about shortest vector problem, something called dihedral coset problem and how it affects lattices. And also Classic McEliece, because why not? So to intro, OpenAI unleashed their, I model. And I forget the name of it, Astra. David - Astral. Deirdre - They all have a cute, whimsical, powerful name or whatever. And they targeted it at a bunch of just pure math problems, it appeared to be. And they put out this paper that was like, OpenAI's 10 math proofs. and one of the 10 was like a new result closest vector problem. And when I saw this, I was like,"Oh, that's interesting, and maybe I will actually go look at the proof." But I think you read it first, and you're like,"Actually, this is kind of nice." Can you tell us your take? Chris - Yeah, so I think the first character of my skeet tweet thread on this was the exploding head emoji, like, wow. And it's held up. Like, the result itself is this new proof. So it's about the closest vector problem on lattices and actually approximating the closest vector problem on lattices, right? So the closest vector problem is I give you a lattice and I give you a target point somewhere out in space. And the goal is follow a lattice point that's as close as possible to that target point. And that's the exact, like you have to follow exactly the closest lattice vector to the target. And then there's this approximate version which says, oh, you don't have to give me exactly the closest. You can give me a point which is within some factor of the closest. Okay. So that's like the approximation factor. And for a long time, we've known that the closest vector problem is NP-hard in that exact version. Like that goes back to the 80s. That's classic stuff. And then in the 90s, people showed that increasing the approximation factor, which can make the problem easier, right? Like you have more possible answers. It's an easier problem. But even then, if you increase the approximation factor to like any constant, 100, a billion, a Google, whatever, it's still NP-hard, right, to even get approximately close to the factor. And then even if you go to factors like n to the 1 over log log n, right, so not quite a polynomial. n is the dimension here, by the way, dimension. So not quite polynomial, but merely i-ish, close-ish is still NP-hard. Okay, so that was like the last word that we had on the NP hardness. And it was from around 1998. I think maybe there's a follow up journal version in 2003. So more than 20 years. And then this hadn't budged, like nobody had improved upon that. And that result used like this heavy PCP machinery, probabilistically checkable proofs and all this stuff. Technical, doesn't matter. And then OpenAI shows up on August 1st and is like, hey, we show that actually polynomial approximation, CVP, is NP-hard. And their polynomial is n to the 1 over 400. Deirdre - I was wondering what that term really was. Chris - And so, yeah. Deirdre - That's good. Chris - And so that's a fixed polynomial, right? N to the 1 over 400. That's the first term in the title of the paper. CVP is NPR. But what's exciting is that it's some fixed polynomials end to a constant. And then I quickly noticed not making any intelligent observation whatsoever, but it's like, why end of the one over 400? Like, is there something intrinsic there? Is there something important? And so you run to your model, you run to your favorite cloud or your chat or whoever. You say, can you improve this? And it says, oh, yeah, actually, I can get you like end of the one over 28 without doing anything but like improving the bookkeeping here. Like I didn't change anything about the proof. I just used better numbers. Right. So I found it really interesting that like Astra didn't try to even. Deirdre - Well, we're not even really sure how they queried it or what they asked it, but it does. Chris - This polynomial. Yeah. Deirdre - Seem that you can come up with a impressive attacks with very simple queries with not a lot of detail about what you're asking the model to do. So driving down that factor from one or driving. Chris - Exactly. Deirdre - Up that factor from one of one over 400 to one over 128 or whatever. So how so that is bringing the closer and closer to the actual closest vector problem as opposed to like this approximation. bound, right? Chris - No well it's making it's taking you farther away from the exact version. Deirdre - The other way around. Okay, yeah, yeah. Chris - Farther away yep yeah because like we know yeah. Deirdre - Cool. And that's attractive because you can do more efficient cryptography if you have more space, kind of? Chris - Well, for the CVP, actually, crypto is not in this regime at all. So this is like purely a complexity, computational complexity result. So, yeah, I just want to put that out there. But there is this one half or n to the one half barrier, like square root of n barrier that's known, where we know that the square root n approximate CVP is in the class called co-NP, the complement of NP problems. Deirdre - Yeah. Chris - And because of that, it's highly unlikely. Okay, so this would cause some major collapse in the polynomial time hierarchy, dogs and cats living together, like chaos everywhere, right? So we do not have any reason to make, we very much do not expect square root n to be NP hard. But now we have like, oh, n to the 1 over 400 is, n to the one over 28 is, n to the one over eight is with like other people kind of pushing and prodding on the models to like improve this thing. And as of just a few days after that, somebody who goes by the name of Mira on Twitter, I don't even know who it is, poked the models long enough to get them to prove, oh yeah, I can get any n to the half minus any tiny constant. So like arbitrarily close to square root n basically is still NP hard. So now we have this like total phase change, you know, up to square root n, but not quite is NP at square root n and beyond. You have, you know, very good reason to think it's not NP-hard. And so we went from like this huge unknown gap to like completely closed gap in a matter of a few days with just miles poking on things. I mean, that's insane. David - So I want to go back to that a little bit to make sure like I'm kind of understanding that like what changed. So, like, in general, even if it's not, like, directly related to the things that we ultimately ended up making cryptography on, like, we like the idea of the problem remaining complexity theory hard for worse and worse approximations, as opposed to over time to keep it hard, having to make the approximation slowly approach the real problem. because if the approximation remains hard at arbitrarily large sized things, then we can feel better about how hard everything is overall. Chris - Yeah, you got it. I mean, it's kind of a vibes thing. It's not like a formal result, but like, let's take away CVP precisely. Let's drop that problem and just take a kind of other lattice problems like shortest vector problems and things. We can do cryptography from those problems with approximation factors that are like n or n to the 1.5 you know things like that or n squared right so like very small polynomials approximation factors give us crypto from certain lattice problems and now we're saying oh well n to that nearly one half for cp at least is np hard so it it seems like not a big jump from this np hard regime and we you know that should kind of gives us a little more confidence you know if you feel like I mean by contrast the— Deirdre - Yeah. Chris - Best algorithms we have to attack these problems in like efficiently in polynomial time they only get like exponentially bad approximation factors like nearly two to the n so you got to go all the way out to like these huge factors in order to solve these problems efficiently and so this kind of gives us a belief that okay these small polynomial factor problems are probably hard like that that that's a good good warm and fuzzy feeling yeah. David - Yeah, because like, previously, like, 1 over log log n, like, at extremely large n is basically just like, n to the 0, right, n. Chris - Yeah kind of yeah. David - But to get out there with one over the end of 400, you need to be able to end of the E to the E to the 400. Chris - Yeah right right if something like that yeah yeah. David - Or something like that for it to cross over. So it's like, all these numbers are fake. Chris - Yeah. Yeah. And I think, I think the other thing that's cool about this, I don't think anybody expected it or would have bet on it. Like if you had asked me last Friday is small, you know, tiny polynomial approximate or hard NP hard, like probably not. I don't, I don't think that's, that's going to be even true, much less do I expect it. And then, so it just completely changed our understanding of these problems. Deirdre - One other thing that you mentioned when you were skeeting, posting about this on Blue Sky, was that the proof is actually quite elegant and uses novel techniques, which is like wonderful to see because even humans sometimes have a hard time giving a grokkable, nice proof of some either, you know, something that they're trying to establish or that, you know, a lemma is correct or something like that. Can you explain that a little bit? Chris - A couple of things about this. So the, you know, the prior best result that goes back to the late 90s, using this like really heavy machinery, this PCP machinery, and all this like self-composition, really complicated. It's pretty hard to follow. It's a great result, but it's like pretty quiet run. Why can't be there. And then this result, it just like shoots straight at the target. I mean, it gives this direct reduction. I know you all remember from undergrad, like to prove a problem and be hard, you give a reduction from 3SAT to your problem. Deirdre - Yeah yeah sure we all remember from undergrad. Chris - So you guys do these in your sleep still. So that's what this did. It just went straight from 3SAT to a CVP problem, this approximate CVP problem. And it did so with really just elegant, algebraic encoding of the 3SAT formula. You have to take a 3SAT formula and translate it to a CVP, a lattice and a target point, right? And satisfying certain properties. And it just did it straight. It took like, oh yeah, we're going to encode these whole formulas as a Reed Solomon code, a Reed Solomon code word. And we're going to take each clause and encode it in a slightly different way as a Reed Solomon code word and put constraints. And these constraints give you a CVP instance. Actually, it gives you this, the side effect is it gives you this nearest code word problem instance, actually. So it goes by two steps. First, it goes to the nearest code word problem. And then there's a very simple prior known reduction from nearest code word problem to CVP. So the interesting novelty is in that step to nearest code word, which is quite cool. And it's just unlike anything I've ever seen. I asked some people around, and they hadn't seen it either. I asked the people who would like work in the coding complexity and like all these polynomial code coding problems. And they're like, yeah, I mean, I've seen some stuff with shadows and whatever, but nothing nearly quite like this. So really original, really elegant, Deirdre - Yeah. Chris - Very beautiful. David - And to just like confirm I know we all know this from undergrad but to confirm um what we definitely learned in ECS 376, like when you're there, the goal is to say, look, 3SAT, we all agree, you know, is NP hard. So if problem, or you can take a 3SAT instance, convert it into another problem, solve that problem, and then convert it back, we must know that that other problem is at least as hard as 3SAT. So in this case, we took an arbitrary 3SAT instance, and we turned it into, I don't want to solve that problem, instead I'll solve CVP directly and then therefore had we done that it must be at least as hard now which way does the— Chris - Exactly a plus yeah yeah yeah yeah. David - Inequality get rid see this was the thing that always confused me I would always get backwards I never remembered which direction of the reduction was which is that three sat less than or three sat greater than CVP. Chris - It's 3SAT less than or equal saying like the difficulty of the three set problem is no more than the difficulty of of the cvp problem but you know the inequality aside, you have it exactly right. And the interesting thing, like we're trying to prove that not CVP is NP-hard, but what you have to do is actually design a reduction that maps this formula to a CVP instance, but you need to kind of like polarize it in some way. So if the formula is satisfiable, you need to generate a CVP instance that is a yes instance, like the target point is pretty close to the lattice. But if the formula was not satisfiable, target point has to be like much farther away from the lattice by this n to the 1 over 400 factor or whatever the factor is. So you need to kind of generate these like two very different situations from merely the fact that this formula is either satisfiable or not. And you don't know whether it is your reduction just transfers its satisfiability to these two conditions. So that's why it's super intricate and tricky to some approximation proofs. Deirdre - Yeah. This kind of jumped out at me when we were analyzing this because we've seen other proofs, other algorithms from models. We especially care about how they're applicable to cryptography. And this is sort of a hop, skip and a jump away from how hard are some of the lattice problems that we build our cryptography on. But sometimes, like we've seen some papers come out that are basically driven by some of these large language models, such as ones that of Anthropic, obviously kept it up to date with the latest literature in the field. And you saw all the pieces, you were able to keep it all in your context, and you were able to put the pieces together and then kind of draw the rest of the owl. And like the result is a result and it's meaningful and it's useful, but it's also not very clever. I don't think the words elegant or, you know, interesting or, you know, any of the things that you used to describe this proof would be used for that. But now this is apparently fully powered by yet another model with a different way it was grown or a different way that it was targeted or something like that. and it's it's very interesting to see and we we might be reaching the point because I've been sort of trying to keep my ear out for do moment when it comes to mathematics or cryptography or anything like that where doing something that to the human experts seems different or notable or I would never think of that or alien because sometimes these you know Go grandmasters would describe the moves that AlphaGo would take and they'd be like, it's like someone came down to Earth and was playing some crazy alien version of Go with moves that I would never even think of. And this smells something in that ballpark. So yeah, I don't know. Chris - Yeah I I I kind of agree with everything you just said I mean I don't want to minimize anything from the previous results they're super impressive but like you say like the for the most part people say like okay yeah you took like very uh expertly put together a lot of different pieces and put them in in in different ways but like the dominoes were kind of all there lined up we didn't quite see how to knock over you know the first one or whatever and then you know the model found it and then everything falls falls and and it comes out great and like that's super useful uh super interesting but I think this is the first one you know where I can you know from my own knowledge and experience confidently say like oh this is really original like this is it's not alien math because it's all known stuff it's like these read solomon things or whatever right but they were the whole path that it took was like extremely different from anything you know I'm aware of and anyone I've talked to is aware of so that is that's why I think you know the Mythos Hawk break and everything I was like oh that's really was like wow like whoa this is really. Deirdre - Yeah. All right. Anyone have anything else before we we pivot? No. Cool. Awesome. You mentioned that there were some you mentioned before we started recording that there were some other results that had come out recently. not the closest vector problem, but the shortest vector problem that jumped out to you that we had completely missed. Do you want to share with that with the Chris - Sure. Yeah. I mean, it was over a span of maybe three days. We had three different papers posted to ePrint, which is like the cryptography preprint server, all getting more or less the same result, which the result is the following. The shortest vector problem, so that is you're just given a lattice, there's no target point, and you want to follow the exact shortest non-zero vector in the lattice. Deirdre - Mm-hmm. Chris - So zero is always in there, that's shortest, obviously, but you want the shortest non-zero vector in the lattice. So the state-of-the-art for the exact SVP is from 2015, And it's basically a two to the. So exponential time with a nice clean n in the exponent, right? And with a little extra, let's worry about that. So basically two to the n, and then these new papers, you can get something like two to the point seven, two something something times. So they improve the constant in the exponent from like just one times n to 0.7 something times n. And they all came out like within a couple days of each other. And they all use the same basic technique. And some of the papers admit that like AI came up with this and other ones, we kind of got a little And some of them don't comment at all on other AI games. But in any case, it's pretty clear that AI was the force multiplier. And so, you know, that's the result that hadn't been improved in 11 years. It uses the same core component behind the prior test results, but does some extra in a more efficient way. It doesn't seem to have any effect on the security of Datis crypto, as far as anyone can tell, because it's attacking this exact worst SVP. So if the algorithm has to provably work, and it's already has a nice shape to it and everything. And so kind of heuristically, we know how to do much better than the 2^{0.7 whatever n}. So it doesn't really change as far as we can tell any of the security estimates, but it is like, again, like as a pure complexity result, it's a big step forward. Deirdre - I wonder, I'm the fact that we had like three that came out very close to each other. And they were very similar. I'm very curious how they were querying or what they were querying. And like, I'm just I'm, I'm very curious, because I have a feeling they all kind of went in the same path. And they finessed it into, you know, something that they, you know, they put out themselves. Well, yeah, this is, Chris - And this is one where like all the techniques used are kind of well established and it was put together in a way, Deirdre - All right. Chris - But it wasn't like, Oh my gosh, this is some brand new alien math or anything like that. Deirdre - Yeah, okay. David - I was going to say, I seem to recall there being a proof for one of the lattice-related problems that the average case complexity and the worst case complexity were the same. And so does that not apply here? Like you were saying, oh, it's not relevant because it's worst case only. But I thought that we had proved for just about everything with lattices that worst case and average case have the same complexity. So what am I misunderstanding? Chris - Yeah, so we have these worst case to average case reductions, which is like what crypto frequently relies on, because you got to use random instances for your crypto, but you want to make sure that you're using secure random instances that are actually hard to break. And the worst case hardness of those kind of tells you, well, you can't break the crypto unless you're also capable of breaking these problems in the worst case. So the reason it doesn't kind of move the needle on that, which is a great question, is that these worst case to average case reductions usually have a blow up in the dimension to some amount. Right. So it's like, oh, it starts in dimension N and it goes to maybe dimension 10 N or something like that. Right. And so, oh, if I can break, well, I can break the worst case in 2^0.7n, whatever n, or I can break the average case in 2^0.7n, whatever, 0.2, something times 10n, like these aren't really comparable. So that's the, maybe the short answer to that question. Deirdre - Okay we're gonna oh of course yeah yeah yeah and there's yeah and there's always like especially. Chris - There's also approximation factors in there too. This is for exact SVP. So there's another reason. Deirdre - If you're trying to like, you know, the learning with errors problem reduces the shortest vector, and there's, there's already gaps in there we've got gaps in here. And then we've got gaps between the problem that we build our constructions with and all of them add up into what you can how expensive it is to try and actually estimate any of this stuff and break it. Chris - Break it. Yeah, exactly. Yeah. So the gaps always make things a little easier and yeah. So. Deirdre - Okay, and more lattices for lattice cryptographer. There is a is a is a is a quantum attack paper, a preliminary draft on the ePrint, and they're trying to attack the dihedral coset problem in what they say is polynomial time. And this has been a bit of a kerfuffle because one, it's a quantum algorithm and you can't just code up your quantum algorithm against toy parameters and just run it and see if it those computers yet, unfortunately. And everyone is trying to see if this paper were correct and how closely it would apply from the dihedral coset problem to things true. And we don't know. It doesn't sound like anyone knows. Do you have an opinion? David - Also, can you explain what the dihedral coset problem is? Because that's something we all also definitely know. Chris - I have opinions. Yeah, yeah, we should start with that. Indeed, indeed. Yeah. So before we go to dihedral, we should go to cyclic, because that's where the story begins, really, like 30 some years ago. Deirdre - That too, because I didn't know that one before I started reading this. Chris - So, you know, we kind of all know Shor's quantum algorithm, which like breaks factoring and discrete log. Deirdre - Yes. Chris - Right. And the way it does that is by solving this what's called a hidden shift problem on the cyclic group, basically. So there's cyclic groups in the discrete log problem and there's cyclic groups hiding in the factoring problem. And quantum algorithms, computers, Shor, at solving these hidden hidden hidden shift problems on the cyclic groups. Okay, huge cyclic groups. So the closest thing to being a cyclic group without cyclic is the dihedral group. Okay, so the dihedral group is basically cyclic, but also with like flips. So if you think of like an N-gon, a regular N-gon, a triangle, a square, a pentagon, et cetera, with N sides, and then you can obviously rotate it to itself, right? And then it'll overlap with itself with all the variations. But you can also flip it, right, if it's got an even number of sides. Flip is giving you now the dihedral group. So this is, the dihedral group is basically the symmetry of an N-gon, right? And for all we know, quantum breaks and solves this hidden shift problem on the cyclic group, huge cyclic groups, but it's totally unable to do it on the adding this one flip element kind of destroys, seems to destroy quantum's power to solve it. So that's kind of a strange and bizarre situation. But there we have it. And then, so people for a long time have been trying to solve this dihedral hidden coset or dihedral coset problem quantumly. So that's what the claimed result is basically to have done this. So you can take a lattice problem, transform it into this hidden shift on a huge dihedral group. And then if you can solve that, that gives you a solution to your original lattice problem. So that's what we're dealing with here. And there's a bunch of overheads involved in these reductions, but they're all polynomial. So the claim here is polynomial time coset problem, and therefore for all these lattice problems that underlie cryptography. So pretty serious. The good news or bad news or news is that people don't seem to buy the proof. They don't. They're identified errors in the proof that are pretty substantial and they don't seem to be easily fixable. And it's in more than one place, it appears to be. So the status of this claim is still kind of up in the air. And people are trying to figure out, you know, what's actually going on here? Are these serious issues? Are they fixable? Or is there something fundamentally, you know, insufficient with this approach? So that's where we are as of August, whatever day we're recording. Deirdre - It's just 13. Chris - This and by the time you print we may have some resolution. I know people have found some interesting things about this so stay tuned. Deirdre - If this did hold, how far away it, and which instances of LWE would be shaking in their boots versus others? Chris - Yeah. Deirdre - Because this reminds, some of us are getting flashbacks to Chen's paper in 2024, which was a different quantum attack. And it was basically going to endanger a whole bunch of lattice constructions, but especially more complex instances like need for FHE or the things you need for, there's more space in the parameters. I think it's between the dimension and the modulus size, things like that. And those are things that you usually use for more complicated instances, either using ring LWE for weird blind or, you know, odder things than say ML-KEM which the gap between those parameters is smaller. So do you think there's anything like that at play here if it were to hold. Chris - Yeah I mean all these all the paper all these questions come down to like what actual gap factor or approximation factor does this thing attack right and I think if I remember correctly with the with the chen paper it was like claiming to attack a factor bigger than maybe what basic encryption needs but sufficient to break needs or what like more fancy crypto. Deirdre - Yeah, yeah. Chris - Needs but the specific factor I think didn't really matter like if that paradigm had worked out if that algorithm had actually been correct and correct analysis we're quibbling over the approximation factor you know is it n to the one over 400 or is it n to the one over 28 or is it n to the you know whatever like it's the same kind of story broke it for n^3 and probably push on it a little bit you're going to get it for n squared and for n to the one half n to the one and whatever. So yeah, like, and you're talking about the sun, like, do you really care what the— Deirdre - It's sort of like asking how hot is the fire when everything's on fire. Chris - Temperature is? It's freaking hot, like everything's gonna burn. So it doesn't matter too much. So my best understanding is the current paper, at least claims to reach factors that would, you know, break all the crypto, or, you know, more or less all of it. And, you know, so I don't really get too wrapped up in the exact factor that's involved, because, like, either it works as a new paradigm, or it doesn't. And if it works, fundamentally, then, like, we need to abandon all this stuff, even though, oh, well, you're an end quarter off from the factor that I use that now, forget about it just like go away so um that's how I I see this. Deirdre - Okay, yeah. I think it's very hard to say. It's hard to just completely say, yeah, no, there's a bug over here. And there's a bug over there. So just like chuck it in the bin, as tempting as it is, just like, no, no, no, it's no, everything's fine. Just chuck it in the bin. So I think we have to say stay tuned to the consensus on a— Chris - Yeah, saying that the proof is flawed is like an insufficient conclusion to things. Deirdre - Yeah. Chris - But there will be more decisive conclusions in the near future. I'm very confident that will kind of fully resolve the unknowns right now. Deirdre - Okay. I hope you're right, because that'll help me sleep better at night with all of our post-quandum options. Okay. To stop talking about lattices for a second, there was another paper on classic McEliece. I are you no we're never going to stop talking about lattices or— Chris - How much time you got? Deirdre - I mean I've been told that secretly elliptic curves are a lattice or something like that or can be represented as a lattice problem um another another paper uh that does not seem to have any AI involved but like whatever doesn't who cares at this point A much more efficient distinguisher and a not very efficient decryption attack on the code-based cryptosystem Classic McEliece. but when you're telling me about a public key encryption system and it says, oh, we can distinguish your public key from a random key. And I'm just like, okay, like, all right, like, so? But apparently, this is like a big deal in code based cryptography, where code is not we've implemented computer code, but we were using codes like the Reed Solomon codes. Yeah, the error. Chris - Error correction codes. Deirdre - Goppa, in this case, I that are underneath Classic McEliece. Goppa codes that are underneath Classic us why we care about a much improved distinguisher attack and why we worry when distinguisher attack for code-based- Nice photography. Chris - Yeah, there's a bunch of things to unpack here. So the headline paper title result is like a quasi polynomial time analysis of of McEliece for the Classic McEliece kind of parameters or the asymptotic parameter Classic McEliece uses. So quasi polynomial time means, well, not quite polynomial, but pretty close. So it's not like n to a constant. It's not n cubed or n to the hundred, but it's like n to the log n. Right. That's that's what they're going after. And there's a specific reason why the log n is there, but we won't get into it. So this is like asymptotically good because the previous thing we had was a paper from Eurocrypt 25. I think it was 25, yes. That was a slightly sub exponential, like n to, sorry, two to the like n, and then some logs that happen to log factors that end up being less than one. Okay, something like that. So just barely slightly better than two to the n and not like actually practical, like this only kicked in for very large n's. So that was sort of the first bang or the first shot heard around the world. And then this result is like, oh no, it's not two to the nearly n, it's like n to the log n. So vastly, vastly better in terms of complexity. And they actually gave concrete estimates for the specific McEliece parameters, showing that the runtimes are something like 2¹¹⁵, or is it 2¹¹⁴, 2¹, something like in the 2 to the low 100s, right? That was for distinguishing. Okay, so distinguishing is like, oh, you give me a key that is McEliece key, or it's just totally random junk. And they can tell which is which, right? They can tell which one it is. That's what the algorithm does. And they have a proof, like a rigorous proof that it works within this running time. Okay, so like, why do we care? Who cares about distinguishing the key? It's because of the techniques that actually allow you to do it. It's like the ideas, the algebra, the new approach that they brought to this problem That's very unlike anything else. And they were able to extend the technique, also do decoding, basically, or like recover the message from a ciphertext, right? Given the ciphertext, recover the message. And the way it works is like very similar to the distinguisher. They basically glue the ciphertext onto the public key, like as if it was just a slight key, and they do some fiddling with it, and they run the distinguisher. And if their distinguisher says looks good, that means you have a zero in this position of your ciphertext. Deirdre - Oh, no. Chris - And if it says looks random to me, that means you have a one as the error in that position. Deirdre - Oh, no. Chris - So you can very easily recover all the bits of the error vector in the ciphertext by just kind of running the distinguisher a bunch of times with slightly bigger parameters. Deirdre - Oh. Chris - So that's the natural thing. And I should say, the fact that you can use a distinguisher to follow the error and actually do the decoding is not a big shock, let's say. I mean, it's very clever. It's a cool idea. But in codes and lattices and everything, we have all these kinds of different search decision reductions that are called. It just says, like, oh, if you have a distinguisher, you can kind of leverage it to solve and follow the error and solve LWE and whatever. So search to decision reductions are like very common in this general milieu and this version of such a reduction. So they have a way to decrypt a ciphertext in like a comparable amount of time. I'm not saying exactly. There's overhead to it for sure. But in quasi polynomial time and there are some heuristics that they need. They can't prove it completely that it works, but in all their evidence, you know, suggests that, yeah, this actually does work. And then the natural thing that they say in the paper is like, oh, by the way, we have this distinguisher. Obviously, a really important thing would be can you recover the secret key from a public key? Right. And they say, like, conceptually, our ideas ought to be applicable to that question, too. like let's get the secret key from the public key, but we'll leave that for later. Okay, so stay tuned. It's basically what they're telling us. David - Um and they weren't like they were trying to do pir they're like private information retrieval right like this was not a group of people that this didn't just come out of the like uh crypt analysis community this came out of like privacy and they were trying to build something on there. Chris - Yeah. David - Like oh well our scheme doesn't work because of this result oh wait doesn't that apply to this other thing like is that um uh like that seems bad for what like mcgleese generally like do you think there's something about mcgleese that it was like perhaps understudied relative to other things Or like, why do you think that this kind of popped out of a somewhat unrelated field rather than from the cryptanalysis itself? Is there any takeaway from that, or is it just the way the world goes? Chris - I mean, I can spec. Yeah, I can speculate. I mean, I think a lot of things we're learning from these AI papers is that like big results can come from using very different kinds of math than an error. Right, the CVP result, it was just pulled error correcting codes. Certain ideas from error correcting codes, of course, were used in complex lab problems, like I don't know, but the specific sophisticated tools that the. Not the ones that, you know, you're difficult to use. So the AI's were able to bring like very different math to these problems than most of the experts, you know, working on work. for the CVP result. They brought all this function field math and error correcting codes and things like that. And, you know, this, we did simple error in the problem before, but nothing like the tools that were by Astra to this problem. And so maybe what happened here was something similar where, you know, the cryptanalysis had been a pretty narrow for a long time, right? like it had basically come down to information set decoding problem and people were just saying like how quickly can I decode uh and follow errors and decrypt it um and so pushing on that same direction for many years you know didn't yield anything really substantially new but then when people were able to bring very different kinds of mathematical algebraic geometry from 2005 uh you know all of a sudden new things become possible when you start doing these clever algebraic high degrees varieties and all kinds of stuff like that so very new tools open up some some right and new exciting results this group was trying to build what's called doubly efficient peer so very specific kind of pir that um we basically have only one construction of it's from LWE or Ring LWE actually. Deirdre - Yeah. Chris - Years ago, I think. And naturally people have been trying to build doubly efficient beer from many other assumptions. So far, I don't think anything has really come up. They ran into this barrier to follow their narrative in the paper. They ran into this barrier and realized, oh, we can't get it from this technique because mumble, mumble, mumble. and then, oh, wait, that break Classic McEliece in quasi-poly time. So it's super cool how different ideas can just cross-pollinate like this and have on a— One thing that I saw repeatedly remarked started getting attention was that I heard from more than one person, yeah, but we were always a little suspicious about Classic McEliece. And like, I am younger than Classic McEliece by at least a decade. So I don't have any of that context. I've just heard that it is a thing that exists. is like one of a handful of instances of code-based, you know, public key cryptography. And I've heard that it's like old and trusted and it's still standing. So like, it sounds fine to me. Like, you know, I, now that you look at like a, you can do distinguisher attacks like this on it and, you know, it smells a little something. Why do we believe these codes are strong or like, you know, strong one way and, you know, have a trap door the other day, other way, you know, all that sort of stuff. And like, I just don't look at the deep literature there to convince myself, because I've never really needed to. But like, why? Like, do you have a sense of like, why there's sort of a vibe in the field of just sort of like, yeah, but we were always like a little bit suspect. I was a little suspect of Mikalese. Yeah. Oh, I think Matt Green publicly said it, right? It was always sketchy. But probably a lot of people think that as well. And unfortunately, I'm not younger than McEliece cryptosystem. I mean, I can tell you the things that I have heard and the things that I believe myself. One is that a lot of variants proposed over the over the years to try and make it more efficient. Let's make the key smaller. Let's use some different codes. Let's not use binary GAPA codes. Let's use some other family of codes. Virtually all of these got broken. And for some reason, the original, you know, McEliece didn't. I don't have a sense that the community ever really understood at some deep level why All these like proposed and they just self-destruct, right? everything else around it is, is just a of uncomfortable. Everything else around it is, is just a disaster. So that's kind of uncomfortable. And then I think, I mean, another aspect of it is like, people just don't understand what it is that makes it, you know, kind of okay, where all these variants aren't. Deirdre - Mm-hmm. Chris - And the level of diversity of breadth of ideas that had brought to attack it were not that wide. They kind of all came down to this variations of information set decoding. Let's just treat the public code and then try to decode the random code. Deirdre - Mm-hmm. Chris - We'll attack on the public keys themselves. But obviously, it was just like a permutation and a linear transform of this code. so it just has this it just has this kind of feeling why if this is okay exactly makes it okay when all these other things okay I at least never found a you know a good solution for these things so that's you know probably why you know when I was in school I would talk to you know I remember talking to some professors about it and they're like yeah we don't know what the hell is this thing like we just don't know what to think of it right and like scientifically you want to understand you know you want to have a reasonable explanation for why this thing is plausibly secure and I never heard one at least you know um yeah. Deirdre - Hmm. This unfortunately is reminding me of the oil and vinegar and variants that are being tried out, especially for post-quantum signatures. And there have been, I think it's wedge attacks against a lot of these more complicated, smaller, faster versions that oil and vinegar is a specific flavor of multivariate public key cryptography. And it just seems like all of these other ones, except OG oil and vinegar, and I think mayo, which has like a slight tweak on oil and vinegar, just keep, they keep falling down. And a lot of this sounds very similar to the story you told of codes that are code-based crypto. Chris - Yeah, there are a lot of similarities, like you say, like people propose things to try to improve the efficiency, you know, just So understand is, you know, good in them to work or not work. Deirdre - Thank you very much for taking on a tour on various sections of post-quantum David - One last important question, though. Chris - David? Yes. David - How are you feeling about Michigan football this season? Chris - This season. Well, can we talk about like what's happened since the last time I was on? David - Oh, yeah. Chris - We got a national championship in football. We got a national championship in basketball. David - I mean, champions. Oh, yeah. Chris - Who's got it better than us, man? David - Mm-hmm. Nobody, although. we don't need to talk about what happened. Chris - So. David - Kind of in between some of those things but like right now you know we asked grandma for Kenny Dillingham and she said what Kyle Whittingham and there we are that's gonna be great. Yeah, and I'm excited to see you at the Rose Bowl in a few months. Congrats, Michigan football. Go blue. Cool. All right. Where's my thing? Oh, gosh. I do this every time. I have a spiel that I have to give. Chris - Sponsor read. Deirdre - Yes. Well, David - No, we did our one sponsor read of the year. Deirdre - We do one a year. David - And we thank them very much. Chris - Hmm. David - But we did the one. Deirdre - Um where is it okay Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. You can find the podcast online@scwpod, and the hosts online@durumcrustulum, @tqbf and@davidadrian. You can buy merch online at security at merch that Security Cryptography Whatever.com and if you like the pod give us a five-star review Go blue!