Dan Boneh and Justin Drake on Quantum Cryptanalysis with ZKProof.org community, mod: Jonathan Rouach

本站添加: 2026-05-15

[00:00:00]So, maybe we we can start we can start this uh this little talk uh with this kind of elephant in the room. You you suggested it. Uh the fact that we need to trust your the the words of the practitioners in this space because now everything is under wraps. And so you come with a such and such is peeled on so and so technology. And I've heard this guy and that guy.

[00:00:29]Uh it's it's about the reason why we're we're also having this conversation because it's it's basically the only way that we have as a community to figure out what's going on.

[00:00:40]So, uh at the meta level first maybe can you establish the the credentials if if you will of why we should listen to both of you.

[00:00:52]Like what what did you do in the space?

[00:00:55]Uh I know that everybody when they start talking about uh you know, these topics they they immediately go, "Listen, I'm not a physi- I'm not an expert. I'm not I'm not everything." But you guys spent a lot of time in this space. So please uh allow us first to to understand like how much weight to assign to what you're saying because I think it's a it's a core part of uh understanding. Okay.

[00:01:16]Yeah, so well first of all I guess um uh let's see. So, I still remember actually when Shor's algorithm came out. And uh to be honest, we actually myself even wrote some papers uh building on on it back back when it came out. So it's not like I'm new to the space. I've I've been following the space for quite a while. For a long time I have to say uh the most uh um uh the the experiments that were being done were using this uh NMR techniques, the nuclear magnetic resonance methods, which clearly didn't scale. So I kind of became a little bit skeptical because those methods were clearly not going to get us anywhere. And I have to say I kind of uh when superconducting qubits came out, I got a little worried, but still it seemed like that they're going to be quite difficult to scale. So, the issue is again, can you write can you run the entire algorithm in one unit?

[00:02:06]And with superconducting qubits, it's it's pretty clear you can't do it in one unit. You have to kind of figure out how how to get multiple units to work together, which is a whole other technology that needs to be developed.

[00:02:18]When the when the neutral atom methods came out, I first heard about them about in 2022 where the kind of uh these experiments started coming out. Um that was actually quite quite worrisome. And the new result from Ouroboros Atomic, I think this is maybe Justin I'll just kind of repeat what Justin said here. It's the the number the number they're they're claiming is basically 26,000 qubits in 10 days.

[00:02:43]So, 26,000 is really important here because the it's um we're basically at the point where we can already build 100,000 traps using one laser. Yeah. And so, really with one unit, it's kind of important that 26,000 is less than 100,000. Yeah, you can build with one unit basically, you can have enough traps to actually do the entire algorithm. It would take 10 days, and we can talk about some of the physical challenges that they still have to overcome. So, I'm actually not I'm quite pessimistic about 2029. Are these are these machines available to to the general public for testing or >> Good good. Um so, but let me just finish the I'll just say to answer your first question. So, for the over the last couple months, both Justin and I have been talking to a lot of the physics teams who are building these these who are doing these experiments. Uh the papers are out there. So, you can read you can actually go read the papers, you know, um one of the papers that I really like is a paper that just appeared last November. It's an experiment from Dolev who was at Harvard at the time. He's the founder of Ouroboros Atomic. I think it's kind of important for people to understand. He did an experiment with 448 qubits where he literally demonstrated all the steps of a quantum computer, yeah? So, he demonstrated quantum computing error correction on those 448 cubits. He demonstrated 27 gates. So, you can actually run 27 gates quantum error corrected.

[00:04:05]And then the last thing that needs to be done, which we can talk about, is this magic state distillation, which is a fairly complicated thing that he also was able to demonstrate to work. So, really kind of he really showed that all the steps actually work.

[00:04:17]Now, it's just a matter of scaling it up to, you know, 26,000 cubits and have it run for 10 days. The other thing that's really important to say is also a paper from last November was it was showed that he was able to build quantum memory, just keep the state stable for 2 hours. Before we were measuring these things in microseconds. Now, he got it stable to be stable for 2 hours. And, you know, Adam and other physicists basically, they all say basically, once you get it stable for 2 hours, going to 10 days is not that much harder. Yeah.

[00:04:50]So, it's like all the pieces are coming together. And this is we're not talking about things that happened a decade ago.

[00:04:54]We're talking about papers from last November. Yeah, November 2025. So, there's been like a shift in in the physics experiment physics experiments that kind of make all of us and all of you should be quite nervous about how quickly things are changing. So, it's not like we're not we couldn't give this talk 5 years ago.

[00:05:14]Yeah, just things haven't happened then.

[00:05:16]But now things have changed and it's time for our community to take this threat more seriously.

[00:05:21]At the same time, I have to say there are a lot of challenges left to solve before we can run Shor's algorithm at scale. So, I'm quite skeptic about 2029.

[00:05:31]We we can go through the challenges.

[00:05:32]It's it would be I think it would be The way I like to say it is if we had an Apollo program, like, you know, 3% of the US budget was devoted to building a quantum computer We might have that and we don't know, right?

[00:05:44]Yeah, we don't know.

