Episode 400 - Quantum Advances, Hybrid Signatures and SNARKs to the Rescue with Dan Boneh

Transcript

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online. This is our 400th episode of the Zero Knowledge podcast and this week I bring Dan Bonet back on the show. For those who don't know, Dan is a professor of computer science and electrical engineering at Stanford University and one of my favorite guests. We start off in discussing Google's quantum algorithm announcement as well as his involvement

with that. We cover the risks of rushing post-quantum cryptographic transitions, Dan's hesitation in offering timelines for quantum advancements and why he believes algebraic signatures are preferable to hashbased ones. We also touch on exactly what the Google works showed and the unusual way it was shared. We talk about the potential use of hybrid signatures for the postquantum transition as well as other advancements in cryptography in ZK systems that he and his research team are excited about. We wrapped up with an update on the Ethereum Foundation's proximity prize, a $1 million challenge to resolve an open mathematical question that could meaningfully improve Snarks. So, what a great way to celebrate our 400th episode. As always, with my

conversations with Dan, I was left with a bunch of ideas for future topics that we could cover, as well as guests we could invite to the show. So, hope you enjoy our 400th episode. It's quite a milestone and I want to say thank you to our listeners for sticking with us. Here's to many more Zero Knowledge podcast episodes to come. Now, here's my interview with Dan. Today, I'm here with one of my favorite guests, Dan Bonet. Dan is a professor of computer science and electrical engineering at Stanford University.

Welcome back to the show, Dan. >> Thank you, Anna. It's always fun to be on this on the show. >> Cool. And I think you may be aware of this. This is episode 400 of the Zero Knowledge podcast. >> Whoa. >> And I was very excited to have I I really thought about it. I was like, who would be an amazing guest for this particular episode? I looked at when have you last been on? What were the other episodes? And I feel I feel like this is a perfect time to bring you back. ZK is in a a bit of an inflection moment. I feel like so much research has happened and yet we're seeing it now kind of become applied all over the place. So, it's like this very different moment for ZK. So, I can't wait to talk to you about it. I want to just

highlight for the listeners some of our previous episodes in case they want to check it out. You were our guest on episode 100, then again on episode 256, and then in 20 late 2024, you were episode 345. We kept picking kind of good numbers for your episodes. My god, I can't wait to be on episode 512. >> Exactly. Yes, that's our next one. One of the things I've really liked about these episodes is I feel like every time you come on, you highlight a lot of very cutting edge research and in the episodes that come after that, maybe it might take us a few months, might even take us a few years, we eventually get to cover them. And so when I was listening back to episode 100 for example, you were talking about code

offiscation. You were talking about making things postquantum, you know, I feel like those threads that have become more and more relevant over the years were already placed. You talked about content provenence in episode 256 and then I know the last episode you talked about lattises which like I had never really heard about. And last year we actually got a chance to dive quite deep into lattises with some interviews with Vadim and Beni and we also covered it in the ZK whiteboard sessions. So I know we have a lot to cover. So one of the most relevant topics and maybe something we can kick off with is the work you did with Google on a recent paper on their quantum advancements. So maybe we can start there.

>> Yeah. Yeah. That's it's a great way to start. Actually maybe I can zoom out for just one second Anna. So the the topics that I hope we can uh we can cover is of course everybody's interested in quantum these days. So we'll talk about some quantum aspects and new developments. I'm also hoping we can talk a little bit about the proximity prize that the Ethereum Foundation put out. I find that really exciting and it's a kind of a cool math question. I you know even if you're even if your audience is not going to work on the question, I just want people to know that there's this prize for this cool math question that would be fun to discuss. And then you know there are basically all other blockchain related crypto advances that are always always fun. So I hope we have some time at the end to talk about more

general crypto advances. Of course everything is related to ZK. >> So so yeah. So let's go back to the to the quantum question. And so maybe is it okay if I start maybe just by kind of pointing out four points that I'd like the people to take away and then we can kind of drill down into these four points. >> Let's do it. >> Um >> yeah. So first of all, yeah, it's kind of interesting where you started. The first question that people usually ask me is when, right? When are we going to have a when are we going to have a quantum computer? Yeah. What's the what's the timeline look like? The answer is really nobody knows. I don't know. There's nobody else knows this. We don't know. I'll say it's a it's some it's n years away for some unknown value of n. Yeah. Now sometimes people press

me to kind of actually give a number and then what I if you really really really insist I I kind of tell you that we can try to do a M Mo's law based calculation to see how fast these machines are improving and where they have to go and then you get something like a number between 2035 and 2040 2040 is probably more more relevant. But then a lot of the physicists basically tell me that Moore's law is not the right model for estimating this this event especially in the neutral atoms experiments which we'll talk about I guess in just a second.

>> That's not a good way to predict where things will happen. So the answer is I don't know. >> Okay. But why do you have teams making predictions? Like why does Google say oh we've moved up our kind of quantum date a quantum reaching a certain level by x amount of years and then a date is given. Like why are they doing that? I'll answer that but then I want to explain quickly my three other points and then we'll dive deeper but let me let me answer that. So yeah so you're right both Google and Cloudflare have said that by 2029 they want uh everything to be transitioned to postquantum. >> Yeah. >> Now it's important to understand Google is a big organization. Yeah. The people who said 2029 for the transitions are not the quantum people. This is the Google security team. The Google

security team made their own assessment and they said we want to transition Google to postquantum security by postquantum cryptography by 2029. I want to so of course I want to kind of say why they probably did this and why this is a reasonable idea. So, first of all, transitioning all of the Google infrastructure to postquantum cryptography, that is a massive undertaking. In particular, for digital signatures, right? For digital signatures, there's typically hardware involved. You have to update your hardware, throw away old hardware, buy new hardware that's going to support all these postquantum operations. That is a fairly sign significant undertaking.

There's a very good chance that they're not going to meet the 2029 deadline by setting a 2029 deadline and missing it by 3 years. you know, they they're still on pretty safe ground. Originally, they had set the 2035 deadline. >> If they had set it to to be 2035 and then they missed that by three years, >> now we're going to getting into nervous territory. Right now, we don't really know what's going to happen. So, I think by moving the deadline earlier, in some sense, they're giving themselves some more slack. Uh, which is, you know, it's a reasonable a reasonable thing to do. Uh, so that was my first point that the timeline, remember, nobody really knows.

All we can do is is is speculate. And I'll talk more about the timeline actually as we dig deeper into it. The second point I want to make which I think is really important is actually related to that which is it's really important not to rush this transition. >> Yeah. I'm quite worried that because people are setting deadlines to be quite aggressive. 2029 is a pretty aggressive deadline. >> We are more likely to make to make a catastrophic mistake than we are to be attacked by a quantum adversary. like implementing a scheme that hasn't been battle tested. Is that sort of what you're saying?

>> Let me give you an example. Let me give you an example. So, so let's just say this is a hypothetical situation. Although somebody did just come and tell me about this. So, let's suppose you want to transition your company to postquantum security. Well, today you're using hardware to sign to generate your signatures. Yeah. So, these are called HSM. So, your ECDSA orn keys are in HSM. Uh and the keys are protected by the hardware. Make sense? So if somebody attacks your infrastructure, they can't steal the key because it's protected by the hardware. Well, these HSMs don't support postquantum signatures. They don't support MLDDSA and Falcon and all the other uh postquantum signatures. So what are they going to do if they want to transition now to postquantum signatures? They only have one option,

which is let's take the key out of the hardware and put it now on a regular CPU and generate signatures on the regular CPU. >> To me, that sounds like a step in the wrong direction. >> Oh yeah. >> Yeah. Because now you are more likely to be attacked by a regular hacker than by a quantum computer. >> Wow. >> Okay. And so to me the right course of action in this kind of decision procedure, decision environment is don't take your keys out of the HSM. >> You should instead lean on your HSM provider to support postquantum signatures in their HSM hardware. Wait for them to update their hardware, buy the new hardware, and then do the transition. This is why setting the deadline to be 2029 is a good idea cuz you can go tell your HSM provider, hey,

we want to transition by 2029. You got you guys got to get your act together and give us better hardware. >> Again, most likely they'll miss the deadline. Yeah. But fine, we have a bit of slack. And so they'll move only once the hardware is available, but they're not going to put their security keys, their signing keys at risk by moving moving them out of the hardware. Yeah. And I have many other examples like this where there's a it seems to me like there's a bit of a risk in rushing this transition. We really should take our time. This is a very complicated and I'll say interesting process and we don't want to rush it and cause some catastrophic mistake.

>> Do you think that idea though that like some of the systems that like the proving systems I just think of like the ZK systems like >> yes there are the postquantum systems available but some of them are newer like they're cool but they haven't necessarily been used much. like would you prefer that we wait and have those be out in the wild battle tested before you implement them? Is that a concern as well for any of the new postquantum schemes basically? Oh, for any of the postconquer signatures, I think the the implementation of course there's always questions about bugs and implementation the honestly the implementation is kind of not the main bottleneck. The implementation is, you know, like we said, all the hardware that goes around it. Honestly, when you talk to people in industry who need to do, you know,

