Everybody Is Losing Their Minds About AI Math And Crypto

Everybody Is Losing Their Minds About AI Math And Crypto

SCW's Picture
SCW #episode #security #cryptography #mathematics #ai #proofs #complexity

The gang talks about what AI getting Good At Math might mean for cryptography, and why public-key cryptography probably isn’t ending. David is on a mission to civilize and claims a crisis of empiricism. He also wrote a blog post about this. Everyone agrees Nadia deserves tokens.

“I mean, you could claim that anything’s real if the only basis for believing in it is that nobody’s proved it doesn’t exist!”

Links:

This rough transcript has not been edited and may have errors.

Chapters:

Intro

Deirdre: Hello, welcome to Security Cryptography Whatever. I’m Deirdre.

David: I’m David.

Thomas: It’s a me, Thomas.

Deirdre: Yes, that’s Thomas. Um and it’s a just us episode because everyone is losing their minds about math and cryptography and AI and math.

Thomas: I’m not losing my mind.

David: Yeah. Everybody’s crazy except us.

Deirdre: Yeah Yeah. Peikert about AI AI. Uh uh and Michigan football supporter Professor Chris Peikert Peikert about AI AI. Uh uh and Michigan football supporter Professor Chris Pike Peikert about AI AI.

David: We don’t talk about Michigan football anymore.

Deirdre: Huh? No, we don’t.

David: We we’ve stopped talking about Michigan football.

Deirdre: We don’t talk about them anymore. uh AI pro AI lattice proofs, uh new AI assisted proofs of hardness assumptions, low uh you know, low lowest uh low bound hardness assumptions for things like the closest vector problem, which is fundamental to some of our lattice constructions that we think are post-quantum secure or at least they’re very related to the hardness assumptions of the things that we’re trying to deploy, uh, which is extremely cool. But also the AIs are doing a whole bunch of other math apparently and just going like And dumping it on us and solving very big problems like the Navier Stokes fluid dynamics problem, which I had not heard about until they apparently solved it.

David: Yeah. Yeah, so.

Deirdre: And all of this has happened in the last few weeks.

David: I don’t I don’t know if solved is the right word for Navier-Stokes, but yeah, since the last time we recorded,

Deirdre: So.

David: There was a Navier-Stokes counterexample for the external force case. Um and then there was also a drop of drop of I think 83 um papers of which some number had lean formalizations, I think around only 10 um uh from openai about a whole host of math things um as opposed to their original like 10 papers,

Deirdre: Well they oh okay.

David: Uh of which one was about lattices that we talked about with Chris. Um and the drop of 80 th the there’s a bunch of controversy around the Navier Stokes that I don’t think we’re gonna go into, but the 80 drop of 83 papers I think was much larger um and raised a lot more questions, I think, in the math community about is this an effective way to communicate?

Deirdre: Well, not only.

Thomas: So which algorithms are which algorithms are broken now because of that drop?

David: None.

Deirdre: Uh.

Thomas: Does RSA still work?

Deirdre: Yes.

David: So the the drop of 83 had nothing to do with cryptography.

Thomas: Did you did you check?

Deirdre: So.

Thomas: Did you did you check? Did you ask Claude?

David: Yes.

Deirdre: Yes, well I did.

David: Uh.

Deirdre: I asked several models to check.

David: Uh uh uh another victory for empiricism.

Deirdre: Not Yeah. Um it wasn’t just 83 like papers. They like okay, they just there were rumors for several weeks that they had a bunch of math results. Um, and there were also rumors that they being open AI specifically. Uh, and there were also rumors that they had some crypto, classical crypto-related results, and we still haven’t really seen anything come out of that. But we did see this just dump after this Navier-Stokes stuff, which was like a single result that like you can go we’ll we’ll put some links in the show notes of like They the open AI people heard that the anthropic people were collaborating with like real deal mathematicians to solve this problem and they had a solution.

And in like the week between them hearing about that and like they had a solution and they published it and they put on their blog and they had like a giant paper and they had a lean formalization and like the the external mathematicians were like I was asking OpenAI, ChatGPT about something.

David: Yeah.

Deirdre: Did you use my chat session to scoop me?

David: Yeah, I mean I think a bunch of that’s like a a load of crap, but like um but from a rumor standpoint, the rumors resolved pretty quickly.

Deirdre: But still that’s and then yeah.

David: There was like rumors of a millennial problem that pretty quickly went to Navier-Stokes, and then like the labs were racing, and then there was a paper within like three days. There was nothing nearly as credible unless you’ve heard something like for real that there is actually a cryptographic result of any actual meaning from anyone like mildly reputable or—

Deirdre: Correct.

David: In a way that is resolved, other than like people vague posting w about other people they’d post it.

Deirdre: Yes. I think a lot of people are looking at this the Navier-Stokes stuff, this giant like, and then a few days, weeks later, this giant dump of over 400 like results and like a much smaller number of quote papers write-ups. Uh a couple of them have reasoning traces that they just literally put in a giant repo with a single commit on GitHub and they just slapped it up there. Um.

David: Now to to to be fair, if it had more than one commit, would that have helped you go through it?

Deirdre: No, it wouldn’t, but it’s just it was it was authored by Anonymous.

David: Okay.

Deirdre: Like they didn’t even have a real c like anyway, uh the—

Thomas: In my field, this is a this is a time-honored tradition of in competitive exploit development, if you’re worried that somebody else is about to announce something,

Deirdre: Yeah.

Thomas: You burn the exploits. You just drop them. It’s what you’re supposed to do.

Deirdre: Like four over 400 of them of just you burn uh like.

Thomas: It’s.

Rumors swirl

Deirdre: Years of PhD students and and academic careers in mathematics.

Thomas: I gotta say you don’t sound you don’t sound thrilled about this.

David: Does it burn their careers?