[00:05:46]We can all we can all talk about things we know. Maybe we can do it by 2029 with the current level of funding where it's just a bunch of small startups and small teams working to build it. It's very unlikely this will be done in the next decade even.

[00:05:59]In just in in in what you presented you gave a left side which was the software and the right side which was the hardware. It seems like gravitating the talks around the hardware. This is the the things that we can verify those papers try to reproduce go and and and collect the the results outside but then the other side the the cryptographic advancements those are the the sides that that we're going to be kind of relying on on these conversations.

[00:06:31]So maybe again uh what brought you to get into this this space deeper and and you know look at those lasers and and get excited about it.

[00:06:44]Yeah, I mean unlike Dan I have no credentials in this space for the the quantum computing specifically. I was invited by the Google folks just to review you know the Ethereum section or whatever and you know I just took the opportunity to to learn more and I was like totally nerd sniped and especially after the auratomic paper I've pretty much done nothing other than like learn about neutral atoms. So you know like I spent hundreds of hours in the last you know five weeks just learning about neutral atoms and I think I've watched like most of the YouTube videos. That's how I learn a lot like It's like Bitcoin in 2012 you could still wrap your head around what what's going on in the space right? And you get to know the people because there's not that many people who make the presentations.

[00:07:31]>> [clears throat] >> And you know I'm I'm starting to build a network of Telegram contacts and and whatnot and uh it's and the the the way that I I roll here is like purely based on intuition. So, I'm like an LLM like ingesting all of this data and then kind of giving like reasonable kind of output, but not having like a deep understanding of what's going on.

[00:07:52]>> So, this is a this is an important point. So, uh many of the things that that you described, like we said, we can go back to the papers and and see them.

[00:08:01]Uh but and so, thank you for aligning us on the facts, right? These these are, you know, unarguable facts.

[00:08:09]Uh but there's a question of tone. Like, what do we do with this information?

[00:08:13]Every time we marvel at the at the progress, there's a uh a a background you know, uh you know, emotion of fear that is joint to it because it can impact a lot of what we're doing.

[00:08:28]Uh how do you look at the tone of the conversation and what to do with with this information that you described?

[00:08:35]And this goes to both of you. It's a kind of a core question because it there there might be impact to that tone.

[00:08:44]Yeah, the tone is extremely important.

[00:08:46]And I think it's important to not be alarmist and not to appeal to emotions.

[00:08:50]If we rush things, there's like two things that can happen that are bad.

[00:08:55]Like, one is that we can just make mistakes in the new cryptography that we deploy and we end up with a system which is actually in practice much weaker than what we have today and there's various ways to shoot yourself in the foot. So, we want to do this properly. We want to take our time. And the good news is that we have, you know, quite a bit of time until, you know, end of 2029.

[00:09:15]The other thing that I'm very mindful of is also the opportunity cost of just working too much on on on quantum. So, there is a world out there where, you know, half of the firm foundation just works on quantum. Like, today is like less than 5% of the firm foundation working working on quantum. And you know, I before I I have a very like strong alarmist take. I want to do a lot of due diligence because it would be disastrous if, you know, I say, you know, we have to put like half of the foundation on this and then it it turns out that it was completely unnecessary.

[00:09:52]Actually, can I add to that? Um I think it's really this tone is really really important. I mean, the message that people in our community should take is uh definitely don't panic.

[00:10:02]Yeah, there's time there's time to fix to fix these things. That's usually what you say when you start panicking, right?

[00:10:06]>> No, no, no, no, no, no.

[00:10:07]>> [laughter] >> This is really don't panic.

[00:10:09]>> Nothing to worry.

[00:10:11]There there there is time for us to to address these things. I think we should not panic but not ignore uh the threat.

[00:10:17]I actually like to say that this uh rush to post quantum is really quite dangerous and there are a bunch of examples that I walked through of of companies that have rushed to post quantum and have ended up hurting their classical security uh because of the fear of a quantum computer or overall their security went down. To be honest, even maybe I uh um I would even say that for example, NIST even standardized their post quantum signatures a little too early.

[00:10:47]Yeah? If they had waited, we would have had better standards now. Just as an example, we have just last year in crypto, there was a better version of ML-DSA that was published. Yeah? If NIST had waited for the better version of ML-DSA, we would have had signatures that are 1/3 the size of what they are today. Yeah? So, that's an example the cost to rushing to post So, we're specifically in the ZK-Proof in a standardization conference. Huh. Uh and we did and you're part of the steering committee, right? Where we did face this exact problem in ZK-Proof because we could have gone to standardize uh Groth16. We actually had a an effort to do a formal verification of the verifier of Groth16. And we realized that part of the reason why uh there's no real strong traction in the industry to standardize the current best practice, right? Even the paper that that was published was was in the end proven using growth 16 at the end.

[00:11:46]Uh this led to not having a standard with with the current classical tools. So, in a way, even the the looming looming question of how fast quantum is arriving is affecting all of us right now with the current classical tools. And it poses the question of how do you standardize with with this you know cloud over the head? Do do you have thoughts on that?