people in healthcare, people in government, people in finance, like not like the hardcore techies like Google and Cloudflare, like everybody else in the world that has to do this postquantum transition, the hardest thing for them is actually to find all the encryption code in their codebase. >> Oh wow. >> And that's going to take a while. people have to actually figure out where are we doing encryption in our codebase and then we have to replace it and then of course there's a question of what to replace it with. So all this stuff is going to take quite a while. Um and again my point is you know let's not rush to avoid a catastrophic mistake that's much more dangerous than actually being attacked by a quantum computer.

The third point I want to talk about is what do we move to? So what postquantum systems do we want to move to? And I have a lot to say about that in the blockchain space. Let's just say that um core blockchains seem to be moving in the direction of hashbased signatures. >> And I want to kind of you know rattle the cage a little bit and say that we I I would like to make an argument for considering more algebraic based signatures rather than just hashbased so that we don't lose many of the properties of algebraic based signatures.

>> What is an example of an algebraic signature? >> Oh yeah yeah yeah for sure for sure. So you know the algebraic postquantum systems the of course the the prominent ones are the lattice based ones and so yeah we should obviously be considering the lattice based systems there there are a couple of others maybe we'll talk about them in just a second the the reason I'd like to kind of make an argument from for algebraic based systems is they have a lot more structure than the hashbased systems and the structure actually lets us do a lot of things that we can't do in the hashbased world yeah so there's a lot of room for innovation maybe just to mention a couple of things like in the Bitcoin world is what what are called adapter signatures. That brilliant idea is possible because of the algebraic structure, threshold signatures,

distributed key generation, hierarchical key derivation, all these things are possible because of the algebraic structure. And uh if we just stick to to hashbased signatures, we're kind of be essentially cutting off a lot of the innovation that can happen with with with digital signatures. >> So again, we'll talk about that in just a second. And the last for the last point that I'm I'm hoping we'll we'll get to is a couple of cute ideas. The Google paper has a number of really cute ideas in it that actually I'd like to talk about. I don't know how many people actually read the Google paper. >> You said when we started and I was like oh yeah I I didn't I read and there actually I'd say there's a couple of good really cute ideas in particular there are three ideas that I wanted to to talk about. Um and so yeah so those

are the four points I wanted I I was hoping people to can take away. the timeline, don't rush, uh, algebraic signatures and, uh, cute ideas in the Google paper. >> Very cool. So, we did, I mean, we started in on timelines, the 2029. You're saying, don't put too much weight on that. There are folks in our community who very much disagree with these early timelines who who say, why are we really worried about this? Like, it's still so far off that this would become relevant threats to like spec specifically like ZK systems. So why are we all of a sudden scrambling to try to make these postquantum systems? I liked actually it was really good clarification that 2029 is more from the

security side. This is sort of like giving buffer time but still what is the timeline that is predicted and I know you kind of are saying there is none but is are we thinking 10 years? Is there any sort of ballpark? >> Yeah, I I knew you're not going to leave me alone with the timeline question. Everybody just wants to know the timeline. Look, the the reality is this is something that's coming. When exactly it's coming, we don't really know. I I I would say just given, you know, I've been talking to a lot of the teams that are building this stuff and there are a lot of challenges that they have to solve to get to where they want to get to. And so we can talk about some of those challenges. Saying that it's going to be that the computer will be the

shore computer will be here by 2030, it's very unlikely, >> very unlikely. But when you stretch it out to 2040, that's when it's starting to feel kind of uncomfortable. >> Oh, okay. >> Yeah. And so again, this is if you force me to say numbers. Yeah. The answer is it's n years away for an unknown value of n >> but not 50 years. You don't think? >> Okay. You know, here I have to say that one of the most depressing statements that I'm really scared of, which is at the the the honest answer is we don't even know today. We don't really know that this is at all possible, >> ever going to work. Oh, wow.

>> The Now, it's very likely that it will. All the physicists promise me that the physics is sound, the architecture is sound, the engineering is sound. It likely will work. >> But then there are physics papers that say, well, who knows? Maybe there's kind of a misunderstanding of quantum mechanics and there's some reason why the universe is preventing us from from implementing these these computers. I don't believe that. I believe we are going to get there. But I'll say the most depressing thing to me is we do all this work to transition to postquantum systems. We pay the penalty of moving to postquantum systems which are much worse than the pre-quantum systems.

>> Wow. >> Not to mention that we have to move away from BLS which kind of breaks my heart of course and then we wait a 100 years and there's still no quantum computer. Then we're going to then we're going to look really really foolish, right? I mean then then then this is the most depressing thing that that can happen unless there's one silver lining unless by trying to build this quantum computer and failing we learn new quantum mechanics and all of a sudden >> all of a sudden you know the new physics that we learn from that is going to give us unbounded energy or whatever. Yeah. So there is a silver lining which is great. I don't believe we're in that world. I believe the quantum mechanics is sound. I believe the engineering is going to get us there. So I believe we

will have a quantum computer uh eventually. When is I should say I'm amazed at how divisive this topic has become. That is really surprising to me. Again it's to remember we don't know the number n. It's n years away and we don't know n. So somehow the value of n has become like a crazy divisive question. Yeah. Is it is it 5 years away? Is it 10 years away? Is it 100 years away? Everybody has opinions and they feel very strongly about those opinions. about the ants. The truth is we don't know until it's built. We won't we we we won't know. What's the other interesting thing is the implication of all this. So like I said, I believe this is coming.

This will happen again for some value finite value of N. I don't want to commit to an end, but for some finite value of N. What's interesting is, you know, the Bitcoin world, Bitcoin in some sense, its strength is that it doesn't change. And here we actually have something that's going to force Bitcoin to change. So, you know, there's a lot a lot of in the Bitcoin world, there's a lot of resistance to this idea. Yeah. That, you know, we don't like change and here we have to do we have to change something. >> So, that's causing a lot of a lot of tension in the Bitcoin world. Of course, let's not even talk about what to do about abandoned assets. That's like a whole other a whole other question that's uh that's causing some issues.

But let's go back to the timeline issue. >> So, I I think it is useful to kind of help maybe your the audience understand a little bit about what's happening. So right now there are kind of two leading architectures for building a quantum computer. Yeah. One is based on what are called superconducting cubits. >> This is more traditional VLSI. These are complicated experiments to do. This is the approach that Google, IBM, Regetti, all those companies are following. These are expensive experiments. You have to have you have to cool everything down to close to absolute zero. These are complicated experiments to do >> and and basically every time we hear or see these quantum computers with all of the wires, this is the kind of quantum computer that we're talking about. The super conducive Yeah. It's like

>> super conducting cubits. What you're what you're looking at is basically a fridge that has to cool everything down. >> Yeah. Uh the other approach which is more recent and super exciting and probably you know people now think that that's probably going to lead take us there first is what's called the neutral atoms approach. Neutral atoms. >> Yeah. >> So yeah. Yeah. You're right Anna. It's very closely related to this. So what's interesting about neutral atoms? Let me just say that building these computers basically take three components. Yeah. There's a laser. There's optics that split the laser beam into like let's say 10,000 traps depending on how many cubits you want. And then there's a vacuum chamber where the traps actually live in. It's kind of interesting why you need a vacuum chamber. You're you're

using the laser using these beams to trap atoms. And you you need a vacuum chamber to make sure that like other atoms in the environment don't just come and knock the atoms out of the out of their traps. Yeah. This is why you need a vacuum chamber. Uh now interestingly these are much simpler experiments to do than the superconducting cubits. You don't need to fabricate maybe you don't need to fabricate complicated as6 and so on but and the result there there are many startups they're actually following the neutral atoms approach. In fact there's even a lab at Stanford that's now building like this summer just one professor is building a thousand a neutral atom uh experiment.

>> Cool. Who is that? >> That's professor Choy at Stanford. >> Okay. Okay. because we had Yelina Vokovich on the show last year and I want to just understand where her research fits in this because hers was very much to do with light and photons. >> It's all related. >> So, is that in the same kind of category as this neutral atoms? >> Oh, yes. Yes. Yes. The photonics people are super super happy about this cuz now all of a sudden this is all about splitting a laser beam into a whole bunch of other beams and moving those beams around. >> So, what's interesting is again because these are much easier experiments to do.

There are lots of startups that are going down the path of of neutral atoms. What I wanted to stress is though these are the two architectures are fundamentally different architectures. So let me just explain why that's so. So superconducting basically you have local connectivity. So only closed cubits can interact with one another. >> Whereas with neutral atoms you can kind of move them around and have them interact with one another and then move them back into their into their locations. Yeah. So you have much better connectivity with neutral atoms which gives you more flexibility in the type of algorithms you can implement. But because you have to move things around neutral atoms are a lot slower than superconducting cubits about a thousand times slower.