Deirdre: I think the whole thing that the way that at least OpenAI has been conducting themselves in terms of basically taking math problems to show how badass their models are, um, is extremely rude to like the entire field of mathematics as like a human endeavor because all of all of this is is interfacing with like the human culture of how humans do mathematics and especially because they like it’s obvious that they just threw a bunch of queries at models, took what’s got spat out, and kind of just threw it up on the internet.

Some of them have lean formalizations of a small minority. Some people have found issues and s in a subset of those lean formalizations and like we can talk about lean. Um but it’s like the paper the PDFs that they put out are like kinda like maybe they make sense, but they’re also kind of gobbledygook. They’re not intended for a human being to read, even if they are using langu like English and math and they are in a PDF form.

Like it’s like it’s it’s kind of like running a query, throwing it over the wall and saying, Math mathematicians, you figure out what this actually means. To mathematics. It’s quite rude. Like, and the I feel like that’s being uh uh nice about it. So but then and if you care about cryptography, it doesn’t look like there’s anything in there that’s relevant to cryptography.

Thomas: Like um Shouldn’t shouldn’t you be happy?

Deirdre: Ha ha.

David: Yeah.

Thomas: It’s a negative result. Isn’t that what uh that’s what Chris Peikert and Mac.

Deirdre: Will.

David: Yeah.

Deirdre: Yeah Yeah maybe we don’t know what they tried and didn’t we we don’t have like the the counterfactual of like what did they try and and not get anything out of? We got some in in like things there’s some math people who are like based on the results they publish, it’s it’s obvious that they’re trying to solve like a general math problem and I forget the fucking name of it, but like they’re trying to solve like a bigger math problem that’s not really related to crypto and these are sort of like sub problem results that kind of fall.

David: Everyone wants to solve a Riemann for no particular reason.

Deirdre: Out of that. It might yeah, it might be Riemann, but like it’s obvious that they’re like they’re not spitting out these these sub-results because they’re trying to, I don’t know,

David: Um.

Deirdre: Prove P equals NP or some other cryptographically related problem or something like that.

David: I don’t know that P equaling and P is even that cryptographically related, which we’ll get to.

Deirdre: No, it’s not, but like I’m trying to think of a a big grand problem that would be related to cryptography and like whatever.

David: But like.

Deirdre: I don’t know.

David: But I I think your point about cryptography missing is like kind of gets back to what I was gonna say a friend labeled as a crisis of empiricism.

Deirdre: So.

Thomas: Um.

David: Because you can interpret that as two ways. You can interpret that as like evidence as to what the models are good at based off based off of everything that we have seen. Or you can interpret it a as everything you don’t see must be the things that they’re the best at.

Deirdre: Right.

David: Right? To that I will I will say so so like uh um or or rather moving on a little bit from the 83 proofs, this has led people to infer and the rumors that like there is some big result about cryptography. And then I would say um a number of like well-known cryptographers, either public some of which publicly, some of which like privately, when I’ve texted them, have been like, oh, suddenly they are rating anywhere from 3% to 15% to increase.

incredibly likely that like anything up to all public key cryptography um like is gonna uh uh classical public key cryptography is gonna be broken and then or algebraic group based cryptography rather is gonna be broken in some way and then walking some of that back.

Deirdre: Mm-hmm.

David: Um but I I just don’t think there is any evidence for that.

Deirdre: Mm-hmm.

David: And I kinda wanna go through like both um why why I think that and why what you see from this is actually the kind of the opposite of of what’s happening there and then like where we might.

Deirdre: Yeah.

Thomas: Having seen this coming having seen this coming like a mile away, I’ve already coined the term postpublic cryptography.

David: Actually expect to see results.

Deirdre: Yeah, sure.

Thomas: Um so we can all.

Deirdre: So Kerberos. We’re just gonna use the OG version of Kerberos forever.

Thomas: There’s a whole diff there’s a whole different there’s there’s whole families of postpublic cryptography I’m sure there’s a hash based construction we can use somewhere.

Deirdre: Oh yeah. very very popular amongst the uh the cryptocurrency people.

Thomas: Yeah.

David: Yeah.

Deirdre: They’re just they’re just gonna throw out all um all algebra and just just just just use hashes forever. Don’t tell the threshold. Threshold wallet people, but it it’s all hashes all the way down. Anyway.

David: So I think we could always fall back to like just pure ring LWE where like it takes a two fifty six by two fifty six matrix to like encrypt.

Thomas: Symmetric binary GAPA codes.

David: A single bit and then you do that, you know, like 32 bytes worth of time, it’s incredibly inefficient, but like the pure construction that is NP complete, I believe, gives you a scheme that encrypts a single bit. And so let’s scale that up.

Thomas: We’ve scaled dumber we’ve scaled dumber things up.

Deirdre: Yeah. Um yeah, go ahead.

David: Um so I would say like what we’ve seen in the last like uh six months or whatever is that like AI is basically a search tool. this is not to discount as progress at all. It is incredibly amazing what is achieved what it like it has achieved. This is not just like that we stochastic parroted ourselves a solution to Navier Stokes or a counter example to the Jacobian search conjecture. But fundamentally, it’s a search tool, and it kind of like is good at two-ish types of searches.

Like one of them being like a detailed refinement of a current thing um that like looks similar to like optimizing a video codec for a coding agent, right? You give it something that’s extremely verifiable, a small domain, and you say, have at it, guy. Um Um and I would say like the Navier-Stokes result is like pretty close to that um in um in um in the sense of like it started um down what was w with what was already sort of like the bleeding edge and it just fucked around with the lean until it finally got some differential equations that it did what it wants at a speed at which like humans would not.

The other type of thing is like when AI knows about two public things and then connects them for whatever reason in its weights in a way that humans have not because the chance that the single human would know those two things is much lower. You kind of saw this a little more um with the lattice proof that we talked about um with Chris Peikert uh last episode um where it connected two things and then the connection was actually not complicated at all, but the fact that there was a connection was what was novel.

Deirdre: And there was a specific application of codes to to solve that reduction, basically. It was but I it was a an interesting example of a quote, elegant solution or application that you know we had kind of been talking about like we would it would be interesting to see these models actually come up with that sort.

