Everybody Is Losing Their Minds About AI Math And Crypto

Everybody Is Losing Their Minds About AI Math And Crypto

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 transcript has been edited for length and clarity.

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. 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. The last thing that we recorded was talking to friend of the pod and Michigan football supporter Professor Chris Peikert about AI.

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

Deirdre: Huh? No, we don’t.

David: We’ve stopped talking about Michigan football.

Deirdre: We don’t talk about them anymore. AI lattice proofs, new AI-assisted proofs of hardness assumptions, lowest 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, 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, so.

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

David: 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. And then there was also a drop of, I think, 83 papers, of which some number had Lean formalizations—I think around only 10—from OpenAI about a whole host of math things, as opposed to their original 10 papers.

Deirdre: Well, they— oh, okay.

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

Deirdre: Well, not only—

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

David: None.

Thomas: Does RSA still work?

Deirdre: Yes.

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

Thomas: Did you check?

Deirdre: So.

Thomas: Did you check? Did you ask Claude?

David: Yes.

Deirdre: Yes, well, I did.

Deirdre: I asked several models to check.

David: Another victory for empiricism.

Deirdre: Not—yeah. It wasn’t just 83 papers. There were rumors for several weeks that they had a bunch of math results. And there were also rumors that they—being OpenAI specifically. 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 a single result that—we’ll put some links in the show notes—the OpenAI people heard that the Anthropic people were collaborating with real deal mathematicians to solve this problem and they had a solution.

And in the week between them hearing about that, they had a solution and they published it and they put on their blog and they had a giant paper and they had a Lean formalization, and 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 think a bunch of that’s a load of crap, but from a rumor standpoint, the rumors resolved pretty quickly.

Deirdre: But still, and then, yeah.

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

Deirdre: Correct.

David: In a way that is resolved, other than people vague posting about other people.

Deirdre: Yes. I think a lot of people are looking at the Navier-Stokes stuff, and then a few days, weeks later, this giant dump of over 400 results and a much smaller number of quote papers, write-ups. 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.

David: Now, 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 was authored by Anonymous.

David: Okay.

Deirdre: They didn’t even have a real— anyway, the—

Thomas: In my field, this is a time-honored tradition: 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: Four—over 400 of them of just you burn—

Rumors swirl

Thomas: It’s—

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

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

David: Does it burn their careers?

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

Some of them have Lean formalizations, of a small minority. Some people have found issues in a subset of those Lean formalizations, and we can talk about Lean. But the PDFs that they put out are kind of—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 English and math and they are in a PDF form.

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

Thomas: Shouldn’t you be happy?

Deirdre: Ha.

David: Yeah.

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

Deirdre: Will.

David: Yeah.

Deirdre: Yeah, maybe. We don’t know what they tried and didn’t— we don’t have the counterfactual of what did they try and not get anything out of? There’s some math people who are like, based on the results they publish, it’s obvious that they’re trying to solve a general math problem, and I forget the fucking name of it, but they’re trying to solve a bigger math problem that’s not really related to crypto, and these are 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 it’s obvious that they’re not spitting out these sub-results because they’re trying to, I don’t know—

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

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

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

David: But—

Deirdre: I don’t know.

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

Deirdre: So.

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

Deirdre: Right.

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

Incredibly likely that anything up to all classical public key cryptography is going to be broken—or algebraic group based cryptography rather is going to be broken in some way—and then walking some of that back.

Deirdre: Mm-hmm.

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

Deirdre: Mm-hmm.

David: And I kind of want to go through both why I think that and why what you see from this is actually the opposite of what’s happening there, and then where we might—

Deirdre: Yeah.

Thomas: 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: So we can all—

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

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

Deirdre: Oh yeah. Very popular amongst the cryptocurrency people.

Thomas: Yeah.

David: Yeah.

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

David: So I think we could always fall back to just pure ring LWE, where it takes a 256 by 256 matrix to encrypt.

Thomas: Symmetric binary Goppa codes.

David: —a single bit, and then you do that 32 bytes worth of time. It’s incredibly inefficient, but 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 things up.

Deirdre: Yeah, go ahead.

David: So I would say what we’ve seen in the last six months or whatever is that AI is basically a search tool. This is not to discount as progress at all. It is incredibly amazing what it has achieved. This is not just 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 is good at two-ish types of searches.

One of them being a detailed refinement of a current thing that looks similar to 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.” And I would say the Navier-Stokes result is pretty close to that, in the sense of: it started with what was already 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 humans would not.

The other type of thing is 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 saw this a little more with the lattice proof that we talked about with Chris Peikert last episode, 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 solve that reduction, basically. It was an interesting example of a, quote, “elegant solution” or application that we had kind of been talking about. We would—it would be interesting to see these models actually come up with that sort.

David: Yeah.