>> Oh okay. >> Yeah. So in the Google paper the the claim is if we build a quantum computer using super superconducting cubits amazingly their estimate is that ACDSA can be broken in roughly 20 minutes. >> Okay. But wait, just one one double check because I think the way you just said it was neutral atoms was slower. >> Slower. Yeah. Okay. So with superconducting with superc conducting the estimate is ECDSA in 20 minutes. >> Yeah. >> With neutral atoms the Caltech paper basically estimates about 10 days to break ECDSA. >> That seems counterintuitive because you're thinking like light versus material. But >> No, no, no, no, no. I think you're thinking about a different approach. The neutral atoms approach is actually atoms. The light is used to trap atoms.

So the cubits are actually held the information is actually held in atoms. >> Okay. >> Yeah. The photonics method is a very different method for doing quantum computing that I'm not that I'm not going to talk about. >> Okay. Okay. >> And I by the way I should I should mention the Google paper came at the same time as a Caltech paper was published by Dov and and others. They're experimental physicists. In fact they have a their own startup called Oratomic which is super exciting. Also building this stuff and they're actually quite along quite far along. It's really quite interesting that like in uh what is it last year Dolv published this paper showing an experiment with 449 neutral atoms where they actually implemented 27 gates. Yeah. They actually ran a 27 gate circuit. They implemented quantum error

correction. They literally showed that all the components that are needed to work actually work. So now they all they have to do you know all in big quotes. All they have to do is just scale that up to something like, you know, they they claim 26,000 atoms, more likely even more than that, but just, you know, we're going from a couple hundred to a couple thousands. I mean, tens of thousands. >> So that this is why we have confidence that this is coming >> because it's no, it doesn't seem out of the question. And they're claiming that they're going to do the scaling pretty quickly. So then we'll see. And and then what's interesting is also their papers literally talk about the design, the architecture for the computer. you know, we're going to have memory here, we're going to have compute over here, we're going to have IO over there.

>> They literally kind of laid out the architectures for a computer. It's called a threezone architecture. >> And it all seems to be coming together. So, the other thing that might people might worry about is can we keep these computers in coherence? >> They have an experiment where they actually kept the computer in coherence for 2 hours. It didn't do anything. It just sat sat there. But it actually maintained coherence for two hours using this trick called repl replenishing of atoms. Uh and so yeah the components are coming together. This is why this is why people need to pay attention to this.

You know it's I like to say you know don't panic, don't rush, >> but you can't ignore this stuff. This this these experiments are scaling. >> There was like big a big aha moment like a year or two ago where quantum error correction was shown to work. the physical cubits were getting were getting better and better and so yeah this this stuff is coming. when thinking about these kind of quantum computers, something that I and you just sort of mentioned it. I kept thinking before I started to dig into it that quantum computer was like a single thing that you would have a computer the way we have a computer but it would be a quantum computer. But what I understood is it's like it's a comp it will probably be like a component like it there's no memory in a quantum computer as far as I understand right and you

need you need like the other pieces of a computer as we understand it and then the quantum could be like one element is that correct is that sort of how we have to envision like a future version of a quantum computer and the second question is could we ever have one in our house? Yeah. Yeah. Yeah. I think I think that's a bit of a simplistic simplistic view. I think you can think of the quantum part of the computer as literally a physics experiment. >> Okay. >> Yeah. It's an experiment that helping that's helping a classical computation. >> Ah.

>> And so what's interesting actually this is one of the things I was going just going to talk about is a quantum computer actually is driven by a classical computer. So there's a huge classical computer that's sitting on the side and actually driving the quantum experiments. >> Okay. >> Yeah. So it's telling the quantum computer literally what it's doing what the classical computer is doing is it's telling the the laser beams where to go. Yeah. So it's kind of moving things around. It's uh turning on lasers on and off. It's doing uh measurements and so on. So everything is orchestrated by a classical computer.

>> Is it also taking the result and then interpreting it? Not only that, it turns out for the ECDSA attack algorithm, there's a huge classical computation that has to happen once the quantum experiment is done. Yeah, we're not Yeah, we we do the quantum experiment, we get some results, we're not done now. We have to do a big classical computation to actually get the discrete log. And I actually love to talk about that a bit more. >> So, you asked, are we going ever going to have one in our house? It's interesting. So when I talk to the physics folks that do neutral atoms experiments, their claim is that the size of the computer is about the size of a garage.

>> Still a little big, but not that big. >> Well, you have to remember classical computers used to be the size of a building. >> True. >> Yeah. It took a while. You have took a while for things to miniaturaturize. And so, you know, just the first generation quantum computer is going to be quite large. And then, you know, then who knows? >> Wow. >> But the fact that these things are running, they could run actually at room temperature. Um well maybe they have to be cooled a bit but they do but they don't have to be cooled too much. I mean this this technology is actually coming as a it's kind of important to understand actually this is I got conflicting answers here. One neutral atom team told me that everything they're building is off-the-shelf equipment like okay it's just putting it together which is really hard writing

writing running the classical computations is really so that's just building it is hard but everything is offtheshelf >> components and another team told me no we're building custom components so I can't really tell if it's if it's really just offtheshelf or or or custom but the point is these experiments are not that difficult to build and we have a lot of of uh startups that are actually going after that the main challenge in building these computers is dealing with errors. Yeah. So these are atoms that are interacting with the environment. They constantly do things you don't want them to do like they they you know there are these gates that get applied to them that you don't want applied to them and so you have to fix errors. Yeah. So the whole game here is how to get how to

reduce errors and there are three approaches that people use to reducing errors. One approach is to build better physical cubits. So more accurate physical cubits and the experimentalists have been working hard on building better and better and better physical cubits to the point okay to the point where they're now they've gotten so good that the second approach kicks in which is error correction. This is what's called quantum error correction. So we build we encode the entire computation in an error in a quantum error error correcting code and then the error correction code error correcting code allows us to recover from errors in the physical layer. Now the physical cubits have gotten so good that now quantum error correction can kick in. This was what was so exciting about the Willow

experiment back in in 2024. They got the physical the superconducting physical cubits to be so good that they could demonstrate that error correction really works. >> Okay. >> So that was that was cool that the that we can demonstrate the error correction works. Since then, as I said, this 449 experiment, they actually also demonstrated error correction across 27 gates. And so that works. The third way to get to reduce errors is to shorten the computation. Right? The longer your computation, the more errors you accumulate. So the third way to to reduce errors is to simplify your algorithms so that the algorithms run the computer runs faster and as a result, it accumulates few fewer errors.

The Google paper is in this third category. Yeah. It's a way to reduce the length of the computation so that you don't need as strong as many cubits to correct for errors. >> Okay, >> so hopefully this places things kind of in perspective. So the Caltech paper, the new Caltech paper is about better error correcting codes. There's a lot of papers on trying to build better and better physical cubits and the Google paper was about shrinking the computation size. Yeah, the computation length so we don't accumulate that many errors. >> So these are not competing basically research. This is complimentary.

>> Totally complimentary. These are three complimentary approaches. By the way, let me tell say one more thing about quantum error correction. This is a really cool area. So quantum error correction is all algebra. And if folks who are like into algebra stuff, you guys should start working on quantum error correction. This is such a cool it's a purely algebraic question. What's interesting is it turns out the way these these experiments work is you let the quantum computer work. meaning you kind of direct the laser beam, you move the atoms around, you make them interact with one another and so on. And now you need to do error correction. Well, how do you do error correction? Well, you measure and then based on the measurement, you take some other actions. Now, it turns out that calculating what's called the decoding, calculating the actually applying the

error correction code to the computation that turns out to be a massive classical computation. Just to give you an example, the Oratomic team, they were saying that their gates will operate at let's say 1 millisecond per operation. >> But the time it takes them to run the error correction is a few seconds per gate. >> So the classical computer is holding back the quantum computer. >> Oh wow. >> Which is really interesting because of this actually even Nvidia got into this game. So they Nvidia, you know, they their eyes lit up. They said, "Wow, there's a big computing problem here. We have computers, right?" And so even Nvidia built kernels. They have now GPUs that whose whole purpose is just to do quantum error correction.

>> Wow. >> Yeah. So, it's kind of cool how the industry is coming together. >> Oh my gosh. >> To make all all of this work. So, like for your listeners who like algebra, you don't you don't have to be a physics experimentalist to help in this area. >> Go work on quantum error corruption codes. They're so they're so cool and there's so many open problems to work on there. >> So cool. I did not know the NVIDIA connection though. That's I mean this is just sort of like if if this AI experiment doesn't work there's always quantum right >> that's right that's right your your podcast could could turn into a quantum error correction podcast I'm I'm just kidding stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick stick with your knowledge >> okay should we dive into the algebraic

signatures now that was I know one of the points you wanted to cover >> oh yeah I have I would love to talk about that but actually first can we maybe talk a little bit about the Google paper I think there are some there are some cute ideas in the paper that I just want wanted people to to be familiar with and so yeah we can do that we can do that briefly yeah so let's see so let's start first of all with kind of the elephant in the room which is a zk proof >> so what is the zk proof what did the proof actually prove >> yeah true as I understood it it was like the algorithm that they had discovered some like kind of what you were talking about reducing the computation now I kind of have bit of a better context