[00:12:19]Uh it's very difficult. And there is value to kind of trying to put things early out things out early. So, one one piece of valuable input is you know, we have hundreds of cryptanalysts that are looking at like all of these post-quantum schemes in the second round of the NIST. And you know, it's very good because we we learn about breaks with you know, whatever like all sorts of you know, exotic schemes. And that's very useful information. And also even like the the assumptions that we we think are are pretty strong like lattices. It's good to have experts look at this more seriously.

[00:13:01]Um on standardization specifically, I have this like optimistic project called SHA-4. So, the idea here is to try and get NIST to run another competition for hash functions specifically for algebraic hash functions that are ZK-friendly.

[00:13:22]And interestingly, they invited me to give a talk just a a few weeks ago.

[00:13:28]Um and uh the reason they invited me to give a talk is because um there was this presidential action uh kind of encouraging various branches of government to play nice with with crypto. So, we have a unique opportunity here to engage uh with NIST um but you know, uh unfortunately, more likely than not, it would take years for this shuffle competition to even start.

[00:13:50]Yeah, actually can I can I add to that?

[00:13:51]So, um I actually really like the stance of the Ethereum Foundation on this this question, which is that uh for any system that they deploy pre-quantum, they at least in their pocket they have they have to have a post-quantum version of it, which is I think a really nice nice stance so that you can switch if you have to if you have to.

[00:14:10]>> So, what's the post-quantum version of growth 16 that's in the pocket?

[00:14:14]>> Yeah, so it's the hash-based systems.

[00:14:15]And and so the we have uh proximity gaps uh that that we need to solve there?

[00:14:20]Well, I mean, that's just an optimization. You you can either choose to take the optimization or not. So, do we consider this is a an important question. Do we consider that we have in our pocket uh a form of efficient uh zero-knowledge proof based on the on the hashes that uh that we could switch to? Yeah. So, I would I would say when it comes to the standardization effort, you should standardize the most efficient scheme, which is probably pre-quantum, but you should also standardize the uh a post-quantum system so that you can switch so you have a standard ready to switch if Q day happens on 2029.

[00:14:54]Um yeah. So, hopefully that's that's where things will go. And even within the hash-based uh SNARKs, we can have agility. So, um you know, we can switch from one hash function to another. And this is what we're doing actually with uh XMSS signatures. So, we're inviting the validators to register three different pub keys with three different hashes.

[00:15:13]And if Poseidon breaks for whatever reason, we can move to Blake or another one. Um of course, there are costs to moving to something like Blake because you have much less efficiency, and so it would mean you would have to do the signature aggregation with on a GPU as opposed to CPU but it's much better to pay that cost than it is to have you know the whole thing crumble.

[00:15:33]Can I actually make my one more point about the about the zero knowledge question? Um so as you know the Google paper published a zero knowledge proof of the existence of a circuit.

[00:15:44]Um I would actually I keep saying this I would I would view this as like a challenge for the community. So somebody I I actually wish they had published the paper in the clear. I believe in open research. I don't believe in uh keeping knowledge class uh not public. Uh I want um you know this is this is the Oratomi and Google these are all efforts that are happening in California. I want quantum in Silicon Valley to happen in California. If we keep it not public it might happen somewhere else. Uh and so this is a challenge to all of you please figure out the circuit. Yeah literally you can download the Kicks Mix quantum emulator. The Kicks Mix emulator it had the documentation page is pretty short.

[00:16:26]These quantum gates are not that the Toffoli gates are really simple. By the way Toffoli gate is a pretty simple thing. It's just a function A and B XOR C. That's a Toffoli gate. Yeah so the question is just can you implement uh elliptic curve addition using a small number of Toffoli gates? That's like a question that all of you can post the cloud post the cloud and work on yourself. Yeah. And just for context the context here like it's basically one guy Craig Gidney that is just doing this manually so he's been obsessed with Shor for the last 10 years. And all of the results come from him and when chatting with him you know he [snorts] doesn't even use AI. Like he's just rolling with pen and like doing it manually so presumably if more eyes go on it and you use more sophisticated tools we would get you know extremely good results.

[00:17:14]What was the name again?

[00:17:16]Uh Craig Gidney.

[00:17:18]Yeah he he has a few He has a lot of papers on quantum optimization. I thought you were saying challenge to the community of taking that proof and trying to reverse engineer what was the circuit there to try to break the zero knowledge there.

[00:17:30]>> What do you mean? It's a zero knowledge proof. No, that if succinct unless if succinct got their proof correctly Yeah, the proof actually it was one of the reasons it was an important for us to use Groth16 is because we really wanted the proof in the paper. Yeah, if we had a post-quantum proof we couldn't put it in the paper.

[00:17:49]>> Dan wanted that. Yes, it was really [laughter] important. It should be in the paper. It's like it's like four lines of four lines of To repeat the mechanism you have a whole system running that can run like the simulation of what would happen with this algorithm and then the result of running that in zero knowledge produces a tiny proof that that is the thing that was published. So, of course you're saying we can't go back.