David: Yeah.

Deirdre: Of thing. And like that connection at the very least seems to be the thing that they uh keep doing. Uh.

David: Well, I I don’t know about keep doing it. It’s definitely done it some I haven’t gone through all of these three proofs and picked one or the other, but it seems pretty clear that it kind of does both broad and deep searches in in some ways.

Deirdre: Yeah.

Math etiquette

Deirdre: Yeah, this this is a theme that I’m I’m hearing from other mathematicians who are describing, like, oh, they did do a proof of a thing that’s relevant to my area, and it was not shit. Some of them are shit. Um, but some of them have this kind of commonality of like putting putting things together that are non-obvious and are like a nice idea and like yeah, so that seems to be improving at least.

David: Yeah, and I’d say like this is also partially due. Like Lean is also just new.

Deirdre: Yeah, too.

David: Like uh MathLib started in like 2017, lean four came out in like 2021 or 2023, right? Like um lean is relatively new too, so like there’s a couple of forces colliding here of both like AI and just the fact that like we happen to have this verifiable tool. It helps a lot with math um that just previously didn’t exist at all.

Thomas: Question for Deirdre.

Deirdre: Yeah.

Thomas: So what um I I had dinner with a mathematician a coupl— like last week um and the same question came up and I got like a whole like I.

Deirdre: Mm-hmm.

Thomas: Got like a whole explanation of they they didn’t say that it was rude, but like like the the subtext was that it was counterproductive, that all these problems are like seeds for a lot of mathematical discovery that like you’re hoping that like people don’t just solve those problems but like the the work to solve those problems turns into a lot of other important math and all that.

Deirdre: Yeah.

Thomas: But if you’re if you’re open AI in this situation with uh, you know, whatever they’ve got going on, what do you want them to do here?

Deirdre: Oh like actually interface with mathematicians in those areas and be like we think we found something, like here’s what the model spat out. Let’s work together to turn this, to understand what the model spat out, turn this into a legible proof and a legible write-up and understand what this thing is doing and present it in a e you know preprint or readable format to connect it to the rest of the area of mathematics and to make sure that the prior work that it’s obviously using because it ingested it during its training or whatever, is being properly credited.

Because like this, this is like a cultural thing of like, uh there was there was a wonderful um thread I think it was on s one of the platforms or whatever there was like uh how do we do how do we share credit anymore in academia where like the whole point is to publish and get cited and that’s like that’s how you build like your entire you know academic career. Um when the entire when all of published knowledge seems to be ingested by these, you know, bleeding edge models.

Like everyone, like everyone basically gets credit, so no one gets credit. Um, like those are the two major things. Is like, but it’s obvious that that’s not what they were interested in, open AI. They want to see if we can throw a pretty b b bald, you know, bear query at the model, what it’ll come out with. They don’t actually care about the quality of the result and bringing it to human beings beings, especially human beings in that area of human knowledge, uh, they just want to see what the model is capable of.

And like the fact that you just kind of throw this thing over the wall and it like blows up you know either a whole researcher’s like decade or possibly an entire area of mathematics or destroys like multiple like grad students like possible careers it’s just like an afterthought to them. Whereas like you could be like it could be a very fruitful collaboration for hundreds, if not thousands, of mathematicians, but they don’t care about that. They just wanted to like, it’s just a little toy for the model to show its stuff on and they don’t care about what that does for an entire area.

Thomas: Okay. That makes sense, especially especially because you know that interfacing with the actual mathematicians working in this field was just another prompt. And not even like a specific prompt, just like follow the people working in this field and email them.

Deirdre: And like it could have like I don’t know what math has, but like in cryptography, we have like a a lovely uh the database that’s like kind of like uh communally updated called crypto bib. And like anytime that I’m doing anything with models and I’m asking you about crypto, I’m like, here’s crypto bib. Like here is like a very well curated like uh reference of papers and authors and contact information.

David: Not to defend or not defend OpenAI here, but I actually think the problem of like let’s say you have like some arbitrary research result,

Deirdre: Yeah.

Magical math machines

David: Which researcher should I go talk to? Is actually non-trivial, even given one of those. Like just like thinking back like 10 years to when I was in grad school, if you had a scanning HTTPS-related result, like you could go to Chrome, you could go to Michigan, you could go uh where I was,

Deirdre: Yeah.

David: Or you could go over to say like Dave Levin over at Maryland and like um the not all of these people like collaborate together a ton right like these are all nice people I know them I have worked with them in various capacities, but like if you sent it to all three, that would actually be probably deeply unproductive, right?

Deirdre: Yeah, that’s fair.

David: Like.

Deirdre: Yeah, like you’d have to there’s some human legwork. You can’t just do another query to follow the appropriate people to bring a possible result to. But the other thing that’s like frustrating and and rude about the whole open AI timeline is that after the Navier-Stokes brou-ha-ha. They like had announced this like collaboration with a bunch of mathematicians, like on purpose, so that they could advise A— OpenAI about like how to better roll out important math important math results or like work work and interface with the mathematics community.

And they like obvi they as part of their post where they announced this dump, they were they said, Yeah, we work with them a little bit. And then like further on journalism was like, yeah, they took some of our uh recommendations, but like the most important ones about like interfacing with the community about results before you just dump them on the internet. They obviously just did not do it all like quotes from actual math mathematicians and like yeah so they had opportunities to do this better and they obviously like they they threw some lean proofs on it and that was Kind of it. So.

Thomas: I’m sold. It was rude.

Deirdre: Yeah. so but back on so we have this big result with has no cryptography. There’s a question like, well, what’s gonna like happen with cryptography now that we have all these like magical math machines? and I just think it’s a bad idea to think of them as magical math machines. Number one. What we have done is we have been able to turn a bunch of things into search problems, as discussed earlier. So the question is like what are these good at?

What do we know about cryptography now that might be amenable to this? Um, and what results might we actually expect to see versus versus not see? Um the other thing that I would add is that like for the most part, the results that have been coming out um for math, again, not a mathematician, um, have been in line with things that people like thought were true already, but had not figured out how to prove were true.