they didn't want to release the algorithm and so they used a zk to prove that the algorithm did what it that it did without revealing anything else. >> That's exactly right. But let's let's give a bit more detail here cuz I think it's kind of interesting. >> So when you look at Shor's algorithm to compute discrete log, the hardest part of the algorithm surprisingly turns out to be a classical computation. Yeah. And let me tell you what that is. The hardest part of the algorithm is basically you are trying to compute the discrete log of say h base G. So H and G are two points on an elliptic curve.

you're trying to comput the street log of h base g. The hardest part of the algorithm is computing x * g + y * h for certain integers x and y. Okay. Okay. So that's just a classical computation that the quantum circuit has to implement. And what we want to do is basically come up with the shortest possible circuit, the fastest possible quantum circuit to do this classical computation. And so what the Google paper does is basically it discovered a better algorithm to to do this classical computation. Yeah.

Simple. X * G plus Y * H. >> I want to point out that that computation if you if you think about it a little bit and it's actually we explained it in the paper. It turns out that computation is literally just 28 elliptic curve additions. 28 elliptic curve additions. So the whole thing that the hardest part of Shor's algorithm is computing 28 elliptic curve additions. >> Okay. >> Yeah. Amazingly. >> Okay. So what what the zero knowledge proof shows is that there exists a quantum circuit that given two elliptic curve points will add them up using only what is it 2.7 million quantum gates.

These are called tofly gates. So it's a it's a classical computation that is implemented using quantum gates and correctly implements elliptic curve addition. So they have this quantum gate simulator it's called kickmix that uh that they've built >> and they loaded their circuit into kick mix and the proof actually shows that the circuit that they loaded the the circuit is the witness. It's the secret data. >> Okay. They ran the simulator inside of the inside of the ZKVM and the simulator said yes, if you use this circuit that was loaded to add up 9,000 random points, it does the job correctly.

>> Okay, >> so that's what the proof proves. >> I now am so the reduction of the computation that Google found or this algorithm does. Just to be clear, this is not like you know you talked about how there's the classical computer and then the quantum computer. Where does this live? Does this live in the classical computer interacting with the quantum or is it within the quantum computer itself? >> Yeah, it's all it's all kind of uh together. So what happens is you know you implement your quantum circuit. The way for example to do elliptic curve additions, the way you implement your quantum circuit is by having the classical computer look at the individual gates and for each gate it tells the classical computer tells the

photonics that you know the optical apparatus to behave in a particular way. Yeah. You know move the beams there, move the beams here depending on on what the gates are. So you literally go gate by gate and then the classical computer basically programs the optical apparatus to do the right thing. >> And the quick mix is a simulation. >> Kick mix. Yeah. That's a so that's a simulator >> that basically loads the description of a quantum circuit. >> Yes. >> And then basically if it's a if it if it's classically simulatable, which in this case it is, it goes ahead and simulates it and checks that it did it did the right thing.

>> I see. And so the ZKVM and the proof was kind of both sides. It was like that if you use this on the tra sort of traditional computer side of things within the simulator that you will get the outcome that you're looking for. >> Exactly. Exactly. So the the ZKVM literally executes the technics quantum circuit simulator. >> Cool. >> Which circuit is being is executed? That's the secret witness which is kind of loaded into the simulator and shown to run to run correctly. So that was a ZK proof. Now there's an important lesson here which again is important for your audience to hear which is ZK uh so the kickmix simulator was built as an in-house tool. It was never designed to operate in adversarial environments.

>> Okay. >> And as we know ZK circuits have to work in adversarial environments because the attacker is going to try to forge a witness. So to do this as you can imagine this was a pretty massive computation they had to use to use GPUs and all that to generate this proof. And so when they translated their kickmix simulator to Rust so they can run it inside of a ZKVM, they tried to simplify the code. And one way to simplify the code is they removed some checks. >> Ah >> well the minute you remove checks there's a way for an attacker to load a fake witness a fake circuit >> that would do the same thing but doesn't actually is not a valid quantum circuit.

>> Oh >> and so yeah so the trail of bits guy >> this is what I was going to ask cuz I heard about >> yeah yeah this is this is really important to remember. backward. I mean, the way they described it was that they almost like unraveled this secret because of the change, I guess. >> No, no, not unravel the secret. What what Keegan Ryan at Trill Vitz was able to do, he was able to basically write down an invalid quantum circuit >> and still have it >> that the simulator would just ingest and run >> and confused it into thinking that it did the right thing even though it's an invalid circuit. >> Because this is not the actual simulator. like the actual simulator that's in house was not put into it.

Okay. >> Yeah. So basically, you know, the simulator had to be fixed and had to include all these extra checks and by the way the Kean Ryan did phenomenal job there. So >> kudos to kudos to him for for doing this work and yeah then the proofs were quickly regenerated. This within like a day or two the proof were regenerated. So it's okay that now the the ZK proof is correct. I see. >> There's an important lesson here to remember is, you know, when implementing ZK proofs, >> you have to make sure that the circuit you're running in inside a ZKVM or the program in a ZKVM is bulletproof. >> Yeah.

>> Yeah. It's secure. The other point I want to make is I had hoped that, you know, I'm I'm a re I'm a researcher. I like open academic research. I would have actually been happier if the circuit had been made public. >> Yeah. >> And so I think now there's a challenge for our community. You know, go and download the kick mix simulator. It's actually pretty simple. It's not It's pretty easy to use and figure out what the circuit is. Yeah, somebody should This is like like a great puzzle. Go figure out what the circuit is. >> Yeah. All you have to do is figure out how to add two elliptic curve points using tole gates. Yeah, that's it.

>> Do you know why they weren't able to release it? Like why did it have to be proprietary? >> Okay, this is this is this is a good question. So, what I'll say is this. Let's just say that Google operates under certain constraints >> and their only option was either to make this discovery and say nothing >> or to make this discovery and prove it in zero knowledge. Those were the only options that they could do under the constraints they were operating under. And this actually brings an important point because they often say that uh in fact when I talk to the other companies that are building this stuff they often say that at some point you know this de this progress might actually happen not under the public eye. So you know it

could be that like we get to 2035 and for some reason let's say after 2030 >> we don't hear we don't hear any progress in quantum computing but a lot of progress is being done. It's just not in the public eye. And that actually something that is quite concerning. That is something we need to be worried about in that the fact that we're not hearing about progress doesn't mean that there isn't progress being made. To me, that is I have to say that is quite heartbreaking. And not only heartbreaking is there's a a bit a bit of risk in it in that, you know, I >> one country could get it before other countries. For example, >> I I'll say it more maybe more poetically in that there's a possibility of a quantum Silicon Valley emerging. We want quantum Silicon Valley to happen in

California, not elsewhere. >> Okay. >> Yeah. But if California companies don't talk about their progress, then it's probably going to happen elsewhere. >> Oh, yeah. >> So, there's I think there's a policy aspect there as well. I hope this is all developed in the open and and that at least we we know about the progress that's being made and the progress is not is not kept in the dark. >> Oh yeah. So that was only one idea. Okay. >> So much for being so much for being brief. Yeah. So much for being brief. The the other you know maybe I'll just quickly mention one other idea there.

It's very cute actually. I really like this idea. So remember I told you that the hardest part of Shor's algorithm is computing X * G + Y * H. >> Okay. Now, interestingly, in Bitcoin, for example, G is fixed forever. >> G's doesn't change, but H is actually dependent on your on your public key, on your Bitcoin address. >> Okay? >> All right. >> So, really, you can you can compute X * G ahead of time. We call this priming the computer. >> And then once the public key becomes available, all you have to do is compute Y * H. So, in some sense, this is like an easy factor of two speed up. So that when you reveal your public key now the algorithm can run twice as fast to

compute discrete log of the public key. Now there's a really bizarre coincidence there in that with superc conducting cubits I said it takes 20 minutes to compute elliptic curve discrete log. Divide that by two now it takes 10 minutes and what is 10 minutes? 10 minutes is the bitcoin block rate. >> Okay. So that has all sorts of implications to what are called uh online attacks that as soon as the public key is revealed immediately the attacker can kind of try to run the discrete log algorithm if the computer is primed they might be able to break it in 10 minutes and then >> you know >> what would that mean though? Would that mean like before the user even can notice before the minor can even like what what would that actually mean?

>> Yeah. Yeah. What okay this is again we're going into Bitcoin land here. What this means is that the user submits their transaction to the memp pool. >> Yes. >> Before the transaction is is included into a block, an attacker could break the discrete block, issue a competing transaction >> and and move that into into the block. >> And this is the concern. I mean, just going back to like sort of why this matters to the Bitcoin folks is >> okay. This is this is one concern. >> Okay. >> Yeah. This this this basically would mean that putting transactions in a memp pool in Bitcoin is going to be risky when this happens. If this happens, probably that would mean that people would stop putting transactions in the meool. Yeah. And they'd have to move to other methods unless Bitcoin actually

adjusts and moves to postquantum mechanisms before then. And of course there's a now there's a lot of discussion in the Bitcoin community on on how to do that. Exactly. >> For sure. And we actually we had project 11 on some time ago who talked about exactly that migration path and the challenge of doing of basically getting everyone to change sort of to to upgrade their accounts to upgrade their signature schemes basically and how unlikely or hard that would be to do on mass in a decentralized place. >> Yeah. Actually, I have to say this is kind of one of the reasons why, you know, I say don't panic, don't rush, but don't ignore in that, you know, we need to take our time to decide what to do.