[00:18:12]>> knowledge proof. You can't go back. You have to invent your the the circuit yourself. So, that's one point I wanted to make. The other other I wanted to make point I wanted to make really quickly is there's a lot of development that needs to happen in quantum error correcting codes to get to a Shor's scale computer and you know, there are lots of algebraists in the audience here. Quantum error correcting codes is a purely algebraic question. Yeah, you can literally think about this all of us are equipped to think about this problem. They're literally talking about using LDPC codes which also come up in zero knowledge and So, it's an amazing area. So, it's like anybody has spare cycles, go learn about quantum error correcting codes and you can really make a strong contribution.

[00:18:55]Let's talk about the lattices part of of you know, the the design space. Do you believe that the the progress that you just described that we we managed to have a shorter signatures? Is Is going to stop or do you expect more progress there?

[00:19:16]Me? Oh, I see.

[00:19:17]Uh Uh yes, I would Okay, so let's see. So, uh more >> a lattice talk on less secure proof and you're you're quite in that space, right?

[00:19:26]>> Right, right, right. So, so you So, you're asking are we going to have better post-quantum signatures? That's really what you're asking. Yes. Yes, the answer to that is of course we're going to have you know, things only get better, they never get worse. Well, actually they could get worse.

[00:19:37]>> [laughter] >> Yeah, but uh in in this space that they generally generally get they they they get better. So, yeah, so we will we will have have better signature schemes.

[00:19:46]Um there's not there's no theorem that says that we can't have uh you know, a post-quantum signature that's under 200 bytes long. Yeah, so um presumably what what we we we will get there. Um so, let's see. So, uh I think you were you were you were asking also if we should standardize the lattice methods or That's the implication. I got to What is the the pace at which we need to look at what we have, get that, [snorts] implement it, and and stop and standardize uh versus waiting a little bit more, testing a bit more maybe, or optimizing a bit more.

[00:20:21]>> Yeah, I look, I think the answer there is we had need Honestly, we we can't have a standard that's just uh frozen in time and doesn't update.

[00:20:30]So, the standards process itself has to be rolling forward. And NIST actually understands this. They know this quite well. In fact, they have they have What is What is it called? The additional signatures competition that's currently in its round two. So, hopefully uh it'll conclude at some What is addition signature? It's uh the ability to to program >> Add more signature schemes, yeah? And so, uh yeah, the fact that uh they froze ML-DSA and and Falcon, um they kind of see the problem with this. I think they either worried about the length of the signatures and B, they're also worried about the fact that we're putting all our eggs in the lattice baskets. Uh and so, they want to diversify both the assumptions and uh get better signatures.

[00:21:09]>> What are the other baskets?

[00:21:11]Oh, there are many other baskets. Uh wait, there's the MPC in the head methods, there are the multiple polynomial methods, there are the there are you know, uh coding methods. There are Yeah, there are many trains to do to do different uh post-quantum isogeny methods. There are many trains to do different uh uh post-quantum signatures.

[00:21:27]And uh yeah, we we just make sure need to make sure that the uh the the standard is updated over time. You know, I I have to say it's a little uh disheartening when you talk to folks in industry, everybody seems to be standardizing on ML-DSA. Yeah? Even though we already have better example better signature schemes.

[00:21:43]>> It's the addition of two signals, right?

[00:21:45]Worry and this is the standard. Like what what That's the the logical step, right? Um What worry, so moving you to change what is currently available as a standard, this. Is there Is there any other outcome? Well, as I'm saying, we already have better things than what's in the standard.

[00:22:05]Um so so yeah, so that's but so that's one one uh one thing to consider. The other thing to consider that comes up often is I think also uh even the EF is is nervous about deploying lattice-based signatures because who knows, maybe maybe lattice-based signatures are not as as secure as we think. There's this fear of a classical attack, say on on lattice-based signatures. Probably I would be fairly confident about the classical security, uh but there's still a justifiable fear about the the classic security of these signatures.

[00:22:37]But the answer to that is fairly simple, which is just do what the web did for encryption, and that is let's use hybrid signatures, right? So, when ML-DSA signatures are so big that adding an ECDSA signature to it is like taking a bus and adding a football to it. It's not that much longer.

[00:22:54]Yeah? And so, the minute you do that, there is no classical attack on you, or at least if there was a classical attack on that, there would be a classical attack on on blockchains today. So, at least we're taking the classical threat off the table. And then the only thing to worry about is our quantum our lattice-based signatures quantum secure. Yeah, and that is a There was a a scare around the paper that went around and then we understood that probably the results don't hold, right?

[00:23:20]Yeah. Did did that path open up doubt or or was that doubt shut down? Do you remember the the researcher and the names?

[00:23:30]I remember the paper, but it was basically shut down. There was Yeah, this is a Euler's paper.

[00:23:37]Yeah, that was an an interesting attempt. I would encourage more people to to look at the problem cuz we need more people to study the problem, but as far our present state of knowledge is that lattice signatures are perfectly fine in a post-quantum world. That could change tomorrow, but our present That's our our present state of knowledge.

[00:23:54]All right, let's open up to questions from the audience.