Right? We got a tighter bound on Riemann. No one expects like Riemann to actually be false. Um uh the Navier-Stokes, it was a counterexample, but it was a counter example with the external force with like an incredibly unrealistic external force. So it’s like physicists have been using Navier-Stokes to model fluid mechanics for like several uh uh several centuries, like it seems pretty f correct most of the time, right? Even if it isn’t fully descriptive, right? necessarily it surprised Peikert that there was a proof for it that they were able to necessarily it surprised Pikert that there was a proof for it that they were able to push it that far, but it didn’t wasn’t necessarily a surprising result.

The fact that it was a result was surprising, but it was perfectly in line with where things were going, Mm-hmm.

David: And then ultimately ended at well it got pushed as tight of a bound as possible, right? Um so, to some extent, I would say you should expect that AI will simply confirm your priors on cryptography.

Deirdre: Mm-hmm.

David: Would be like a first good baseline assumption, would be that anything that you already thought was true about cryptography, you should expect that AI will prove in some way better than humans would. We have this big gap in most of crypto of like non-PQC cryptography in that the proofs like don’t exist or are like really weak for like the fundamental hardness of a lot of uh of basically every single type of public key cryptography that’s based on an algebraic group, we don’t really have like great formal proofs as to why these problems are hard.

We just have empirical results. that suggests that they are hard. And then, you know, proofs in some cases that show that they’re easy in certain situations. And then just a gap of knowledge around whether or not they’re actually hard.

Deirdre: Yeah. And yet we’ve been comfortable enough with that empirical state of like, okay, the best known attack,

David: Um.

Deirdre: We have N years and we’ve done about this much work trying to follow the best attacks against the general instances of these problems.

Diffie-Hellman

Deirdre: And the best known attacks are about this, you know, this proportional to the security parameter size. And we’re comfortable with that. And we’ve rolled it out. And like some of the post-quantum problems are kind of an outlier in our history of rolling out cryptography, in that we have like lower bound proofs of like closely related problems.

David: Yeah.

Deirdre: Like that’s that’s a more of an outlier in the history of deploying cryptography Yeah.

David: Yeah, so so I I would immediately make like a a uh a division between like lattice cryptography and non-ladis cryptography because we just have like a much better uh um mathematical understanding of the like fundamental underpinnings of lattices than we do of the like hardness, the computational complexity of of various elliptic curve groups.

Deirdre: Yeah.

David: Um so you should expect stuff to go over there. Then you go on go on that side, like Sophie um Sophie Schmieg has a really good blog post um called All Diffie-Hellman is elliptic curve Diffie-Hellman.

Deirdre: Mm-hmm.

David: Um you can kind of build a hierarchy from elliptic curve Diffie-Hellman.

Deirdre: Awesome.

David: Regular Diffie-Hellman over a prime order group is actually just a degenerate case of elliptic curve Diffie-Hellman. Read Sophie’s blog post to understand why. Not gonna go into it. Um and then factoring actually is in some ways kind of or at least uh the factoring as relates to RSA is in some ways kind of a degenerate case of Diffie-Hellman, because what you really have is the product of T. Two prime order groups shoved together. And if somehow you had a magical factoring or magical prime order discrete log machine, um f factoring pops out immediately.

Um, using the same literal trick that you would use in a factoring algorithm. Um so like there is kind of a hierarchy of like ideal to less ideal that goes from elliptic curves to to Diffie-Hellman to regular RSA.

Deirdre: Yeah. And that kind of coheres with like it’s all vulnerable to shore in slightly different ways of finding periodicity and the and things like that.

David: And—

Deirdre: So that all kind of coheres.

David: Yes. And it also coheres with the like actual algorithms for factoring and discrete log and then elliptic curve discrete log.

Deirdre: Mm-hmm.

David: Because the the the best known algorithm for discrete log and factoring the number field sieve, which is basically just a fancier version of the quadratic sieve with more math in it, um is more or less the same for factoring and discrete log. You just like change um you do some work mod P instead of mod two, um, when doing a bunch of linear algebra. Um But that approach basically doesn’t work for elliptic curves. Um there’s a reason that people called factoring algorithm an index calculus, and it’s because you’re doing linear algebra over the powers of elements, which is referred to as their index, and then like that just doesn’t exist in the elliptic curves because the math is weird and involves point addition and shit like that. And so that’s more or less why it’s stronger is that like that class of algorithm doesn’t work.

Deirdre: Yeah.

David: And no one really knows how to like there’s like almost no work on like a good elliptic curve um like discrete logs that um as in the way that.

Deirdre: Yeah. It’s all it’s all polyg ro Polyg Row.

David: There is on like RSA.

Deirdre: That’s like the best we have. Or Polyd Row.

David: Yeah.

Deirdre: Yeah.

David: Yeah, there’s very little to go on. And so like right off the bat, that should tell you that like out of these like you RSA has kind of more room uh uh uh uh less of a sound basis up through elliptic curved DLP. So given that, like what could you expect?

Thomas: Holler’s row, Polyg Hellman.

Deirdre: That one.

Thomas: Sorry.

Deirdre: Yeah, yeah, yeah, yeah. I was swappadoodling the the P’s and Q’s.

Thomas: Just because there are just because there are crypto pals uh exercises for them.

Deirdre: Oh. yeah, so like I I think you could kind of le assume that like if there’s gonna be results, they’re probably gonna be and they’re gonna be like bigger or in the terms of like something like just not working at all anymore. I think you should expect them in RSA. And if you follow something expect something that’s just like completely new, but um like just shaves maybe only a few bits off of something, right? Like a Like elliptic curves have an have kind of more room to just lose a couple bits and have no one really care, although the bounds are really cut tight at 128-bit.

Um uh but in terms of like results that are actually relevant to security, you would kind of expect those, I think, in RSA. Um, and I think you might see those in in two ways, would be my guess. So, like there actually are not a lot of people that do algebraic cryptanalysis, particularly in the US. Yeah.