Deirdre: —of thing. And that connection at the very least seems to be the thing that they keep doing.

David: Well, 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 does both broad and deep searches in some ways.

Math etiquette

Deirdre: Yeah, this is a theme that I’m hearing from other mathematicians who are describing, 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. But some of them have this commonality of putting things together that are non-obvious and are a nice idea, and yeah, so that seems to be improving at least.

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

Deirdre: Yeah, too.

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

Thomas: Question for Deirdre.

Deirdre: Yeah.

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

Deirdre: Mm-hmm.

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

Deirdre: Yeah.

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

Deirdre: Oh, actually interface with mathematicians in those areas and be like, we think we found something, here’s what the model spat out. Let’s work together 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 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 this is a cultural thing. There was a wonderful thread, I think it was on one of the platforms or whatever, there was, how do we share credit anymore in academia, where the whole point is to publish and get cited, and that’s how you build your entire academic career, when all of published knowledge seems to be ingested by these bleeding edge models?

Everyone basically gets credit, so no one gets credit. Those are the two major things. But it’s obvious that that’s not what they were interested in, OpenAI. They want to see if we can throw a pretty bald, bare 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, especially human beings in that area of human knowledge; 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 because interfacing with the actual mathematicians working in this field was just another prompt. And not even a specific prompt, just “find the people working in this field and email them.”

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

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

Magical math machines

Deirdre: Yeah.

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

Deirdre: Yeah.

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

Deirdre: Yeah, that’s fair.

David: Like.

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

And as part of their post where they announced this dump, they said, “Yeah, we work with them a little bit.” And then further on, journalism was like, “Yeah, they took some of our recommendations, but the most important ones, about interfacing with the community about results before you just dump them on the internet—they obviously just did not do it all.” Quotes from actual mathematicians. And yeah, so they had opportunities to do this better, and they obviously 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 going to happen with cryptography now that we have all these 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, what are these good at?

What do we know about cryptography now that might be amenable to this? And what results might we actually expect to see versus not see? The other thing that I would add is that for the most part, the results that have been coming out for math—again, not a mathematician—have been in line with things that people 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 Riemann to actually be false. The Navier-Stokes, it was a counterexample, but it was a counter example with the external force, with an incredibly unrealistic external force. So physicists have been using Navier-Stokes to model fluid mechanics for several centuries; it seems pretty correct most of the time, right? Even if it isn’t fully descriptive, right? The proof that we talked about with Peikert didn’t necessarily— it surprised Peikert 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.

David: And then ultimately ended at— well, it got pushed as tight of a bound as possible, right? 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 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 non-PQC cryptography in that the proofs don’t exist or are really weak for the fundamental hardness of basically every single type of public key cryptography that’s based on an algebraic group. We don’t really have great formal proofs as to why these problems are hard.

We just have empirical results that suggests that they are hard. And then 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, okay, the best known attack—

Diffie-Hellman

Deirdre: We have N years, and we’ve done about this much work trying to find the best attacks against the general instances of these problems. And the best known attacks are about this proportional to the security parameter size. And we’re comfortable with that. And we’ve rolled it out. And some of the post-quantum problems are kind of an outlier in our history of rolling out cryptography, in that we have lower bound proofs of closely related problems.

David: Yeah.

Deirdre: That’s more of an outlier in the history of deploying cryptography.

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

Deirdre: Yeah.

David: So you should expect stuff to go over there. Then you go on that side—Sophie Schmieg has a really good blog post called “All Diffie-Hellman Is Elliptic Curve Diffie-Hellman.”

Deirdre: Mm-hmm.

David: 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 going to go into it. And then factoring actually is in some ways—or at least 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 two prime order groups shoved together. And if somehow you had a magical factoring or magical prime order discrete log machine, factoring pops out immediately.

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

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

David: And—

Deirdre: So that all kind of coheres.

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

Deirdre: Mm-hmm.

David: Because 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, is more or less the same for factoring and discrete log. You just do some work mod P instead of mod two, when doing a bunch of linear algebra. But that approach basically doesn’t work for elliptic curves. 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 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 that class of algorithm doesn’t work.

Deirdre: Yeah.

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

Deirdre: Yeah, it’s all Pohlig rho.

David: There is on RSA.

Deirdre: That’s the best we have. Or Pollard rho.

David: Yeah.

Deirdre: Yeah.

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

Thomas: Pollard’s rho, Pohlig-Hellman.

Deirdre: That one.

Thomas: Sorry.

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

Thomas: Just because there are Cryptopals exercises for them.

Deirdre: Oh, yeah, so I think you could kind of assume that if there’s going to be results, they’re probably going to be bigger, or in the terms of something just not working at all anymore. I think you should expect them in RSA. And if you find something, expect something that’s just completely new, but just shaves maybe only a few bits off of something, right? Elliptic curves 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.

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