[00:23:57]Uh I'll I'll get back to them just in a moment. Everyone else first.

[00:24:04]All right.

[00:24:06]Ariel and then Okay, this is a suggestion, but yeah, I'm happy to I I think we should like sort of like What's the word in in I forgot the word in English, but the a petition.

[00:24:22]Uh I I think we should sort of demand uh some some demonstration of sure on whatever larger than zero bit elliptic curve before we do these migrations. I think this will be a a win-win because I think, you know, human nature we don't do good work when we're held to low standards. And I feel the quantum industry is in a sense being held to a low standard. They're saying We're saying at at some hint vague hint, we're going to redo all our tech stack at great both risk from the upgrade and opportunity cost risk, like not uh standardizing Groth16. So, as a constructive thing, I think there should be like maybe even a formal petition, "Hey, Google is doing this very risky huge upgrade. Ethereum is we we demand some demonstration of Shor's algorithm on some curve indisputable that it's really not just as good as a random guess, indisputable uh and I think this will be good for everybody.

[00:25:34]Uh you know, it will make put make them do better work. I mean, maybe they're doing awesome work. I don't mean to I think it'll be good for for the quantum people.

[00:25:42]Uh it'll focus them on the the real problems. Cuz right, cuz sort of you know, Craig he's awesome.

[00:25:50]I chat with him on Twitter, but it's sort of like the analogy I have in my head is like it's papers on like once you have a time machine that goes 1 second in time, given that time machine, I can make a time machine that goes 5 years back in time. 60 years back in time. And now we have to start worrying about time traveling Nazis helping Hitler win the war. That's the analogy I have. That's it's great. But right, we the big question is like can we go can we do it at all? So, I think this will such a petition will be like a win-win for everybody.

[00:26:21]Like I'll feel I'll feel better. I'm as someone on the skeptical side who's like I feel my you know, and I know people are losing jobs, people are losing funding and jobs, people are concentrating on elliptic curve cryptography, which is still the same like practically the whole internet runs on uh there's there's no there's nothing better than Pollard's rho.

[00:26:41]Right? Poseidon, we have we have already a direction of tax. I don't know.

[00:26:46]30 The whole internet is running on a discrete ECD elliptic curve signatures.

[00:26:50]There's nothing better than Pollard's algorithm.

[00:26:53]So, so I think it'll Yeah, this will be a a good thing for for win-win for everybody. Thanks. Yeah.

[00:27:00]I mean, we we will get that. The thing is that we haven't reached this milestone of a real-time you know, the decoded logical qubit where you can perform logical operations. So, you know, where all of the ingredients are there, but we haven't reached this like very important milestone. And once we do have this milestone, then you can start building these these more complicated circuits.

[00:27:24]Um I think I think it will happen, and I hopefully it will happen soon. Um like one thing to be careful of though is that once you have this demonstration, you're not too far off from a demonstration of the much bigger thing because you've cleared off, you know, 90% of the engineering hurdles just to get to this point where you're going to have, you know, just a few uh you know, good enough qubits logical qubits that on which you can run run computation. So, this mentality I think it would be amazing if we if we had this demonstration, but um it's also a bit dangerous to just wait for it.

[00:28:02]I actually I I really I I agree with you. I think actually we need we do need to encourage them to do small small um demonstrations. Um Yeah, so when when will that happen? We don't we don't know, but actually in our last in our recent conversations with them, we actually did push them to do small small demonstrations. They were actually quite interested and happy.

[00:28:23]They didn't even realize that like anybody would be interested in factoring 21. That yeah. And so, they they they uh would be I think they are open to to kind of to doing that. Uh so, hopefully we'll see Yeah, hopefully we'll see that we'll see that soon.

[00:28:39]Yeah.

[00:28:39]But that as as Justin was saying, I don't think that we should wait so that those small demonstrations probably are going to happen not too far in the future.

[00:28:51]Uh but if we wait for those to happen before we do anything, then we will have lost some precious time where we at least as a community can think about what we want to actually do.

[00:29:05]Hi.

[00:29:06]Um so I have two related questions. Like one is what is the asymptotic run time of Shor's algorithm? Is it like linear in the number of bits or quadratic? Yeah, yeah, it's actually the running time is really simple. Actually, it's really funny to me that the the hardest part of Shor's algorithm is a classical computation. And it's like like Justin was saying in his slides, it's a very simple classical computation. Now, maybe I should repeat it. If you want to compute the discrete log of H base G, the computation is simply X * G + Y * H for integers X and Y.

[00:29:38]Yeah? So, the running time is however long that takes.

[00:29:41]And so, all the optimizations is they use a windowing method for that for that multiplication. And they use an unnatural windowing method where you do use a different window where you use a different lookup table for every step in the window because the lookup table can be done classically outside of the computer. And so, what ends up doing what you end up doing is you're doing an elliptic curve addition plus a lookup table. Lookups and part of the optimizations that Craig did is he showed that lookup tables are very cheap in a quantum circuit.

[00:30:12]Uh yeah, so you can have very very So, they're talking about uh 16-bit windows.