David: Um in the US, um, the reason for this is like crypto usually exists in CS departments because of of uh Goldwasser, um and who is basically the matriarch of cryptography in the US.

Deirdre: Hehehehe Yeah.

David: And then um in Europe it’s mostly in the math department. Um but algebraic cryptanalysis is m still more of a math thing. And there’s not that much overall. Um there’s actually only like five ish people, most of which are in France, who like really understand um the number field sieve like in and work on the implementation.

Deirdre: And th there’s just so much more in symmetric. It’s crazy. And like it is in Europe still. There’s just so much more devoted to like hashes and and block ciphers and and you know pseudo-random permutations and things like that.

David: Yeah.

Deirdre: It’s kind of wild.

David: Yeah. So you could again you could view this in two ways. You could view this as like that’s because there’s nothing left to do, or you could view this as that’s because it’s like drastically underfunded and the government has some result.

Deirdre: Mm-hmm.

David: But then like given what do we know about AI and the other results, like it seems like the most likely thing that you would see is the really good AI at coding um get like a you know five to 10 bit improvement on uh NFS, hunt the number field sieve because some combination of the AI um at math and coding like just beats out these like five um professors in French who.

Deirdre: Yeah.

David: Are great people and I am co-authors with and I appreciate them, but like you know, c compared to—

Deirdre: Who will win? One beefy LLM and all the compute you can throw at it or five lovely f.

David: Yeah. Yeah, so like I’ve been saying for a while.

Deirdre: Europeans.

David: I I I expect improvements um uh and just j purely just from like optimizing those implementations better that are like equivalent to taking a few bits off and that pushes 1024. I I would say RSA 1024 will become feasible for really large clusters. It’s kind of feasible now, depending on what you mean by feasible. Um like anthropic could spend their entire GPU cluster and do it in like a week right now, but that would be a stupid use of resources.

Deirdre: I mean they,

David: I think that’ll come down to closer to um like a larger but feasible effort and then five twelve will become like real fast would be my guess.

Deirdre: I mean like that happened in spare compute time for eight eight ninety-six with just CADO, I think it was just sped up and slightly improved CADO NFS or something.

David: Um Um yeah, that was just Cado NFS ported to um be on GPUs, and some of the parts are like embarrass a couple parts of this are embarrassingly parallel,

Deirdre: Okay.

David: So they work very well on a GPU. But like right now the um RSA 1024 is roughly 80s 80 80-ish bits of security. Um and RSA 512 is like 64 bits of security, roughly, if you just like plug the numbers um into like the algorithm complexity. That’s how many like actual bits of security you get out.

Deirdre: Mm-hmm. The next possible thing that might happen but seems exceedingly unlikely, but I know at least one cryptographer who expects this but to be fair, has like kind of thought this since forever would be moving a complexity class down from the current one L of 1/3rd to L of 1/4. That would be like huge. Um that would make RSA 1024 be as easy to break as 512 as now, and RSA 3072 look like RSA 1024 now.

Um that would push it down a lot. Um but like do you actually expect that? Well, unless you were the person that thought that before, like you probably shouldn’t expect that. And I would say the like the whole connecting unrelated dots thing much less likely because some of those unrelated dots may.

Thomas: I I zoned out there for a second.

David: —

Thomas: Is the is the L of one four thing, is the complexity class thing, is that a specific like specific to index calculus situation there?

Finite field

Thomas: Like we’re only talking about finite field cryptography.

David: Um L of 1 third is the current complexity class for um for like index calculus. It is a uh it’s I don’t remember the specific equation, um, but it it’s it’s super polynomial sub-exponential, and then L of one quarter would be like the literal like you’re changing an exponent again from one third to one quarter. So would be the next one.

Thomas: But for the specific reason that we we use curves to avoid index calculus attacks, you wouldn’t expect the same results to hit any of the curve constructions.

David: Yes, exactly. No. Um and no one uses finite field Diffie-Hellman, so like when you say RSA only, even if another this translates through it, like uh fm.

Thomas: Some other AI discovery will break all of curves.

Deirdre: They shouldn’t be, but you know, it might still be floating around.

David: Well, I mean it’s not it’s not twenty fifteen anymore. So I would say like my my general take is that like if you think something is gonna get broken, you have to explain why do you think a search problem? why do you think this is amenable to being solved as a search problem? And what do you think about the world that makes that true? And like you could go full conspiracy or closer to conspiracy theory of like this is here and it’s gonna follow these things in the other place push it through.

You could look at it as a coding problem. But in either case, you should think about like what is the actual complexity of the algorithm now or like how fast is it running now? Where do you think what types of improvements you would get and what would the impact of that be on the various crypto systems. And I would also go further and say like if you’re gonna say public shit, particularly if you’re like reasonably well known, you should probably stick to long form content.

Deirdre: Yeah.

Thomas: Um so I I have a philosophical question there. I d what you’re saying makes a lot of sense and like I agree with I mean to the I mean we’re neither of us are like machine learning experts, but like I I agree that like the easiest way to reason about AI is as like search problems and implicit search problems and all that and like the you should expect like things that are amenable to search problems to be solved or to generate new results makes perfect sense, right?

But philosophically, isn’t it also the case that you’re like arming humans that are doing cryptographic research with you know tools that are gonna accelerate their research. Like the premise of what you’re saying seems to be that only the AI changes something, right? But what if the AI just accelerates like you need you need Antoine Zhu to do the work, right? But like he works faster because he’s got.

Deirdre: Yeah. It’s possible, but that’s kind of like in the realm of the connecting things from faraway places in like the broad field of mathematics or mathematics and you know computer science, um, which maybe the model will do the connection for you, or maybe the the very smart expert human who like had a vague thought in their head or they heard a thing from a person and then they’re like they able to be like super duper accelerated using a model and able to like push it through.

