翻訳待ち：AI Lattice Proofs with Chris Peikert

AI サービスが一時的に利用できないため、復旧後に翻訳を補完します。

Aug 26, 2026 AI Lattice Proofs With Chris Peikert SCW #episode #security #cryptography #lattices #proofs #llms #mceliece #michigan 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. 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 This rough transcript has not been edited and may have errors. Deirdre: Hello, welcome to Security Cryptography Whatever. I’m Deirdre. David: I’m David. Thomas: I’m Thomas and I’m going to be lucky if I have one good minute in this podcast. Deirdre: That’s Thomas. We have a returning special guest today, Professor Chris 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 think it’s still closed 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 for hardness of the 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. Chris: 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, polynomial, 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 [truncated for AI cost control]