[00:30:16]So, 65,000 element windows. The lookups are quite cheap. And when you do that, if you think about X * G + Y * H, that's 512 just 512 elliptic curve additions.

[00:30:27]With a 16-bit window, you do 512 / 16, you get 32 additions. And it turns out there's a very cute trick that lets you shave off three additions. So, you end up with all of Shor's algorithm is just 28 elliptic curve additions. Yeah, that's the whole algorithm. Just 28 elliptic curve additions, and that's uh basically the circuit that you guys are now challenged with coming up with uh how small a circuit can you build that does 28 elliptic curve additions? It's not an actual It's not an actual cuz the guy actually uses it in the ZK circuit.

[00:31:00]Ah, okay.

[00:31:01]>> That's the Orchard's algorithm. Oh, yeah, yeah, yeah. Oh, right, right, right. Of course, of course, yeah. Just cuz this Yeah, cuz it's the same problem. Yeah. You want to do most of the competition outside of the ZK circuit. Same thing here. They want to do most of the competition outside of the quantum computer. Yeah, it's good good point. I would bet on Daira being able to find the optimization. Go for Please.

[00:31:19]Do it.

[00:31:21]The first obvious thing is that you can do a classical paper Wait, wait, wait.

[00:31:25]Yes, and K then allow people to hear what you say.

[00:31:30]Yeah, there's another question. Can I Can I ask my follow-up question?

[00:31:34]So So the question is I So I guess if there's a multiplication, I guess it's a quadratic in the number of bits of elliptic curve or something like this.

[00:31:42]But my my question is does it make sense to put up a canary, like some kind of massive bounty that you can claim if you can break an 80-bit 80 80-bit elliptic curve or something like this?

[00:31:53]So that we get a signal whether we're close to >> That's not a signal. What Once they can do 80-bit discrete logs, it's probably a matter of months before they can do 256-bit discrete. That's not a signal.

[00:32:03]>> That was my question.

[00:32:03]>> That would be too late. Okay. Yeah.

[00:32:06]It It's funny, you know, that like the auratomic people are saying like going from like 100 bits to 256 bits, it's probably just a reconfiguration of the experiment. It's not You You probably You probably won't even have to build anything new to do it.

[00:32:18]But But there's more hands and then you solve the >> [laughter] >> cryptography.

[00:32:28]Right. Um so I read this paper from from Google uh you know, with the with this this zero-knowledge proof of this of this circuit. Um and I was a bit confused by this because it was sort of claimed as a responsible disclosure thing, right? But like I think it's pretty obvious to everybody that someone is going to discover this optimization independently before we build a quantum computer that can run the circuit. So like why do it?

[00:32:56]Three letters. Yeah.

[00:32:58]>> [laughter] >> I I think it's actually worthwhile saying Google operates it's a large company. They operate under certain constraints.

[00:33:08]They really had two options.

[00:33:10]They could make this advance and simply say nothing to the world about making that advance.

[00:33:15]Or they could make the advance and prove it in zero knowledge. Those are the only two options they had. Yeah? Just that's just the world we live in.

[00:33:22]And what they're telling you what they're telling all of us is that for future advances they might not even do the zero knowledge proof. Yeah? So it's quite possible I think quite sad, but possible that 5 years will go by, you will hear of no progress, but progress will have been made. But that's the less progress we need, right?

[00:33:42]What what what we what they presented is is okay, this the algorithms are realistically realizable by once the physics catch catches up.

[00:33:54]No, no, there's still there's still algorithmic like we we still need to develop better quantum error cracking codes. QEC there's a lot of work to be done on the QEC.

[00:34:03]And it's again, I hope not. I think it would be really sad, but there could be advances in QEC that we just won't hear about.

[00:34:11]I hope not, but Hi. So let's say that we meet the 2029 deadline or maybe sometime later quantum computers are deployed in practice, but I just want to ask a few futuristic question which is like let's say that some companies or countries achieve a certain level of you know quantum readiness which other countries or companies don't achieve. So in that scenario, what role do you think will regulation play if at all any? And can you comment about like will there be any you know, do you you know, speculate any you know, checks and balances balances on like what kind of quantum attack is permitted in a legal way and so on?

[00:34:56]So, if there was like one government to keep in mind, it's probably China. And in China, they do things very differently to the US. There's more of a of a centralized you know, research effort and there's not as much transparency.

[00:35:10]And when you talk to the Google guys, they tell you they publish the similar papers with but with six month latency relative to their papers. But yeah, it's possible that you know, the US government is just marching along very fast and so the Chinese government is marching along and we and we don't know about it.

[00:35:26]In terms of regulation, like there is this one NIST date 2035. I believe the way it's framed is that the the branches of the US government have to update their cryptography by 2035 and as I understand what's happening is that a lot of people are just anchoring to this date. And it seems like this date is just a bad date. It was just badly chosen.

[00:35:56]And I heard you know, the other day where the story behind this date and it didn't give me much confidence.