Um because that’s kind of like another theme that we’re seeing from a lot of these results is like it’s either stuff like interesting connections that were not obvious or stuff that was kind of like if we had more time or if we were superhumanly faster using these models, now we can be, we would have gotten there, sort of deal. So I think kind of the ladder is is kind of falling in that camp and maybe it will.

Thomas: Yeah, like.

Deirdre: But also it’s if the thing doesn’t have something to follow, like if there isn’t a Vuln or like a major algorithmic speedup or complexity class speed up to follow, um, that doesn’t mean anyone’s gonna follow it.

Thomas: Yeah, I mean I think the thing I think about here well more like so like yes I get also the connections thing. So we had um we had super singular isogenies for a while, right? And like you have like this Richelo isogeny situation where like there’s a group of people that are actually working on super singular isogeny cryptography that are unaware of like basic results in I guess isogeny graphs from the 19 eighties and 19 nineties, like the Richelow isogenies, which when we had like a guest on to explain them was like don’t ask, you’ll never understand these.

Um, which is why I’ll remember that term forever, right? So it’s like it’s how does cryptography progress when like everybody working in it automatically has the Richelieu I isogenies on tap, right?

David: Well I I I think the—

Thomas: Like you don’t you don’t have to wonder if they’re.

David: The reverse of that statement, like, is also important. Um, right. Like the people doing the cryptography were maybe not aware of the math results from the 80s at the time, but also also the people doing that type of math now we’re not aware that isogenies were being used for cryptography. Whereas at this point, like every mathematician is aware of the fact that like factoring dis and discrete log and elliptic curves are used for cryptography at this point.

Deirdre: Yeah.

David: It like comes up in like introductory and grad level like number theory as like offhand comments and then just like oh if you’re one of those fucking nerds like

David aware

David: you probably care about this specific thing but we don’t like yeah moving on—

Thomas: Okay.

David: But they’re aware that it’s happening.

Thomas: That was gonna be my next question. So we’re not gonna you you wouldn’t expect sudden new cryptocryptographic results from ordin ordinary mathematicians, because ordinary mathematicians are already aware of the yeah.

Deirdre: Not oh,

David: I would prefer if like Nadia over at UCST and then the folks at NRIA in France had access to uh you know a few million dollars or tens of—

Thomas: Okay.

David: Million dollars of tokens like OpenAI had for Navier-Stokes and you know let them go at it because—

Deirdre: Kind of like a bleeding edge model with no no nerfing and all that.

David: Yeah yeah I I blew a week’s worth of uh of GPT Pro tokens um on like trying to get uh Astra to follow uh L of one quarter RSA algorithm and it basically got nowhere. Um but it was not like a particularly uh effective um guidance I would say of the of of the agent and also I had to spend a lot of time avoiding getting blocked by security um things.

Deirdre: Yeah,

David: And that’s not even the same version of the model that was used for these other math ones.

Deirdre: Exactly.

David: Um so I would say if we can get a result, I think Nadia can be the one to do it.

Deirdre: Yeah. uh it’ll take time for these things to percolate um throughout the field, Yes.

David: Um right even right now it just you’re well aware that with software engineering like the various AI pilled levels of researchers um varies or of of of programmers varies a lot. I assume the same is true in math.

Deirdre: And like some of them are going ham. And some of them are like, so what do I do? Do I I ask a question? like there some people are are just experimenting for the first time.

David: Some people have moral oppositions, just like in that.

Deirdre: Yes, there’s that too. I am extremely curious about because I think that I think Like what David said, like it’s a very good search tool and it’s able to kind of make connections if you know, if you can ask the right questions, the make the right queries, it can accelerate things and lines of inquiry and research that were already going and you can put, you know, connect the dots between things that you might not have connected the dots before, like they were just sitting there, but like who would ever connect them?

Because they wouldn’t be aware of them. I think that’s just gonna kind of continue and be accelerated in like, you know, you go from zero to 60 in one train of research, like these algorithm, you know, complexity improvements of you know factoring or whatever. I’m extremely curious about some of the post-quantum areas where there’s a lot of interesting stuff. Ma we’ve seen a lot of progress on codes where like ideas from humans are accelerated to like going from a distinguisher to key recovery in a matter of weeks.

like stuff like that, I think, is gonna continue to happen and in the area of lattices we may have like like we’ve driven down like the worst case to like the you know the the best possible bounds that we can get it for s you know closest vector problem, which is great. And like hopefully that kind of thing continues, but you could also see it going in another direction for you know, a d completely different application of LWE where the parameters are far away and you’re able to distinguish things.

I don’t know. Um I’m very curious to see experts get good at using these tools to like drive to the you know eventual conclusion as fast as it can go. The things that are broken and the things that are good, because uh as some of the other people in our field have basically said, like this is an opportunity to break the things that are breakable now and get rid of them and get a lot of confidence in the things that are not breakable and they’re actually quite strong, and get them used uh instead of the things that are breakable.

I think both of those things can also can be true all at the same time in the area of cryptography and like get getting these powerful tools into the the hands of the the people who can make the correct queries to to drive those directions will be valuable to cryptography in general. And it’s not all uh an apocalypse, I guess.

David: The other thing that I would add that I think is also illustrated by the 83 math results in some cases is that we like drastically underinvest in analyzing algorithms in terms of how fast they actually run on a computer both in terms of what the like literal steps are um or like subroutine steps are um as well.

Deirdre: Yeah.

David: As like what the constants in them are um so it may be the case like uh uh the complexity class formula for you know l of a one quarter and what or one third is like oddly has multiple constants in it um both that are explicit I’m leaving out one of the parameters that there is a c in there that I’m not even claiming that’s like in some exponent. I don’t remember what it is. Um and then, you know, all the other constants that could be there that we ignore because it’s big O.

Um and like it may be the case, like that L of one third where we’re at now is just actually not that hard. We’re just like really bad at the constants right now.

Deirdre: Yeah.