>> But we also need to give people, I don't know, a couple years to actually implement a transition. And so again, if we start now, let's say by 2030, we finalize our plans, we give people five years 2035 you know, that kind of gives us a bit of a bit of comfort zone. you know, if we all the timelines get pushed beyond 20 240, >> you know, now we're kind of getting into uncomfortable territory. >> Have you tracked what lean like the lean Ethereum work and what I mean Justin's a co-author on there, too, so I know you guys are definitely in touch.

>> Beautiful work. Yeah. So, the Ethereum community is they're they're actually taking pretty aggressive steps to to, you know, address this issue. Really interesting stuff. So all their lean VM, their lean signatures, their ve very very very cool ideas go into that. So I'm quite excited about what they're what they're doing. >> Nice. Yeah, we did a a six-part series that I'll link to in the show notes, but if anyone wants to hear more about what they're working on in their case, like the this 10-minute issue, like it's different, right? It's not >> Yeah. Yeah. It's not It's not It's far less relevant to to Ethereum.

>> Got it. Dan, did we cover all three points, all three cool ideas from Google? >> Yes. Actually the third one I think we already we already talked about the fact that these superconducting cubits might might break discrete log quite quickly. So the third one we we we talked about. So yeah. So that's kind of the one of the points in the Google paper. There's a couple of other ideas there that maybe I would ask people to maybe just read the paper >> actually read it not just put it in an LLM and get it summarized. >> Exactly. Exactly. >> Okay. >> Let's sort of return then to the algebraic signatures. this I mean you had sort of highlighted one like the lattis based work and we've actually covered that a fair bit >> here you're talking about potential

postquantum signature schemes right like so things that you would want to migrate to and this is this is the part where I guess because I come from zk land this is the part where I feel most sort of security fearful because these new systems are so new like if you want to start an implementation like you have to know it. First of all, it won't happen overnight and yet you need to start at some point. So kind of like at what point are these systems battle tested enough that you would feel comfortable doing a migration of this level?

>> My god, Anna, that is such a great point. So So let's let's let's discuss that. I think that's a really important point. I think the question you're asking is this. So we have hashbased signatures which are just based on hash functions. Which hash functions is an interesting question in its own right. Maybe we'll talk about that a bit more. These hashbased systems also they're not so simple. Yeah, I mean it takes a bit of work to implement them and there could always be bugs. Who knows? These libraries might not be battle tested enough. Bugs are always a threat. And then we have algebraic signatures.

Lattice signatures are an example of the algebraic algebraic signatures. And I think the question you asked is great like how do we know that these latt signatures are >> quantum secure? >> Yeah. >> Right. Maybe we do all this work and then it turns out they're not quantum secure. In fact, like a year ago, you know, there was actually a paper claiming to break all this stuff, quantum algorithm >> to break all this stuff. Turned out fortunately turned out to be incorrect. But yeah, these are new relatively new questions and how do we know that these things are secure? So my answer to this is first of all as we said algebraic signatures have a lot more structure that enables a lot more innovation like threshold signatures and distributed key generation hierarchical key derivation all this innovation that happen with

algebraic properties of the signatures. >> Mhm. >> So I think your question though is exactly right like how do we know that these things are secure? How do we know that we're not going to harm security of the chain? So the answer to that is actually quite simple and this has already been deployed. The answer to that is what's called a hybrid signature. Okay. >> So what is a hybrid signature? You literally take ECDSA >> as you do today and you concatenate it to a lattice based signature. So you do both. >> So you get both secure. You get sort of the security of the the first even if >> is that >> I would say I would say it is you're provably not degrading security. Okay.

You're at least as secure as ECDSA. >> Okay. >> The reason this is not a crazy proposal is because these these lattisbased signatures are pretty big. Even the the the weak falcon one is over over 600 bytes. So ECDSA is like you know 30 you know under depending on the encoding let's say let's say 32 bytes or under under 60 bytes or so. And so it's not a significant fraction of the signature size. So adding tacking on an ECDSA to a lot of space signature is not that expensive >> from from a space point of view.

>> Okay. I see. I'm I'm surprised that the security follows over though. Like I thought maybe by combining them you degrade the security but you're saying you don't. >> No, no, no. The attacker has to break both of them, right? >> Okay. >> So the point is before before a quantum computer is available, you're as secure as ECDSA and after a quantum computer is available, you know, ECDSA is no longer relevant, but at least you have your your your quantum signature to to fall back onto. >> Okay. So, so this argument, the security argument against these algebraic systems, I think is a valid argument, but all that means is that we should just deploy them in hybrid mode. And I should again, it's very important to understand that this is not a new idea.

The internet has already transitioned to postquantum. You know, the the the communication between you and me right now >> is already postquantum secure. >> I didn't know that. >> And is it but isn't it is it hashbased or is it >> No, it's not h it's hybrid. >> It's hybrid. So actually the communication between you and me right now is protected by elliptic cryptography and lattice cryptography >> together. Yeah. So even the the web you know Google and cloudflare and all those folks they were too afraid to just deploy lattice cryptography by itself. So they went with a hybrid system which is the right thing to do and it's not unreasonable to say also that the blockchain should follow that approach as well. Now, what I see in a lot of a lot of chains, what they are starting to do, or some chains, what they're

starting to do is they're giving people a choice. You know, you can kind of sign using multiple signatures and we're going to let you choose which combination of signatures you want to do yourself. You know, if history has told us anything, this is a massive foot gun, right? Developers will will get this wrong one way or another. Users will get this wrong one way or another. It's much better to sort of enshrine a signature scheme that by default, by construction, by design is a hybrid signature scheme that does both both signatures. >> Interesting.

>> Yeah. Again, this is like my my opinion. I'm not, you know, of course engineers are are free to do whatever they choose, but this seems like a safe way to go. >> Cool. I have two questions. One is both are a little bit like outside. One is when were the lattises deployed on the internet? Because I actually just didn't know that. So I'm curious like what era are we talking about? Like the '9s? >> No, no, no, no. Heaven forbid. More recent. No, no, no. The the the first Oh, wait. So the Google did the first experiments like if I remember correctly in the mid2010s.

>> Okay. >> And then Chrome adopted this is the name for the cipher spec is 2559 MLM. Um, if I remember correctly, Chrome adopted that in the LA I want to say in the last 2 years. I'm not 100% sure. >> And then Cloudflare had to adopt it as well cuz you need both the browser and the server to adopt to adopt it. And so they did that as well. And yeah, these days when you look you I mean I I wish I could bring up a window here and just show you. >> It's a hybrid. Yeah, it's it's a hybrid scheme. I wonder like if there's ever new schemes that come out. Well, we just have like hybrid three-way like the all of the different kind of cryptographic systems layered on top of one another.

Okay. >> This this gets expensive. >> That's a limitation. >> Yeah. Yeah. Yeah. The interesting thing is lattice signatures are kind of already big. So tacking on an ECDSA is like, you know, it's like taking a bus and tacking on an ant to it. You know, it's not it's not doesn't add that much to the overall length. >> Easy. >> Okay. Maybe not an ant, but you know, a football. >> Okay. Something that won't weigh it down. >> Yeah. Something that won't make it that much longer. Exactly. >> Makes sense. Okay. The other question, and this is quite out of left field possibly, >> as you were talking about these things, so you Yeah, we were talking about security. I mean, what kind of flashed in my mind were like isogynes? This is I'm just curious like we're first of all we're or are isogynes postquantum and as

far as I understood like there was a lot of work in that direction but then I don't know if it's paused or if it's sort of like there was some you know some fundamental thing seems to have been broken around it. >> Okay. So you know I'm going to zoom out just for a second because I think I think there's it's important to kind of draw a bigger picture here. So remember we said don't rush the transition. >> Mhm. I think actually NIST rushed things a little bit and then they standardized their signature schemes a little too early, the postquantum signature schemes a little too early. >> So they standardized MLDDSA, they standard Falcon and they standard a hash standardize a hashb signature. Now since then now they realized actually that they standardized these things a little too early and so they have another call

for additional signature schemes. Yeah. And that's actually a process that's still continuing. >> Okay. And in that other call, there are other signature schemes, postquantum signatures that are being considered. >> And so, let me give you an example. So, you asked about isogynes. Well, that is actually one of the candidates in this additional call. We made it past round two. >> The scheme is called ski sign. And the cool thing about skis sign is it's really quite short. It's 224 bytes. So, remember pre-quantum signatures are like under, you know, under 100 bytes. would say 60 bytes depending on BLS or ECDSA.

Ski sign is 224 bytes. Yeah. So not that much that much longer. But there in that call there are other signature schemes. There's a lattisbased signature scheme called hawk that actually addresses many of the complaints on on falcon. So hawk is a pretty interesting signature scheme that would likely be added to the to our portfolio of postquantum signatures. And then there's a bunch of other signatures using other techniques that are also result in fairly long signatures. So you ask about ski sign, you know, should they be deployed today? It's a kind of a tricky question. I have to say I probably the the the general consensus is, you know, very cool, but probably we want to wait a few years for more cryp