[00:36:03]So, what I think might happen actually is that this date will be revised. And there's you know, potentially efforts you know, happening to to talk to NIST and and and convince them to change the date. So, if you today are anchoring on this 2035 date, I I you know, urge you to just forget about it. What's the date again? 2035.

[00:36:27]So, a follow up on this. So maybe we are moving towards a you know multi-polar world or you know just a bit tangential but in that case do you you know also speculate that there will be some sort of a DAO or something about the governance of quantum rules or regulations in the world?

[00:36:53]That's not that's not a question for us I think.

[00:37:02]Thank you.

[00:37:03]Yeah, I have a question. Are the entities that are running on RSA on the same schedule as ECDSA or are they going a little slower?

[00:37:13]So the question I don't completely get the question but basically RSA is harder than at least as we know today given the the best in class algorithms than than discrete log.

[00:37:24]And like the way in which they're harder is that they they they just run they take longer to to run. So if indeed neutral atoms are going to kind of win Q-day then you know we're looking at potentially a whole year to break one RSA key. So maybe we'll see like a super ultra high value key being broken but we're not we're probably not going to see widespread breakage of RSA you know in the early 2030s.

[00:37:48]Maybe I I I can add to that in that the hardest part of factoring is computing the function G to the X mod N for for for for G and for given a G and X, yeah?

[00:38:00]And well because N is 2000 bits G to the X mod N is a lot harder to compute than elliptic curve the elliptic curve multiplication. And so that because of that factoring is is what what is it it's like 10 times harder? 100 times. 100 times harder than than than discrete log. But one interesting coincidence is that the best known algorithm for factoring uses half a register. So, you know how I talked about these registers?

[00:38:26]So, instead of using a register of 2048 bits, use half a register of 1024 bits.

[00:38:31]So, you have the same number of logical qubits. So, you have 4 * 256 versus you know, 2048 / 2. And just by coincidence, these are the the same number. So, from a logical and physical qubit standpoint, it's the same, but the run time is much longer for RSA. I should probably add that like Oded Regev actually had a very cool paper a couple years ago that gives a different way to do factoring quantum factoring that actually reduces the number of qubits, but that improvement is for factoring, not for elliptic curve methods.

[00:39:03]So, um yeah, there are other approaches to factoring, but I guess we're mostly interested in the discrete log question on elliptic curves.

[00:39:11]Okay. Um so, two observations on the related.

[00:39:16]Um so, the first is that some protocols are broken completely by finding a single um discrete log for a statically known key.

[00:39:26]So, Peter Anything using Peterson hashes, um most SNARKs that use um descriptive discrete log um basic basis. So, so, anything based on a IPA, um all you need to do is find um discrete log between two generators that are assumed independent.

[00:39:47]Right? Um that means that um you can afford to take um a much longer time to find your discrete log. So, forget about 10 days. If it takes 1,000 days, then that's fine. The the protocol is completely broken for every key.

[00:40:03]Um and so, we can consider um kind of optimizations that might otherwise not be practical. So, for example, um guess K bits of is key, um then you only need to find the rest of the discrete [clears throat] log. Um, and it's two to the you have to repeat the algorithm two to the K more times.

[00:40:28]Um, but it still works. So, um, that only saves off a a constant factor. But, I mean, I don't know whether there's anything more efficient than that. Maybe you can shave off 2K. Yeah, there is.

[00:40:40]You can actually trade off the amount of quantum computation to the classical computation. Exactly.

[00:40:45]>> You can that this is why they go from 32 additions to 28 additions, rather 31 to 28. That's basically making the classical step harder. Yeah.

[00:40:53]>> Uh, and that's the kind of >> it's the same as 2K.

[00:40:55]>> all they're already using this these kind of tricks.

[00:40:56]>> Yeah, yeah. I thought they would be cuz it's obvious. Um, so, does that not decrease our estimate of >> [snorts] >> um, or maybe this is already taken into account in the 2029 um, date? Is that Is it Um, I mean, everything's taken into account.

[00:41:19]Yes. Um, and like that but I mean, So, in the Google paper for example, um, that there are just a couple of sentences about this. Um, and a lot of the kind of analysis of the impact on blockchains is based on the assumption that you need to break every key. So, so even the analysis of um, Zcash for example, it is just wrong because Zcash can be totally broken by finding one um, discrete log for balance violation.

[00:41:49]Um, and so I I think that's probably true for for quite a few of the other blockchains that um, are affected. Um, so so we know we know that the Google paper has missed things. It They They knew in principle that >> This is discussed. The fact that the SRS can be broken is in the Google paper.

[00:42:08]Uh, it it's not in the specific analysis of Zcash. So, so they haven't kind of applied that conclusion to specific blockchains because I I mean, I guess they they didn't know enough about the specific blockchains um and what they depended on.

[00:42:24]Oh, yeah.

[00:42:27]But but by the way, I do want to clarify the 2029 date from Google and from Cloudflare.

[00:42:34]These are the their targeted dates for the transition.

[00:42:37]Those security teams are not saying that by 2029 they'll have a working quantum computer.

[00:42:42]Um yeah, that date is probably too aggressive.

[00:42:47]Um yeah, it's we're not So, this is just a date to complete the transition.