David: And that’s uh or for some definition of not that hard, right? That’s where like a few bits of security could even just come off of off of improving those constants, right? That’s probably the most likely thing. Question is like how far can you even take that? We don’t really have a good way for for for talking about how constant improvements like change in terms of like actual parameters for like these things. Um for like any crypto system kind of has this trouble because like we can’t prove the number of like steps that it’ll take to even do like power row for some elliptic curve because like we don’t have all the time and atoms in the universe to like empirically run the test, right?

Like so we’re just never we’re we’re always going to be extrapolating that then paired with like we underinvesting constants. And this like particularly illustrated by the examples of the proofs that are like we have a faster than n log n algorithm for integer multiplication or for ff t.

Deirdre: Yeah. Yeah.

David: And it’s like n log n to the one minus epsilon and it’s like okay well that’s that’s technically faster than n log n,

Deirdre: Yeah.

David: But then you go and look at the steps and it assumes shit like you can do constant time uh infinite precision multiplication,

Deirdre: Yeah.

David: Which is just like not a thing you can do. But even like if you could do that, like the point at which these things would actually cross, like, seems very far off. And also, like, who f gives a shit, right? Like one minus epsilon relative to like n log n? Um like is that is that a real improvement or is that just like the way that we’ve actually the the the foundations of theoretical computer science and complexity analysis are perhaps just like a little too detached for reality in terms of like how algorithms run on computers.

Deirdre: Oh, I will say.

David: Um Um.

Thomas: Going fully conspiracy theoretic as you question all of as you question all of complexity theory.

David: No, I’m not going like there was there’s a good post.

Deirdre: No.

David: Um I’ll I’ll I’m not questioning all of complexity theory. I am like complexity theory is clearly like obviously useful. I think that there are other formalizations that we have not yet come up with that may help us describe things like why quick sort and merge sort like is the classic example. Um they have the same complexity class, but quick sorts pretty much always faster because it doesn’t jump all over the array all the time, right? Like that’s something that matters. We don’t have good formalizations for a lot of the things that affect real runtimes, is my point.

Deirdre: And people.

David: And the statisticians make fun of us. I’ll link the link the blog post that like the best the best takedown of the the like n log n algorithm it’s from a statistician and one of the things he says is like you you theoretical computer science people like what are you doing?

Deirdre: I I need to go see this.

David: So I don’t I don’t want to like get into those fights so much but point out that there is a lot of room in that space.

Deirdre: Yeah. And like some it there’s there’s often arguments about like, oh, I have an an an attack algorithm that takes, you know, uh this long uh this is this is the complexity of the attack algorithm in terms of compute steps and that’s like okay well how much memory quantum memory do

Complexity theory

Deirdre: you need and to actually like store all the intermediate or the c the computable inputs to this algorithm. Uh and it turns out like this is one of the reasons that we’re kind of you know, we don’t really care about Grover’s algorithm because yes, you know, in if you just look at the complexity of Grover out our Grover’s algorithm, we should be doubling the the key sizes of our block ciphers, we should be doubling our hash sizes, but if you look at the amount, uh the fact that it needs to basically run in serial and the amount of space that you need, which is kind of a secondary concern, you need quantum memory to to execute the thing, it’s basically impossible to execute in practice.

And so we don’t really give a fuck anymore. We care more about Shor’s algorithm because that that’s not necessarily a concern. so,

Thomas: Is kind of like this is new, right?

Deirdre: Newer.

Thomas: Like this this is a thing I’ve been hearing. Yeah, I I’ve I’ve only been hearing this over the You’re more plugged in, obviously, than I am because you’re actually a cryptographer. I’ve only been hearing this for the past couple months, but it’s like an article of faith in online discussions about post-quantum cryptography.

Deirdre: Yeah, I know, yeah.

Thomas: Is that like, you know, yeah, it’s mostly you know asymmetric cryptography, but even the symmetric stuff, you gotta remember Grover and like so is there like a general consensus at this point that I can just forg I can wipe that part that out of my.

Deirdre: Yeah. There is, and I it probably the uptick is basically because Filippo, like Filippo wrote a very good blog post to basically summarize this view.

Thomas: Brain?

Deirdre: Like I’ve like everyone was basically, yeah, we don’t really care about Grovers. Like because of these reasons. Um anal.

David: But to be clear, s NIST did first, like we’re not just like cribbing f uh yeah.

Deirdre: Oh yeah, yeah, yeah. That’s yeah, yeah, yeah. This didn’t come out of nowhere. Like NIST uh NIST degrees, so all their p their post-quantum migration stuff, like they’re not like y you know, if you if you’re working for the NSA or, you know, the department of the Department of War, uh like they’re gonna require you to use AES-256, but they’ve been requiring to use AES-256 since tw 2,000. You know, they they haven’t changed that position based on the quantum threat.

They’ve just been basing it because like number go bigger and we’re, you know, super important and we want the bigger number for our block cipher. Um but NIST doesn’t care about that in terms of the PQ PQ uh PQ migration.

David: Yeah. I would say it’s been at least consensus for some since at least twenty twenty three, if not earlier,

Deirdre: Um.

David: But I agree with you that like circa around the time when I was still in school, let’s say like twenty seventeen, um when I f like first met Chris Peikert, the consensus was all square root, like double your key lengths.

Deirdre: Yeah. And like I I remember that too, but it it was very much looking just at the complexity numbers of that algorithm and nothing else. And then if you look at it just a little bit further, uh it takes a lot more resources to actually run Grovers uh with a you know large efficient uh you know uh fidelity, high fidelity quantum computer uh than it does uh comparatively for a Shor, Shor’s algorithm. So anyway, the that’s one example of yes, we don’t have like, you know, you could measure space cost, but that’s not the exactly the same as trying to compare quick sort and merge sort and all that sort of stuff. So like, yeah, maybe there’s room for us to uh have better rules or measurements.

David: I think there’s a lot of room for empiricism. Um, I want to end on one half joke slash question. Let’s say you come up or are given or your AI finds a like well a break of RSA on the order of like dropping the complexity class by one something like particularly large like that. Um how do you disclose? What do you do first? Um Um.