analysis. The issue with keysign is twofold. one the key exchange version of of isogyny based schemes called psych that was actually broken very badly. Yeah, it turned out there was a classical attack. >> What scared us about this is that that classical attack was not based on a new theorem. >> There was already a theorem well known in the algebraic geometry community that just the cryptographers us cryptographers didn't know about and that theorem kind of applied and broke the the key exchange mechanism. Mhm. >> So the issue is isogynes use sort of very cool math. I I love this. It's very very cool math, >> but not it's not clear if the crypto community has yet absorbed enough of this cool math to be 100% confident that

there isn't another theorem lurking in the in the in the background there. And so we probably those are, you know, wonderful schemes. They're short. Maybe their performance is not as great as the lattice ones, but we probably need to wait a few more years. that it's quite a while before they actually get adopted. >> But yeah, but the other algebraic schemes like the like I mentioned the the lattice ones like including this new one hawk that's being proposed that's on this track to become a standard are are are quite interesting. >> As you're describing this, I'm just thinking about you know some of these new hacks or you know systems being broken all over the place as LLMs are starting to be deployed into this world of security. And I just wonder if we can like speedrun some of these battle

testing using that. Have Have you seen that emerging yet? Like have you seen audits or I mean ma like mathematical audits of some of these proposals yet? >> Yeah. Yeah. Absolutely. Of course. So, so you know l So, okay, fine. So, so we're we're switching I guess we made it this far without mentioning AI, right? Now, we got to >> we can't we can't I guess these days you can't have a conversation without talking about AI. So these new models a they they're great at doing proofs. So in principle one could take an implementation of these new schemes and try to generate a proof that the implementation actually ma matches the specification of the scheme.

>> And that that actually is a fantastic idea. In fact, I think the the area of formal methods is going to have a golden age right now >> because of that >> because these LLMs are so good at writing lean writing lean proofs and and and so on. So, interestingly, there's a connection to zero knowledge there. I don't know if you want to switch gears to talk a little bit about applications of zero knowledge here. >> Sure. I mean, the other things we wanted to cover on this show is proximity prize, but I think one of them was ZK and I AI. So, should we switch it around? >> Up to you. >> Let's do it. >> Driver. >> Yeah, let's do it. Let's do it. Okay.

Yeah. Yeah. Yeah. So, this question about using AI for a for writing code, B for testing code, and C for proving code. Yeah, >> all of this is all of this is happening even in the ZK space, right? I think you maybe you even had some guests who were working on on using LLMs to to find bugs and to and to do proofs. >> I mean, we did so we had audit we did an interview with CK security where they've created I mean this is last year so I'm sure it's very different now but they had created a whole team of security auditors using different LLM to check each other's work but that was really looking at implementations. What I'm thinking now is like what about these just sort of like the proofs or the where it's still sort of in theoretical

realm. It hasn't been implemented yet. And I don't know if I've covered that so clearly. >> Well, there have there actually have been stories about that too. I mean, it turns out LM are quite good at finding bugs in papers. >> Yeah. >> So, there have actually been a couple of stories now where where using people unraveled some incorrect uh statements and papers using LLM. >> Interesting. >> So, so that's pretty interesting. But let's talk about the first part you were discussing. So you know Mythos or MySOS however it's called has came out and one of the things that Anthropic says is really good at finding bugs. Yes.

>> So yeah. So I've been talking to a lot of my red teaming friends who do have access to mythos and apparently it is quite remarkable like you can give it very high level prompts. You know I've heard there's a zero day in this and that code. >> Go build an exploit and it just don't even find it. Just go build an exploit. >> Wow. >> And it just finds it and builds an exploit. It's >> pretty pretty wild. >> So, interestingly, what this means is, of course, overall it's kind of interesting. The press is interpreting this as bad news. I interpret as great news. >> Yeah. >> Yeah. Exactly. That means that, you know, when we ship out the proof system now, you know, we can use my thoughts to test if there are bugs in this proof system and make sure it's correct.

>> And in fact, people in the community have been doing that quite successfully, which is which is fantastic. What's interesting though is okay so let's say you're shipping some number theory library you can use my sauce to find bugs in it and and fix them so then when you ship it you know that it's correct >> the problem is in 6 months an is going to come up with the next model >> even more even smarter than mythos and it's going to find more bugs and 6 months later they're going to find they come up with the next model and it's going to find more bugs and so >> now we kind of have a bit of a problem in that we have to constantly keep running these models against our software and we to constantly be patching the bugs that they find. So when are we going to have time to write

new software? We're just going to be patching bugs all day long. And so because of this, one thing, one way out of this is actually uh by the way, I should say the these models can also help us fix the bugs. They're not just good at finding bugs. So you know, so they're good on both fronts. But one way out of this uh loop is out of this cycle is actually formal methods. Okay. >> Yeah. So when you when you build a number theory library, you can actually provide a proof that the number theory library implements what you expect it to implement. You know, when you need to do multiplication, it does multiplication correctly. When you need to do division, it does division correctly. So it doesn't matter how smart the LM model is, the library is guaranteed to work.

>> Yeah. >> Yeah. So that's what a formal method proof would do. >> Great. How do we generate these formal methods? These formal method proofs. Well, we write them in there a couple languages, but people we really we really like lean. So you must have heard that people write these proofs in lean and the cool thing >> we did an episode on this well we did an episode actually on program called acorn which >> oh yes yes I love acorn it's great >> it sort of is competing with lean >> acorn is a little bit a different level yeah but yeah it's a it's a pretty cool tool >> we talked about lean in that so we learned a little about it >> oh yeah yeah great great exactly so people write these proofs in lean to prove that the library works correctly >> interestingly the models can actually do

the proofs for you in fact the models can can actually generate the lean code that implements the library, prove that the lean code is correct, and then a compiler can compile from lean to C. So now we're guaranteed that as long as the compiler doesn't have bugs in it, the C code that we end up with is correct, >> should be good. So the implementation all of a sudden is good. Okay. >> Yeah. So formal method, this is going to be a golden age for formal methods and there's a not surprisingly there's a whole bunch of startups going down that that path. What's the ZK angle? >> Exactly. Where does the ZK come in? >> Cool. That great question. Great question. Okay. Well, these proofs that the code runs correctly, they're actually pretty long proofs. Okay, >> these are not simple proofs.

>> Ah, >> and so, well, >> proof of we have do do we have a tool to compress proofs? >> Maybe. >> Maybe. Yeah, these are exactly called snarks. Yeah, >> cool. >> So, that's one aspect where snarks come in. I can the LMS will generate this complicated lean proof. Now, we can run a snark on it. get it get a small a short snark that now whoever wants to run the code all they have to do is just verify the snark and not verify the original lean proof. >> There's another angle to it which is to verify the lean proof you actually have to have the source code of the library >> of the lean or of the original of the library you're trying to prove. Okay.

>> Yeah. Yeah. So if exactly if the code is implemented in originally in lean you would need that source code to verify that the proof that that implementation is correct. Well, the company that's send selling you the software, they might not want to reveal their source code. That's their proprietary data, right? >> And so now we need a zero knowledge proof to prove that the code that you are running came from certain lean code that does satisfy the specification. >> Wow. >> Yeah. So not only do we use snarks for compression, we also use snarks for zero knowledge to hide the original source code.

>> So we actually wrote a we have a system on this. We have a we wrote a paper on this. It's called ZK PI. >> Cool. This is with Alex Osdeir and and and Evan Loer. Um yeah, so I hope that people build on this is a cool application for zero knowledge proofs which is to prove that you have a lean proof of something both for compression and for zero knowledge. >> This is kind of a big this was a conversation on our last episode 399 where we were talking about whether or not like the ZKML story. I mean that started in our community in 2023 and there was a very spec like there was like two or three ways that we saw ZK being used to prove something about inference to prove something about output you know like I feel though now we've heard about more nuanced places

that ZK would exist like ZK like AI watermarking using ZK we have you know what you just described of like doing kind of like to keep part of something where the AI is accelerating it, but you want to keep part of it still still private and provable. >> Like for example, the source code, you want to keep the source code secret, but you want to prove that the source code satisfies a specification. >> That's interesting. Although I guess that could be for anything. It's not really an AI case. That could just be like anytime you want to keep your proprietary code private, which is kind of what Google was doing too with that paper.

>> Yeah. Yeah. Actually, so the Exactly. Exactly. So people have used this actually for for example for what's called a zero knowledge proof of exploit. Okay, >> suppose I have an exploit on your system. I don't want to tell you what the exploit is, but I want to prove to you that I have the exploit. >> Yeah. So, there's been a there's actually a whole DARPA program on how do we do zero knowledge proofs of exploit. >> Wow. >> And that that is a kind of a pretty cool application of ZK. >> I feel like sounds familiar. Have we tal I don't know maybe I've heard about this before, but it's good to hear again. >> Yeah. I don't know. So, the I would say that what Google did with zero knowledge is an example of a zero knowledge proof of exploit.