David: In the US, the reason for this is crypto usually exists in CS departments because of Goldwasser, who is basically the matriarch of cryptography in the US.

Deirdre: Hehehehe. Yeah.

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

Deirdre: And there’s just so much more in symmetric. It’s crazy. And it is in Europe still. There’s just so much more devoted to hashes and block ciphers and 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 given what do we know about AI and the other results, it seems like the most likely thing that you would see is the really good AI at coding get a five to 10 bit improvement on NFS, the number field sieve, because some combination of the AI at math and coding just beats out these five professors in French who—

Deirdre: Yeah.

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

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

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

Deirdre: Europeans.

David: I expect improvements purely just from optimizing those implementations better that are equivalent to taking a few bits off, and that pushes 1024. 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. Anthropic could spend their entire GPU cluster and do it in 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 a larger but feasible effort, and then 512 will become real fast, would be my guess.

Deirdre: That happened in spare compute time for eight 896 with just CADO. I think it was just sped up and slightly improved CADO-NFS or something.

David: Yeah, that was just CADO-NFS ported to be on GPUs, and a couple parts of this are embarrassingly parallel.

Deirdre: Okay.

David: So they work very well on a GPU. But right now the RSA 1024 is roughly 80s—80-ish bits of security. And RSA 512 is like 64 bits of security, roughly, if you just plug the numbers into the algorithm complexity. That’s how many 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 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 huge. That would make RSA 1024 be as easy to break as 512 as now, and RSA 3072 look like RSA 1024 now.

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

Thomas: I zoned out there for a second.

David: —

Thomas: Is the L of 1/4 thing—is the complexity class thing, is that specific to index calculus situation there? We’re only talking about finite field cryptography.

Finite field

David: L of 1 third is the current complexity class for index calculus. It’s—I don’t remember the specific equation, but it’s super polynomial sub-exponential, and then L of one quarter would be the literal—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 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. And no one uses finite field Diffie-Hellman, so when you say RSA only, even if this translates through it—

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

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

David: Well, I mean it’s not 2015 anymore. So I would say like 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 find 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 what is the actual complexity of the algorithm now, or 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 if you’re going to say public shit, particularly if you’re reasonably well known, you should probably stick to long form content.

Deirdre: Yeah.

Thomas: So I have a philosophical question there. What you’re saying makes a lot of sense, and I agree—neither of us are machine learning experts, but I agree that the easiest way to reason about AI is as search problems and implicit search problems and all that, and you should expect 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 arming humans that are doing cryptographic research with tools that are going to accelerate their research? The premise of what you’re saying seems to be that only the AI changes something, right? But what if the AI just accelerates—you need Antoine Joux to do the work, right? But he works faster because he’s got—

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

Because that’s another theme that we’re seeing from a lot of these results: it’s either stuff like interesting connections that were not obvious, or stuff that was 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 the ladder is kind of falling in that camp, and maybe it will.

Thomas: Yeah.

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

Thomas: Yeah, I think the thing I think about here—yes, I get also the connections thing. So we had supersingular isogenies for a while, right? And you have this Richelot isogeny situation where there’s a group of people that are actually working on supersingular isogeny cryptography that are unaware of basic results in, I guess, isogeny graphs from the 1980s and 1990s, like the Richelot isogenies, which, when we had a guest on to explain them, was like, “Don’t ask, you’ll never understand these.”

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

David: Well, I think the—

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

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

Deirdre: Yeah.

David aware

David: It comes up in introductory and grad-level number theory as offhand comments, and then just, “Oh, if you’re one of those fucking nerds, you probably care about this specific thing, but we don’t. Yeah, moving on—”

Thomas: Okay.

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

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

Deirdre: Not—oh.

David: I would prefer if Nadia over at UCSD and then the folks at INRIA in France had access to a few million dollars or tens of—

Thomas: Okay.

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

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

David: Yeah, I blew a week’s worth of GPT Pro tokens on trying to get Astra to find L of one quarter RSA algorithm, and it basically got nowhere. But it was not a particularly effective guidance, I would say, of the agent, and also I had to spend a lot of time avoiding getting blocked by security 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: So I would say if we can get a result, I think Nadia can be the one to do it.

Deirdre: Yeah. It’ll take time for these things to percolate throughout the field. Yes.

David: Right. Even right now, you’re well aware that with software engineering, the various AI-pilled levels of programmers varies a lot. I assume the same is true in math.

Deirdre: And some of them are going ham. And some of them are like, “So what? Do I ask a question?” Some people are just experimenting for the first time.

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

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

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

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

I don’t know. I’m very curious to see experts get good at using these tools to drive to the eventual conclusion as fast as it can go. The things that are broken and the things that are good, because as some of the other people in our field have basically said, 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 instead of the things that are breakable.

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