Deirdre: With a zero knowledge proof, of course, it’s easily usable as an oracle. No, I’m joking.

David: Someone else said to me they were like I’m s I regular I’d call like Adam Langley a Google.

Deirdre: Um.

David: I’m like Adam Langley doesn’t even work on HTTP as a Google anymore, but like I understand why you started there like you want to go to chrome this wasn’t even a chrome person um you’d make a zero knowledge proof Thomas what.

Deirdre: Yeah. Um.

David: Would you do.

Deirdre: No, I’m kidding! I’m kidding, I would not do that. I would not fucking do that ha ha.

Thomas: We’re holding you to that. Um, so what all this does is it means 1024 is breakable on consumer hardware like 512 is.

David: Uh no, let’s say twenty forty-eight is. twenty forty-eight is breakable on like a a reasonably cheap cloud cluster.

Thomas: Oh wow. Oh wow.

David: It like like that level of break.

Thomas: Um Um Well, as a vulnerability researcher and a proponent of full disclosure security, I would just drop the whole thing on Pacement.

David: What how do you disclose? Hell yeah, that’s what I said. I’m like, if I get one, I’m tweeting it out and I’m not even trying, right? Like, it’s going.

Deirdre: I I would have to figure out.

David: Like, here’s a big number, here’s its factors, here’s some code.

Thomas: There would be like there would be shout-outs at the end of my description. I would have shout-outs to uh Steve Weis, David Adrian and Deirdre.

David: Yeah.

Deirdre: I think I think honestly I would uh I would get a signal chat with all of my uh with all of my colleagues at places with lots of users that uh that uh need to know about this and then uh secondarily after they’ve been informed I would probably contact my uh uh my favorite academic cryptographers and then we’d uh write it up or something like that. I would I would be responsible and have some vague notion of coordinated disclosure.

Thomas: I mean obviously.

David: No, I mean you would do that too, but first I would just put it on Twitter.

Deirdre: I I would not.

Thomas: Obviously I would break the obviously I’d break the DNS set key signing keys, which are two or four eight.

Deirdre: Oh Oh,

Thomas: I mean I I’m publishing that on PasteBin at the same time.

Deirdre: Yeah.

Thomas: But I’ve been saying for years and years and years that it is 100% ethical to post the DNS sec root signing keys on PasteBin, even if you have them, because no one will need to be paged.

David: I like I can’t even like independent like sure like get some cryptographers involved, um, verify your result or whatever. Like I can’t imagine what uh an attempt at coordinated disclosure of like RSA is broken would look like.

Deirdre: Oh no.

David: Like, don’t even try, right?

Deirdre: It it would it would be purely a best effort Like, hey, you have a lot of users, hey,

David: Like, what are you gonna do? Right?

Deirdre: You can move quickly to mitigate your posture and hey I’m gonna like uh battle proof this with some smart people who know what the fuck this is about.

Full disclosure

David: Yeah, you’re like I just want to watch. That’s it. We’ll see what happens.

Thomas: Can I can I say something can I say something cryptographically nihilistic which at least for TLS, I don’t think it would matter that much.

Deirdre: Mm.

David: Sure.

Deirdre: Uh huh.

Thomas: Like it’s not how things are gonna get attacked anyways. And there’s like layers of like organizational and like logistical security before you get to are you breaking TLS keys?

Deirdre: Yeah.

Thomas: Um Um.

Deirdre: Be hai list.

David: Yeah, I would actually probably be more worried about like um what uh is there a long-term RSA signing key for like iOS updates?

Deirdre: He believes in nothing. Yes. And Windows and and Android and yeah.

Thomas: Yeah.

David: Like will the adversary be able to ship an update to your phone that like.

Deirdre: Samsung. Yes.

Thomas: We’ve had like we’ve had comparably b bad breaks, right? Like RC4 is up there.

David: I feel like RC4 is already on the way out, and also is not nearly that broken.

Deirdre: I mean I think that’s a good thing.

David: RC4 is broken in the sense of like it doesn’t provide 128 bits of security, but like.

Deirdre: And I think the—

Thomas: Wait, what? RC4, the one you can just run over and over again until the secrets leak out? RC4 is very broken.

David: I don’t I think you’re thinking of RC2. Like RC four.

Thomas: The stream cipher?

David: Yeah, I I don’t think RC four is that broken.

Thomas: Like there’s practical attacks on it.

David: I could be mistaken.

Thomas: You know how I know this is because I was I was Kenny Kenny Patterson made fun of me for thinking there was anything interesting about the RC4 attacks and how they worked. There definitely are. there’s practical attacks in RC4.

David: Well I I thought it was practical as defined by like cryptographer practical, not practical in terms of like you can actually like you know, get plain text out of some ciphertext that you found on the internet.

Deirdre: Ober.

David: It was bad enough that you don’t want to use it. But—

Deirdre: This is before my time.

David: Now we just look like idiots.

Deirdre: RC2 vulnerable related key attack using 2^34 chosen plaintexts.

David: Okay, so we actually think it would not be that bad, and at least Thomas and I would do full disclosure and Deirdre would make a zero dollars proof and then call our friends.

Deirdre: No, I would not. No, I would not.

David: Anyway, Security Cryptography Whatever is a side project from David Adrian, Deirdre Connolly, and Thomas Ptacek. You can buy merch at merch dot securitycryptography whatever dot com.

Deirdre: Yes..

David: You can follow us on Twitter at durumcrustulum, at tqbf and at dadrian.

Deirdre: Other places on the internet.

David: Please think critically. Rate us wherever you watch your podcasts.

Thomas: Hey the best RC4 attack takes 75 hours to recover cookies.

Deirdre: Okay.

Latest Posts

Everybody Is Losing Their Minds About AI Math And Crypto
58 min read

Everybody Is Losing Their Minds About AI Math And Crypto

SCW's Picture
SCW
AI Lattice Proofs With Chris Peikert
45 min read

AI Lattice Proofs With Chris Peikert

SCW's Picture
SCW