>> Wow. >> Right. We have a proof that we have a short quantum circuit. >> Yeah, >> we're just going to prove it to you in zero knowledge. >> Interesting. >> It's it's an example of a zero knowledge proof of exploit. >> Um yeah, and I guess the ZK male community has been very focused on on ZK for inference. >> Yeah. So, you know, that has a role to play to play too. That's kind of a more direct application of ZK. But I think there are all these other connections between AI and ZK. In particular, if the AI gives you a proof, you want to give a zero knowledge proof of the existence of a proof. And that is that is a a good area. You know that ZK is also playing a role in postquantum, right? That I'm sure you you know that >> we I mean that we we mostly have talked

about the postquantum ZK systems. But what do you mean like ZK in the lattice based stuff or >> Well, let's say that let's say that my ECDSA key was derived from some seed phrase using a hash function. >> Yeah. Yeah. >> Yeah. Using what's called BIP 32. when ECDSA. So the way this works is I use a seed phrase. The seed phrase is used to derive my secret key and my secret key is used to derive my my ECDSA public key. >> Yeah. >> When ECDSA stops being secure >> and you need to do a migration >> and you need to do well before you do a migration, I can't use my ECDSA private key anymore because the attacker has my ECDSA private key. So the way I prove that a certain asset is mine is by giving a zk proof that I know the seed

phrase that was used to generate the secret key >> because they don't have that like they don't have that >> the the part. Yes, I I think we did cover that once. Yeah. >> Oh, cool. Cool. Yeah, the hash function is postquantum secure. So going from secret key to seed phrase is something the attacker can't do. So I can still get control of my assets using these EK proofs. These ideas are kind of floating around and there was there was a paper from Miston that kind of um pushed this. I think actually originally this is due to some tweet from Vitalic like everything else in our field. >> Yeah. So yeah, this idea has been has been going around and maybe this is also a way to to do postquantum security in the case of a catastrophe.

>> Since we're on the topic of ZK applications in general, are there any other exotic ZK applications that you've seen? Like because just to give you a sense for what we've seen like ZKID is very developed. It's like now being integrated into all sorts of systems ZK private to private transfers private tokens that's sort of making a resurgence not necessarily like new concept there but it's definitely gaining some popularity. I feel like every time I have you on you you you and your students are working on some sort of edge cases. Are there any others that are on on your mind?

>> Edge cases. Thank you. No, no, no. I don't mean edge. I mean edge cases today that become really relevant. >> Mainream become mainstream later. Yeah. Good. Good. I like that. >> You're indie. It's the indie rock uh ZK applications. >> Yeah. Yeah. Yeah. Yeah. Yeah. Maybe maybe I'll mention I'll mention one. So, you know how how we always like to think out about kind of new new cryptographic primitives that we need. >> Well, I think even on the the very first time that we did one of these podcasts, I guess we talked about offiscation and IO. >> Yeah. I think that was the first time I ever heard about it.

>> Yeah. Yeah. That desperately needed in the blockchain space. We don't have it yet. Hopefully in the future. There's another one that actually is closely related actually offiscation and IO, but it's a little different. It's called witness encryption. Maybe I imagine many of your listeners have heard of witness encryption. So with witness encryption, what happens is I can encrypt to a public statement and you can decrypt if you know the corresponding uh witness. So let me give you an example. >> What's an easy thing? Let's say I can encrypt to a message and you can decrypt only if you know a signature on that message as an example. So the the the the statement that I'm encrypting to is I know a signature on a particular message and the witness for decryption would be the signature.

>> What I just said by the way >> is called identity based encryption. >> Okay. >> Um but witness encryption generalizes that quite dramatically. Let me give you another example. Suppose I can encrypt to a map >> a map some complicated map and you can decrypt if you have a coloring of a map such that no two countries have no two adjacent countries have the same color. >> Whoa. Okay. Some like characteristic of the underlying thing. >> Exactly. There's some some public statement and there's a there's some difficult to derive witness for that public statement. I can encrypt on a public statement without even knowing what the witness is >> and you can later decrypt if you know if you know the witness. This is called this is called witness encryption.

>> Yeah, it's a very cool concept. Oddly, I glad you say that because actually that had turned out to be quite useful in a lot of different areas. In particular, in the Bitcoin world now there's a bunch of applications for witness encryption. >> Of course on Ethereum there's a bunch of applications for witness encryption. So now you ask, well, what's the connection to zero knowledge? Mhm. >> Okay. Well, it turns out zero knowledge is a general tool for simplifying the problem of witness encryption. >> Really? >> Rather than proving to you that I know the witness for a statement, >> I can prove to you that I know a proof that I know a witness for a statement.

>> Okay. >> Yes. So, snarks to the to the rescue. >> Yes. So all so really to get what's called universal witness encryption, >> all I need to do is build a witness encryption scheme for a snark verifier. >> What would be a universal witness encryption though? What what does that mean? Like going back to our example, you you're kind of still talking about two people interact or two individuals. >> Right. Right. Right. So so suppose I want to be able to build witness encryptions for arbitrary statements or I should say arbitrary polinomial time statements. Yeah. So, you know, whether it's maps or signatures or, you know, take your favorite thing that you you want to encrypt to, I want to I want to be able, you know, I want to encrypt maybe to an Ethereum block. Yeah. So, you can decrypt only once you once you

know what the block is >> for for for example. Yeah. So, I want to encrypt to arbitrary statements. >> Turns out that that's if we had a scheme that does that, we would call that a universal witness encryption scheme. Okay. >> So, it allows you to encrypt to an arbitrary statement. >> Is it sort of general? >> For general. Yeah. Universal means general. Yeah. Exactly. Thank you. Yes. Maybe that's a better word. Yeah. Yeah. So we can do that in principle using a snark. So rather than proving that I know a witness for the general statement, I'll just prove that I know a witness for a sorry that I know a proof >> proof of a witness. But are both ZK? Are you kind of like proving a proof? Like is it ZK ZK hops?

>> No, it's just it's just once. It's basically I'm just proving that I know a witness for the statement and then the thing that I encrypt to is a snark verifier, right? So I just need to >> Okay. Yeah. Yeah. No, it makes sense. Okay. So yeah. Okay. I'm trying sorry I'm just trying to map my in my mind. >> Yeah. Maybe it takes a little bit of of of thinking but this is a general statement that that that snarks can kind of help us in building witness encryption. So now the question is basically can we build a witness encryption for the statement that a snark verifier accepted a certain proof >> and there's actually been some interesting progress on today. I would consider this as you know it's one of these problems that in principle we have a solution in practice we don't have a

solution >> like proving that the verifier verified >> well in not just proving that the verifier verified decrypting only if the verifier verified >> okay >> yeah so decryption >> making it like the trigger okay >> exactly trigger for decryption would only work if the verifier verified >> interesting >> yeah it's a beautiful question you know maybe even to make it like super concrete for people let's just use 16mm Mhm. >> Can you come up with an encryption scheme that I can encrypt to a particular statement so that you can decrypt only if you have a gross 16 proof for that statement?

>> And if you think about the gross 16 verifier, it's just like a couple of pairings. So you need to be able to decrypt only if those pairings happen to be, you know, some some some expression and formulas happens to be in pairings happens to be uh satisfied. >> Cool. >> Well, it turns out we don't know how to do that. >> Yeah, great open problem. Please please work on it. Please solve it. If you solve it, Anna, I'll be your friend forever. >> Yeah, it's going to be me. >> Yeah, there you go. >> But maybe someone on my show. I don't know. >> Yeah, absolutely. Yeah. Yeah. Yeah. Yeah. So, actually, there's a little bit of uh progress on building witness encryption for snarks verifiers. There's this company called Awok. Misha and others in the company have a kind of a a recent paper that I would say, you know,

moves it moves the needle a little bit, but still not quite practical in that if I remember correctly, their their encryptions, the size of their cipher text is a couple of hundreds of terabytes for every encryption. So, you know, so there's there's progress and hopefully, you know, I can hopefully your podcast will encourage more more people to work on this problem. Now I should say actually that for specific statements there's actually a lot of progress on on better witness encryption like I mentioned for example if you want witness encryption for verifying a signature for that that is just identity based encryption and for that we have very very efficient constructions.

>> Yeah. So there are there's a class of statements for which we have efficient constructions. It's just for a general snark verifier we currently don't have a good witness encryption scheme. So this is a might be a fun thing to work on. Dan, I'm actually just curious in terms of your research. Like, are you still focused on ZK? I know you in the Z through the ZK lens. Like I know you from the work that has inspired ZK systems that, you know, the the actual work on ZK systems, all of these ZK applications, but I'm curious like, you know, you sort of mentioned offiscation, you mentioned some of these like projects that branch off of ZK maybe or could be parallel. They're kind of in the same category. Yeah. What is your focus today? like are you doing FHE stuff? Are you doing anything else that