Complexity theory

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 drastically underinvest in analyzing algorithms in terms of how fast they actually run on a computer, both in terms of what the literal steps are or subroutine steps are, as well—

Deirdre: Yeah.

David: As what the constants in them are. So it may be the case—the complexity class formula for L of a one quarter and what, or one third, oddly has multiple constants in it, 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 in some exponent. I don’t remember what it is. And then all the other constants that could be there that we ignore because it’s big O.

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

Deirdre: Yeah.

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

So we’re just never—we’re always going to be extrapolating that, then paired with we underinvesting constants. And this 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 FFT.

Deirdre: Yeah.

David: And it’s n log n to the one minus epsilon, and it’s like, okay, well, 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 infinite precision multiplication,

Deirdre: Yeah.

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

Deirdre: Oh, I will say—

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

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

Deirdre: No.

David: I’m not questioning all of complexity theory. I am— complexity theory is clearly 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— is the classic example. 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? 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 blog post that— the best takedown of the n log n algorithm, it’s from a statistician, and one of the things he says is, you theoretical computer science people, what are you doing?

Deirdre: I need to go see this.

David: So 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 there’s often arguments about, “Oh, I have an attack algorithm that takes this long; this is the complexity of the attack algorithm in terms of compute steps.” And that’s like, okay, well, how much quantum memory do you need to actually store all the intermediate, or the computable inputs to this algorithm? And it turns out this is one of the reasons that we don’t really care about Grover’s algorithm, because yes, if you just look at the complexity of Grover’s algorithm, we should be doubling the key sizes of our block ciphers, we should be doubling our hash sizes. But if you look at 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 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’s not necessarily a concern. So,

Thomas: This is new, right?

Deirdre: Newer.

Thomas: This is a thing I’ve been hearing. Yeah, 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: That, yeah, it’s mostly asymmetric cryptography, but even the symmetric stuff, you got to remember Grover. So is there a general consensus at this point that I can wipe that out of my—

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

Thomas: Brain?

Deirdre: Everyone was basically, yeah, we don’t really care about Grovers. Because of these reasons. Anal.

David: But to be clear, NIST did first. We’re not just cribbing—yeah.

Deirdre: Oh yeah. This didn’t come out of nowhere. NIST agrees, so all their post-quantum migration stuff, they’re not — if you’re working for the NSA or the Department of War, they’re going to require you to use AES-256, but they’ve been requiring to use AES-256 since 2000. They haven’t changed that position based on the quantum threat.

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

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

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

Deirdre: Yeah. And I remember that too, but 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, it takes a lot more resources to actually run Grovers with a large efficient—fidelity, high fidelity quantum computer than it does comparatively for a Shor’s algorithm. So anyway, that’s one example of yes, we don’t have—you could measure space cost, but that’s not exactly the same as trying to compare quick sort and merge sort and all that sort of stuff. So yeah, maybe there’s room for us to have better rules or measurements.

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

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’d call Adam Langley at Google.”

David: I’m like, “Adam Langley doesn’t even work on HTTPS at Google anymore, but I understand why you started there. You want to go to Chrome—this wasn’t even a Chrome person. You’d make a zero knowledge proof, Thomas—what?”

Deirdre: Yeah.

David: Would you do?

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

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

David: No, let’s say 2048 is breakable on like a reasonably cheap cloud cluster.

Thomas: Oh wow.

David: That level of break.

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

David: 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? It’s going.

Deirdre: I would have to figure out—

David: 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 Steve Weis, David Adrian and Deirdre.

David: Yeah.

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

Thomas: Obviously.

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

Deirdre: I would not.

Thomas: Obviously I would break the DNSSEC key signing keys, which are 2048.

Deirdre: Oh.

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

Deirdre: Yeah.

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

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

Deirdre: Oh no.

David: Don’t even try, right?

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

David: What are you going to do? Right?

Deirdre: You can move quickly to mitigate your posture, and hey, I’m going to 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 say something cryptographically nihilistic, which at least for TLS, I don’t think it would matter that much.

Deirdre: Mm.

David: Sure.

Deirdre: Huh.

Thomas: It’s not how things are going to get attacked anyways. And there’s layers of organizational and logistical security before you get to, are you breaking TLS keys?

Deirdre: Yeah.

Deirdre: Nihilist.

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

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

Thomas: Yeah.

David: Will the adversary be able to ship an update to your phone that—

Deirdre: Samsung. Yes.

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

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

Deirdre: I think that’s a good thing.

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

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 RC4.

Thomas: The stream cipher?

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

Thomas: There’s practical attacks on it.

David: I could be mistaken.

Thomas: You know how I know this is because I was—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 thought it was practical as defined by cryptographer practical, not practical in terms of you can actually 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 knowledge 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 find 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.