[00:42:51]And same for Ethereum. Same for Ethereum, yeah.

[00:42:54]Yeah, yeah.

[00:42:56]It's going to take a while with Okay, two more questions. Yeah. Um Sorry. Oh, yeah. Uh yeah. Uh I'm going to go the completely opposite way uh from this talk. Not because I believe it, but just for fun.

[00:43:13]Uh but 10 years ago there was a paper I think in the RWC conference, which was about the 1 GB IC uh signatures.

[00:43:23]So, what I was wondering is if people are let's say not very happy about the new post-quantum mechanism and so on. Has anyone actually looked at increasing the key size for ECDSA and so on, so that even if it's polynomial time, it would take so long to break it that we could use it for a little while?

[00:43:47]It's not a blockchain question at least.

[00:43:50]Well, no, I think it is.

[00:43:52]Uh the the negative is I mean, so um today, for example, we have um uh you know, the BLS 381, which is slightly uh you know, larger than than 256. And so, maybe that buys you a little bit of time and you can try and and boost that, but um you know, it's very expensive to make upgrades on on blockchain. So if you going to make an upgrade, you might as well do a proper one. And as you hinted with RSA, you know, we're talking about you know, pub keys that are gigabyte long.

[00:44:22]And now probably with the new resource estimates, they might be you know, 10 gigabytes long. So it it just seems completely impractical at least relative to the to the known technologies that we have. And by the way, this is like a ZK proof and the the you know, one of my slides that one of my actual slides that I didn't show is that ZK proof just solves everything. Right? So we have ZK proof gives a signature aggregation, for example, that solves the size problem. ZK proofs give us post quantum data availability, which by the way has this this problem that there are hinted at, which is that you run one single discrete log and then Ethereum's DA is just blown up and in in its entirety.

[00:45:04]And then even at the execution layer where we have execution proofs you know, of the ZK VM stuff and and and roll ups, we can we we we also have the hash based snarks there.

[00:45:15]Just uh I'll add one sentence to that, which is if you're going to move to a larger discrete log problem, you're basically going to be changing the curve that ECDSA works on.

[00:45:25]Uh changing the curve either in Bitcoin or Ethereum is as hard as moving to an entirely new signature scheme. So then you might as well move to a post quantum signature scheme.

[00:45:33]Also a comment about uh TLS 1.3, the size of the subgroup is still Uh the size of the subgroup is still 256 bits. So what you get is straight one over 256 squared increase in the um quantum circuit cost, I think, which is 2.25 something like that.

[00:46:01]>> Okay.

[00:46:02]Yeah. You You don't get it. It's not cubed.

[00:46:08]Yeah, so one more question taking into account both Dan stock in the earlier Justin stock and this panel and especially this being ZK proof.

[00:46:18]What do you guys think is kind of the most important open problem with ZK proofs in the context of post quantum and not in the context kind of is it proof efficiency proof size yeah.

[00:46:31]>> [snorts] >> So for us the biggest open challenge is the latency of recursion.

[00:46:38]So right now we can do two to one recursion of a hash base proof in about half a second on a on a laptop CPU. And we'd like to get that down, you know, quite quite a bit. But the thing is that um you get you know, the difference between for example 250 milliseconds and 100 milliseconds and 10 milliseconds is is is actually huge. This opens up a whole new design space. And so in some sense, you know, if you think of snarks as the universal glue, then you know, the recursion time is you know, the gap between you know, your your your bricks.

[00:47:11]I don't know. It's not a very good analogy, but we want to get that recursion time as as low as possible and the conjecture helps with that, right?

[00:47:19]Because you have smaller proofs that are easier to to verify and therefore easier to recurse on.

[00:47:24]Honestly, I would love to see better lattice based snarks. So please somebody come up with a better lattice based snark. What's the current Um Lattice fold neo Well, so lattices are very good at folding, but then you still need to to do something at the very end.

[00:47:42]Um so yeah, fine.

[00:47:46]I had a question regarding the presentation you provided where you mentioned this 10 millisecond number to evaluate one gate sort of say or one level. I was wondering is this like is there like a theoretical floor that indicates that it's 10 milliseconds or or is there also the ability to shrink that number and that way speed things up?

[00:48:07]Yeah, so the way the accounting works is a little complicated. So, the minimum um cycle time is going to be on the order of 1 millisecond because that's the error correction cycle time. But then there's this other thing that Dan hinted at, which is the magic state distillation factories whatever. And so, here it's actually more of a throughput thing than a latency thing. So, you can have these factories running uh in parallel um and the the problem is that these factories consume a bunch of qubits. And so, in order to uh not have a too many qubits, you kind of limit yourself to the number of factories and then that basically determines how fast you can produce these magic states. Um and you know, you're going to it comes out at 10 milliseconds. But if you if you're willing to have way more logical qubits for these uh for these for these factories, then you can you know, bring it down significantly much closer to the error correction time, which is you know, 1 millisecond.

[00:49:05]Okay, that was our last question and concludes this talk. So, uh please join me to thank our speakers Dan and Justin.