maybe we've never heard of? >> Oh yeah. Yeah, absolutely. Yeah. Look, I I love the blockchain space because it generates new interesting cryptography questions to work on. So much of my research is basically cryptography for blockchains. >> And so any sort of problem that comes up in the blockchain space that has even even a sliver of cryptography, I love it. I'm on it. >> Nice. >> Um Yeah. So well so it's funny you should say that because for example encryption starting to play an important role in the blockchain space >> like classic encryption.

>> Yeah. Yeah. Yeah. Because >> fully homorphic not like the >> Yeah. Yeah. Yeah. Even even just regular encryption. Why? Because there's now quite a lot of interest in encrypted mess. >> Oh. >> For example, Aptos is deploying actually encrypted mess. And I think other chains are moving in that directions as well. I remember hearing about this so long ago, but it was such an just an idea like and and it's it didn't get sort of traction. I remember, but now I guess it has. >> Yeah. So encrypted meals basically means that when I submit a transaction to the meool, I submit an encrypted form.

>> Yeah. >> And it only gets decrypted after it's finalized on chain. >> And so this would basically get rid of all of the sandwich attacks and basically the MEV scenario would kind of be removed. >> Exactly. So front running it becomes harder by the way not impossible encrypted meles are not the solution to everything >> okay >> but they're a step in the right direction yeah so they make all these sandwich and front runninging attacks harder but it's important to remember not impossible >> the amazing look the reason I love the blockchain space so much is you say encrypted me pools okay but now how do we implement encrypted me pools it turns out it relies on threshold encryption yeah because it's the validators of the block that are going to threshold decrypt the transactions once they're finalized in a

H >> okay so you say fine we know we've been studying threshold decryption for 40 years let's just do that >> but no >> yeah I mean this is why the blockchain is so cool well amazingly it it raises brand new questions in threshold decryption that nobody has thought to ask in the last 40 years >> oh that's good >> so maybe I'll just say the three questions I'll say them very briefly sure >> the first one is what's called batch decryption which is how is it you know we have a thousand transactions in the block out of maybe 10,000 transactions in the mmp Do we really want to go transaction by transaction and decrypt them one by one or can we somehow batch them all together and decrypt only those thousand transactions out of all the transactions in the meool? This is called batch

decryption. The goal is to release a succinct secret key that would let us decrypt the thousand transactions that have been finalized but not any of the other ones in the meool. So this is called batch decryption. I should say this is originally studied in a paper by Vamzi and Sanjang Gar and and others and this is actually also what Aptos is deploying. It's really cool to see to see this happening. Uh I should say with so for example I got really excited by this question and with with Nusra Tas and Evaner we have a postquantum version of batch decryption. Yeah. So of course for every question you ask now you could also ask well what's the postquantum version?

>> Quantum. Yes. >> Yeah. Yeah. And we have a new question to research. >> Cool. So for a researcher, a cryptographer researcher like me, the blockchain is like, you know, I'm like kid in a toy store where there's like wonderful open problems everywhere >> and you get to almost revisit I mean this is like revisiting revisiting areas that have been studied and developed in the past sort of assumed to have settled and then all of a sudden you're finding a new angle to kind of revisit. >> All of a sudden there are new questions. So batch decryption was one new question in threshold decryption. We have this whole work on what's called a decryption context which maybe I won't describe now since we're running low on time. Uh which is a way to strengthen threshold decryption for encrypted name pools. And finally there's this question of what

happens if the validators give away their secret keys. Right? You you hope that they keep their secret keys secret and only decrypt after the transaction is finalized. But a searcher could go to the validator and say, "Hey, I'll give you $100 if you give me your secret key." The searcher would say, the validator would say, "Great. Here's the secret key. There's no penalty for the searcher. There's no penalty for the validator >> for the validator. Mhm. So they could act. Yeah, they could act badly. It's basically breaking the game theory a little. >> I would call that they act rationally. In economics, this would be called acting rationally, right? Okay. >> Uh yeah, put to put a spin on it. Um so anyhow, so so this question so now there's already this all of a sudden this question of what's called traceable threshold decryption, which is if away

if you give away your secret key, I should be able to find out that it's your secret key that was given away. Okay. So then I can slash you. >> Yeah. Again, turned out nobody studied this question. >> Yeah. It's funny the so the threshold decryption encryption story. I for me it starts with Dave Oja talking about it at Osmosis. Never I don't think they ever implemented it but I remember him sharing that idea. >> Osmosis actually did a lot for for cryptoman pools and and they actually they did surface these questions. >> Yeah. They didn't have answers to all of them, but yeah, they actually because they implemented things, they came across these questions. And so, yeah, actually I give Osmosis a lot of credit for uh for introducing the idea.

>> We just had Dave on the show like a few episodes ago, and he's back in the fold on the ZK front, which we're very happy about. >> Excellent. >> Nice. Okay, so Dan, we've covered a lot of ground. There's I'm going to have to go back and listen to this show and then find little threads and hopefully program some episodes that where I can go deeper with maybe some of the people you mentioned or explore some of this work. There was one point that you mentioned at the start of the show, the proximity prize. We don't have too much time, but I think it's worth sharing just a note because we did this series on lean Ethereum. We did an episode with a Jakamo who I know is also judging the proximity prize with you, but I think it would be cool to hear an update. I mean,

for just just a note from where I'm sitting as some I'm putting together the ZK mesh, I've seen the impact of the Proximity Prize just in the kinds of works that were released especially last fall like we just saw paper after paper after paper kind of like addressing the problem that the Proximity Prize wanted folks to address. But yeah, has it been solved? Has it been proven? Has it been disproven? Like, are we done? >> No, not even close. >> Prize awarded or >> No, not even not even close. So, yeah, great. Let's do this. Let's do this briefly. >> Sure.

>> So, yes. So, the Ethereum Foundation in particular Justin Drake deserves a lot of credit for this. They put together this thing called the proximity prize, which is a million dollar prize for solving a purely algebraic question. It's it's elementary algebra about polomials. It's literally something that Gaus could have already worked on if he had asked the question. Yeah, it doesn't require any kind of 20th century math. What's interesting is that why why do we even care about this? Why is the Ethereum Foundation paying a million dollars uh to solve this problem? Well, it turns out if we solve it, we get better snarks particularly base fold and we become better provably better rather than conjectured better. Even the S2 prover becomes better. So there's

basically snarks generally becomes better if we solve it. So there's a lot of incentives uh to do it. So let me actually just say the problem. I might be using words that not everybody's familiar with but hopefully will encourage you to go look up these words. So the problem is basically about read Solomon codes and the question is in a read solomon code what is the largest distance such that the mutual correlated agreement error is still small. >> Yeah that's the whole problem. So maybe you need to look up resolment codes. Maybe you need to look up what is mutual correlated agreement. But that is basically what the question is. So resolve that and you get one of these one of these prizes. Exactly.

>> Cool. It's a couple prizes, right? It's not a single prize. >> Yeah. Yeah. I mean, so the judges are myself, Jako Menzi, and Galaron. And uh yes, even partial progress would be super interesting and we'd love to see both negative and positive uh progress. I should say we actually put up put out just recently we put out a survey paper explaining exactly what the grand challenges in the proximity prize are. >> So if you look on errint you can talk you can look at open problems in proximity questions by myself Jako and Gal and you can see exactly what the problems are and what's known and what are possible directions for attacking these problems.

>> Like in the last few months though we have seen a lot of papers at least show up on e-rint about this topic. Are those attempts are those like when we see that kind of thing is that like that team's submission? >> Yeah. Yeah. So those are those are well those happened actually before the prize was finalized but uh those were kind of steps towards I'd say maybe small steps to towards resolve the resolving the prize but very very very interesting steps really beautiful beautiful ideas really cool stuff >> and great researchers focusing on it which is fun to see like that kind of that group effort folks we've known have had on the show over the years like sort of focusing in on the proximity question. So the Ethereum Foundation by allocating this million-dollar prize is

really focusing the researchers community on this problem and that's bearing fruit. So like you said there has been a there's been a flurry of results on on this question making some making some initial steps towards making progress. One result that I wanted to mention is by Goyal and Gorwami that actually resolved the conjecture just for non-read Solomon codes. So we're interested in this question for read Solomon codes. Yeah, >> they showed everything is solved if we go to other codes. >> And so now the question is well first of all can their techniques apply to read Solomon but more interestingly can we build snarks out of these other codes?

>> Cool. >> Yeah. So there's actually a cool area to to explore there. >> The current thought that's in our survey paper says that they're not such good snarks, >> but who knows? Maybe they can be improved and can make they can be made into better snarks. And that's another way to resolve this this challenge. >> Very nice. Cool. Dan, I want to say thank you so much for coming on the show. As always, tons of ideas, so much to dive into. I hope we get to cover some of these topics in the future. I hope you'll also send some folks my way if you think they make a good guest to talk about these topics in in more detail. I can't wait to see the work that's coming out of your group this year. I feel like I, you know, through

ZK Mesh, I also get to see some of those works come out. Yeah. Thanks so much for the survey. Thanks for being my 400th episode guest. >> Yeah, thank you, Anna. It's always fun to be on this podcast and please stick with it. Don't turn it into an AI podcast. >> Okay, got it. All right, I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Hector, and to our listeners. Thanks for listening.