Quantum Cryptography with Or Sattath

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we'll 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 week, Kobi and I chat with Or Sattath Assistant Professor at the Ben-Gurion University in the Computer Science Department. In this episode, we discuss quantum computing and what this means for existing systems, as well as quantum cryptography, the fields in which Or works. We explore how new quantum cryptography discoveries can interact with existing proof of work systems. And while we don't get a chance to cover everything, I do think we start to scratch the surface of this very interesting field. I want to say a big thank you to Justin Drake for the recommendation. I didn't get a chance to mention this during, in our recording, but I do love these episodes that go outside of our usual topics and that introduce us to new fields. Now, before we kick off, I want to let you know that the application to attend zk10 is still open. This time around, we'll be hosting our event in London. This is happening on September 20th, and as always, we aim to bring together top researchers and engineers working in zk to share their latest research and new findings. Check out the show notes for the application form. Please do note spots are limited. Hope to see you there. Now Tanya will share a little bit about this week's sponsor.

Polygon Labs is thrilled to announce Polygon 2.0, the value layer for the internet. Polygon 2.0 makes mass adoption possible by offering users and developers unlimited scalability and unified liquidity. This mission is fueled by groundbreaking ZK innovations, including a first of its kind ZK powered interoperability protocol. And the next generation of the industry leading and widely adopted Plonky2 proving system. Polygon 2.0 will change the way we experience Web3 by bringing the security and decentralization of Ethereum to the scale and usability of the internet itself. Polygon 2.0 and all of their ZK tech is open source and community driven. Reach out to the Polygon community on Discord at Discord.gigi/0XPolygon to learn more, contribute or to join in on building the future of Web3 together with Polygon. And now here's our episode.

So today, Kobi and I are here with Or Sattath, Assistant Professor at the Ben-Gurion University in the Computer Science department. His research is focused primarily on quantum cryptography. So welcome to the show Or.

Thank you for inviting me.

Hey, Kobi.

Hi.

So what we want to do with today's episode is dive into this topic. I think we should start with a short introduction to yourself. Tell us a little bit about what you were studying and what got you interested in quantum cryptography.

Great, thanks. So I'm working on quantum computing and quantum cryptography. Quantum computing is a new and emerging area of computer science where the model of computation itself changes and it has dramatic implications, mostly actually on classical and quantum cryptography. So I'm interested in both of these aspects, both like, what are these implications and how to tackle the horrible consequences that arise from these changes. And also, what are the benefits? So that basically means, so in quantum cryptography, there are actually new types of phenomena that we can take advantage. So things like the fact that quantum states cannot be copied. So there is a theorem called the no cloning theorem, which states that generic quantum states cannot be copied. And, for example, this is useful for various tasks. And I'll give two such examples.

The first one is called quantum copy protection, which is really interesting. So, quantum copy protection is a compiler, which takes a classical source code, and outputs a quantum state. This quantum state allows you to run the program as usual as any compiled program allows you to do. But if I hand it to you, you cannot give it, another copy to your friend. Right? So if I give Anna one copy protected program, she could run it, she could also, you know, you could send it to Kobi, and then he'll be able to run the program. But it would be impossible for both of you to use the program without communicating.

At the same time? Okay

Exactly. So without communicating, only one of you could run such a program or such a copy protected program. And this, of course, classically this cannot be done, right? If I give you something, which could be run on your computer, Kobi could be run the same program as well, right?

Yeah. I'm just thinking about it in the context of I don't know, Star Trek transporters and things like that, where there is this usual worry where you create copies of the same person a few times. That sounds like something that should be borrowed in sci-fi movies in the future.

To me, it sounds even more like kind of, I think of like DRM software. Like, sort of like the data restriction, like making sure that there's no copies of MP3s out there or something.

Okay. So for MP3s, we know this, you cannot do that, right? There's no, this is like a cat and mouse game, and there's no way to do it. But for the same thing for like quantum MP3, right? If there's a way for me to run the or to listen to that sound, it could be copied. But here, there's no way or no efficient way to run all the possible computations and therefore computationally bounded adversary cannot copy the entire program by brute forcing it. So that's the main observation and that's like the, one of the possible applications. Another possible application is something called quantum money, where, again, unlike the physical bills and coins that we have in our pockets, these are quantum states that are generated by say a central bank. But they cannot be forged by the rules of quantum mechanics itself, rather than, you know, the police coming and, you know putting you in prison if you try to break it right? Or forge it. So it provides new capabilities and I'm trying to figure out these capabilities mostly.

I actually wanted to ask you a quick clarification. So you'd mentioned quantum computing, and then you mentioned quantum cryptography. There's like two different things there. Are they related, or are they like would quantum cryptography work in quantum computers only?

Exactly.

Okay.

So for most of quantum cryptography you need a quantum computer. There are very specific cryptographic primitives, which require only a limited form of a quantum computer. So think of it as a quantum calculator, right? In which you only need to prepare very simple states. Okay? And specifically, there's a protocol called quantum key distribution which is actually implemented in the industry. You could buy it, what, you know, it costs a few thousand dollars, and you could buy these boxes, connect them via an optic fiber. And you have a way to share keys in a way, which is in some sense more secure. But I don't want to get into that. That's a very specific application. And I guess my point is that for quantum cryptography there are elements which do not require a full-blown quantum computer. But definitely for all the topics that I discussed today, they require a full-blown scalable, noise tolerant quantum computer.

These are objects that are years and probably decades away. I'm not an expert on these matters about the attempts to build such computers, but definitely it's not something that we see on the recent horizon. So we have quantum computers, which have several qubits, say 100 qubits these days. But even more importantly, is the question how good their building blocks are. So quantum computers made out of qubits, and more important than the number of qubits that we have in the computer is how accurate they are. So if you apply a transformation to those qubits, usually there is some noise. And the most important aspect is how resilient they are to these noises that kind of arise in a natural setting. And what is really important is how many Nines do you have in that accuracy? And once we'll get to a few, I guess one more Nine there are ways to scale it to have more qubits and do error corrections and do all. So in theory, at least, we have a really good plan for how to do all these steps, but we need better legos, if you wish. Right? We need a really good lego chunks to start our quantum computer. It doesn't matter so much how many legos we have today. That's not such an important parameter, at least for me. That's the way I look at it.

I'm actually curious how much of the physics do you have to know or handle day to day? For example, you know, when I'm working as an engineer, I don't really look at the physics part of things. I just, you know, things are abstracted away for me, are things abstracted the same way for you? And you are working on quantum cryptography?

So that's one of the nicest thing actually in quantum computing. I think this is actually one of the major contributions of quantum computing to quantum theory at large, in the sense that it provides a really clean and nice model that abstracted the way similarly for you, that you don't really need to understand the low level physics that governs, say, the way your hard disc performs, or your memory performs, or your screen performs. Similarly quantum computing provides a really nice and clean obstruction that many of the aspects that were discussed for decades in quantum theory. These techniques, or this framework or language, allows you to explain it in much simpler terms without explaining all the detailed physics involved. I'll give one concrete example, although I won't get into the details. One such example is called Bell inequalities. If you look at what happens in physics, this is usually given as a master course level, and it requires quite a deep understanding.

I think I'll be able to, if you'll give me 30 minutes, I'll be able to explain it to you in much simpler terms in terminology that I'm sure you'll easily understand and appreciate. And if you would've come 50 years ago, I don't think this approach would've been possible simply because this abstraction was not available. And there are many, many, many such examples. This is not a one time thing right. There are many such examples where the, the framework or looking at things more from an information theory side, rather than, you know, a particular implementation turns out to be really powerful, useful and clarifies the really underlying ideas and allows you to kind of focus on the essence rather than aspects which are not so fundamental.

But you as a researcher, are you, like in the work you are doing, are you helping to create those models that are abstracted away? Or are you using models that are already abstracted away?

No, it's kind of weird, right?

To both?

No, to both

Okay

Which is kind of weird. you might say, okay, why don't you use those? So actually I'm a theorist. The thing that I use most is pen and paper. I prove theorems. I you know, design protocols, I do everything, you know, on my computer, on my classical computer. And with the help of mainly my students and the paper in front of me, it is rarely the case that I use a quantum computer or a classical computer for simulation though these things happen once in a while. But this is not, I wouldn't say this is my main tool that helps me in anything. I hope that in one day, you know, like even now, a classical computer is really useful for practitioners, right? They could test their series, they could see whether something is correct or incorrect without, you know, the burden of proving it, which, you know, is sometimes really hard, right? So the quantum computers we have today are unfortunately not enough to gain intuition regarding whether algorithms work or not, et cetera because simply they're not powerful enough. So that's one of the main reasons that I think most researchers do not use a quantum computer as their main tool.

When we talk about these quantum computers or quantum calculators, even I mean I think that the dream is quantum computers, but what do they actually allow for? What opportunities would this actually open up?

Great, quantum computers are not simply faster than classical computers, or they are neither a classical computer that runs in parallel. These are two things that are completely false. And sometimes people get the impression that this is the correct representation of those. And this is not the case. In particular, there is a model or a set of problems called NP complete. These are hard problems that have been studies for, you know, since the 70s and these are problems that can be solved on a computer, which runs in parallel, okay. That if you have like exponential parallelism, you could solve these problems. But quantum computers cannot solve these problems, right?

Okay.

So it does not allow, simply allow you for exponential parallelism. This is not the case. Instead, it's slightly more complicated. So if you remember before I told you that, like to think about these lego blocks, right?

And you could also think of algorithm as, you know, a bunch of lego blocks, right? You do some steps. Each step is a lego block. In this case it's a, say, Boolean gate, end gate, not gate, maybe addition multiplication, something, some simple operation that you're doing. And if you do it a step by step at the end, you'll have the correct result, right? That's how we view algorithms. The way you should think of a quantum computer is a computer in which you have a new type of legos, right? These are quantum gates, which allow you to do different types of operation, right? And sometimes for some concrete problems, it gives you a great shortcut. Instead of doing, you know, many step by step to reach the final destination, you find a really nice shortcut that allows you to reach that destination in fewer steps. It's not that each step is done in, you know, in just less time. It's simply that you use less steps in your algorithm.

Oh, does it mean you can do more complicated combinations in a weird way? Like you can, I'm just thinking of the XOR example or the NAND, like taking 2 and you know, if you want to make a multiplication, you have to kind of add a lot of adds together. But like, is it just a more elaborate function can exist in these smaller steps?

Yeah. So I guess in order to fully understand it, we kind of have to explain what a qubit is, and it could take a while. I'll just say that unlike a classical bit, which can be either in 0 or in 1.

Yeah.

A qubit could be in a super position, meaning it has some weight or amplitude on 0 and another amplitude on one and the transformation that you're allowed to do is far richer.

Wow.

Instead of being able only to do these classical transformation that we're used to such as AND, OR, NOTs and NAND, you have a few more options, okay? Now, one of the interesting aspects is that these weights could be negative. This is very different than probability theory. You could have negative weights. And the main idea behind quantum algorithm is kind of strange. The main idea in quantum algorithms is to design these steps in such a way that the weights on the correct answer add up and the wrong answer cancel. Think of it as there are 2 paths that leading you to the wrong answer. One, if one of them is positive and the other is negative, they could cancel out.

And on the other hand, if the correct solution adds up, you'll see that answer. So, designing a quantum algorithm is really hard. It's to design this intricate pattern. So this phenomenon is sometimes called destructive and constructive interference. You want to things to the wrong answer, to cancel out. And on the other hand the correct answer to construct, right, they both have the same sign, and therefore the correct answer would be in some sense boosted and design quantum algorithm turns out to be a really hard problem. We had a few breakthroughs, and I'll mention maybe 2 of those breakthroughs that are done in the 90s. So that that first major breakthrough that happened was done by Peter Shor. He showed that the problem of factoring could be solved efficiently on a quantum computer. So what exactly do we mean? What do I mean by efficiently?

What is this factoring problem and why is it such a breakthrough? The integer factorization problem is quite simple. If I give you 15, you need to give the, to spit out the number 3 and 5, right? The factors of 15 are 3 and 5. That's the problem. I don't think I need to explain more because it's such a simple thing that we all learned in school, right? Now, it turns out that if I give you a number with say, 100 digits, it's a hard problem. Right? In computer science, the way we classify problems by how hard or easy they are is we ask, if I give you a problem with say 100 bits, how long will it take you to solve that problem? How many steps will your algorithm need to do in order to give me the correct answer?

Now, it turns out that if I give you a number with 100 bits, the running time will be roughly exponential in that 100. On the other hand, when we have an algorithm which runs in a time, which is polynomial in that say 100 squares or 100 cubed, we say that we have an efficient algorithm. And indeed using a quantum computer, we have an efficient algorithm for factoring. And we are not aware, and we definitely tried to factor numbers on a classical computer, and no one has have ever found a classical efficient algorithm for factoring. Now, it's not a proved statement. We can't prove that there is no such algorithm. But it would have really important consequences if we do find such an algorithm.

And I guess like even in the classical world, we have a cat and mouse game, right? Where we need to choose how hard the problems are, but they're still always pretty hard. So for example, if we choose the size of our RSA modulus too small, it still can be something easy.

But if you add, you know, one more bit.

Exactly.

You make it twice as hard. So that's the main thing that, you know, by doing little bit more work, you make it twice as hard to the adversary. So if you are working twice as as hard, it'll be, you know, exponent much harder for the adversary.

Yeah, exactly.

So that's the thing that we are looking for. And the example that you gave is really important in the sense that factoring and related problems, which I'll mention next, are really crucial for cryptography, in one sense. So the way I look at cryptography is taking lemons and creating lemonades in what sense? We don't know an efficient algorithm for factoring that sounds like a lemon, right? We wish we knew such an algorithm, but in cryptography, we turn it into a lemonade. In what sense?

You use it

You use to create a, yeah so we use this fact that the, it's hard for an adversary to bind these factors and construct a secure protocol out of it. And that's the main theme in classical and actually quantum cryptography, we take, we kind of figure out what's the achilles heel of the adversary? What's something that he cannot do?

Yeah.

And construct a protocol based on that fact.

But going back to that point, you mentioned the first major breakthrough with factoring that was done efficiently. So if it is done efficiently, it breaks some concepts, I guess, or could potentially break

Cryptographic protocols. Exactly. So the idea was to take the lemon and turn it into a lemonade, but now it's not a lemon anymore, right? We can't use that protocol anymore.

Wow. Okay.

So that in some sense, it's a win-win scenario. That's the nice thing about cryptography. Either you have a secure protocol, or you had the breakthrough algorithmic improvement, right? Which happened here, we had an algorithmic improvement, which means that the protocols might not be secure once a quantum computer get to be realized. A full blown quantum computer so that's the main breakthrough that happened there. And I want to emphasize already, this isn't only for factoring, it's for many related problems. For example, you may have heard of the discreet log and various other related problems, order finding, discreet log over various like it could be on various groups. All these problems are solved on a quantum computer. So many of the cryptographic primitives that we use today, mostly for public encryption and digital signatures are actually broken by a quantum computer.

Theoretically, not actually yet?

Not actually yet. Of course, we need a quantum computer to do that.

Maybe

That's a good point. We can't even really know for sure. I don't think this is the case, but of course, this is a real it's something to consider, right? Whether maybe someone is, someone does have such a computer with and we just don't know about. It could be.

Is it always true given the decades of research that you have to redesign say a whole algorithm like Shor's algorithm to factor integers? Or have there been some developments in some generic kind of compilers to a family of problems or something of that sort?

Yeah, there are a bunch of families of quantum algorithms, if you wish. So, for example, Shor's algorithm can be generalized to something called the hidden subgroup problem. And there are definitely interesting questions there. For example, we know how to solve this problem for a billion groups. These are commuting, right? That these are groups in which, AB equals BA but we don't know for how to solve this problem for non a billion groups. And this is still a major open problem. We have other types of algorithms mostly related to linear algebra. I don't want to get into that because it's kind of tricky to explain all the intricate aspects there. It would take me a while. There are quantum walks, there are families of quantum algorithms. I think it is fair to say that quantum algorithms are extremely challenging.

It might, it might also just attract more researchers once quantum computers are here, because they will have something practical to work on.

Definitely. So the second breakthrough was an algorithm called Grover's algorithm. Grover's algorithm is really a general algorithm that can be used in lots and lots of use cases. So that's its power. Its main downside is that it only gives a quadratic speed up. So instead of spending, you know, some resource and you spend only square root of them, unlike Shor's algorithm, which gave us an exponential speed up. So this one only gives you a mild advantage if you wish, but it's the advantage here can be, you know, is relevant for almost all purposes. And I'll discuss, I'll explain what it is and you'll immediately see how useful it's, okay. So Grover's algorithm solves the, if you wish, the needle in a haystack problem. Suppose I put a long string behind the curtain, okay, let's call it X1, X2 up till XN. I promise there's a single I such that XI is 1. Your goal is to uncover that I, right? I don't tell you anything beyond that. Now you're classical. You can ask me, okay? Please reveal curtain number 5 and I'll open that curtain. The question is, many curtains do you need me to open in order to find, you know, the bit, which is the one.

The needle in the haystack? Got it.

Exactly, right. So the needle is the index in which XI = 1 and all the other is the hay, right? Suppose the string is of length, N or 100, what will you do? Give it a shot. Come on.

I have no idea.

Let, let's open all of them.

You go one by one, right? You ask me, okay, please open curtain number 1. I'll open it to you. You'll go, and there's clearly no better way to do it, right? You don't know where it is. The only way to do is kind of brute force. You go one by one.

Oh, wow.

Until you find the lucky number. Right? Now, Grover's algorithm solves this problem instead of by doing it for all the bits, right? Meaning N steps, it does the same thing using only square root of N steps. Okay? So you get your quadratic advantage, okay? I won't explain how it's doing that, but that's definitely something worth appreciating.

What does it apply to?

Let me give a concrete example. Suppose your goal is to find the number such that the hash of that number is below Y.

Okay that's familiar.

Does that sound relevant for something, right? This is proof of work, of course.

Yeah.

Right? So here you should think about the problem as finding the value I, such that that value gives you the number, like the low value. This represents the one, right? And that's your goal, finding that nonce, and that's exactly what Grover's algorithm gives you.

Okay?

Okay. Using square root N steps rather than doing these N steps. Now already you could see that I said that there's a needle in the haystack, but what if there are K needles in the haystack? Like in the problem with finding a nonce, there are clearly lots of good nonces. So classically, if you have K nonces, the number of steps you need is roughly N over K.

Yeah.

And in the quantum algorithm, you need square root of that meaning square root of N over K. So the more needles there are, you still have the quadratic speed up over the classical algorithm. That's the point.

I want to ask you though, this Grover's algorithm, is that a quantum algorithm? Is that it breaks this?

Definitely.

Okay. It is. And that's the breakthrough, definitely the actual creation of the algorithm.

Yes.

Okay.

Exactly. Finding this algorithm was a huge breakthrough, even though it's only a quadratic speed up, it's so useful that you could really apply it for tons of problems.

Wow.

Finding collisions for, there are really tons of applications.

And this one, like you were saying, sort of the proof of work thing. So this breakthrough, and this is only theoretical right now, it's the theoretical algorithm that would break proof of work if there was a quantum computer that could run it. Is this right?

I wouldn't say it breaks proof of work. It just would give you a quadratic advantage. Whether it breaks it or not is a matter of interpretation.

I see. Okay.

Yeah. Actually, what does it mean practically to have this quadratic advantage? Like how would it change the structure of like, the mining network of proof of work or?

Great, great. Okay. So we can definitely go into that. It was widely believed that the changes wouldn't be so dramatic.

Okay.

But I don't think this is correct. So I'll explain what exactly I mean, and what's going on here. So it was widely believed that when miners will switch to quantum mining, it would have little effect other than increasing the difficulty. Yeah. Right? Clearly they'd be more efficient. So you might say, okay, so who cares? The difficulty will increase.

Exactly yeah

Like they have a specific quantum miner?

Any quantum miner, okay? No matter how, you know, if you're strong or not so strong, but you need to be relatively weak. I won't explain what exactly that means. You're supposed to have a low hash rate compared to the entire network, as long as this holds the optical time to run is 15.93 minutes. Okay?

Okay.

Which is kind of weird, right?

Yeah.

It means that you run Grover's algorithm up to 15.93 minutes, measure and propagate that block to the other miners,

Okay

Which is kind of weird. I try to explain why this makes sense. The longer you run, the more advantage you have. On the other hand, if you run it for too long, chances are that another miner will find the block before you and it turns out that the sweet spot, you are the only quantum miner. So the other one would be classical and the sweet spot spot is exactly 15.93. Of course, the first thing I did was look at the distribution that, like what happens now in the blockchain and you know, it's supposed to be an exponential distribution. I didn't see any bumps. I was disappointed that...

That's reassuring or disappointing, depend on how you look at it.

So this basically means noone's been able to use one of these things, right, had you seen the bump?

Exactly.

Would it mean like, oh wow, someone's deployed this?

Yes.

Okay,

Look for the bump. If you start seeing a bump at 15.93 you know, something really interesting happened. I wish interesting there was an automated, you know, alarm that would send me an email once this happens. But yeah, I don't know. Still didn't happen as far as I know at least. Okay. And, and that's it. So the message here is that as long as there is a single quantum miner, we're safe. That's the message we get from both papers, even though we don't have proof for that. Remember that this is a simplified model. It's not the full protocol. That's like the caveat, I guess. Okay? But what happens if there are multiple quantum miners? Then things become much trickier.

Interesting.

And that's a crucial decision, that doesn't happen classically, the more you run the algorithm, the bigger your advantages and your risk of, you know, being front run by others. What's the problem? Suppose Anna runs her favorite quantum miner while I'm running mine. I plan to mine for 25 minutes and she planned to mine for 15 minutes only. Now she was lucky, right? She successfully found a block. What should I do? I already run my algorithm for 15 minutes, right? Should I throw it away and start mining on Anna's algorithm? By that I'm spending 15 minutes of resources, right? I spend 15 minutes on that.

You might have already found a block because of the property that you mentioned before.

The thing is that I should measure, I should stop. I could stop. There's nothing stopping me in Grover's algorithm. I could apply as many iterations as I want and stop whenever I want. I spent 15 minutes, even though I plan to spend maybe more, once I hear about Annas block, I'll measure. Okay? And all the network will measure for similar reasons and therefore the rates of block will increase dramatically, unlike now that the fork rate is really low and is related to block propagation reasons. Right? Now, there are blocks that are forks roughly once a day or maybe more even, right? That happens be because maybe Anna and I have found a block roughly at the same second, and I didn't hear about hers. Now it comes from a fundamentally different reason. It is because that I heard about Anna's block and measured and the reason is entirely different and therefore the rates of works would increase and be much higher, and we don't even fully understand what would be the ramifications of that, right?

Unless we change the rules. So I guess the bad news is that if we don't change the rules, the fork rate will definitely go high. We don't fully understand what would happen and what would be the ramifications but in that paper I suggested a way to get around this issue. Again, it's kind of delicate kind of tricky. I hope I'll be able to explain the idea. The idea is the following. Currently there's a tie breaking rule. What happens if Anna and Kobi have mined the block at roughly at the same time? On which one would I mine on top of Anna or Kobi? Currently the rule says mine on top of the one you've heard first. Right. Who? It doesn't matter much. Pick the one which you've heard. First. The idea would be to change the tie breaking room instead of simply mining on top of the one which you have heard first.

We do something different. Okay? And I'm cheating a little bit. The full details are in the paper. I'm not being very accurate here. The idea is that I'll mine on top of the one in which the timestamp is closer to the wall clock time.Why is that? Suppose Anna planned to mine for 15 minutes and you planned to mine for 25 minutes. When you start mining, suppose we all start mining at 8:00 PM you plan to mine for 25 minutes. So the timestamp in the block that you will find if you're successful would be 8.25. And on Anna's it's 8.15. Okay? Suppose she's lucky and you hear about her block, right? The time in her block, the timestamp in her block will be actually 8.15. It's really close to the wall clock time. Whereas if you're using the strategy, which I call the aggressive strategy, right? You've heard about Anna's block and you decided to, in some sense, cheat and measure. Your timestamps will be 8.25. So when I'll hear about your block, I'll say, no, no, no, I go with Anna.

Okay

I hope this makes sense.

Okay? Because you have to decide and test ahead of time, so yeah.

Yes, yes. You measured prematurely. Exactly. And I cannot notice this fact, and I take advantage to choose Anna, which was honest.

And that kind of restores the variance that you had in the classical world.

Yes.

Okay.

Yes. Yes. Now you say, okay, it restored the variance. Not yet. Okay? Not yet. Okay. Not yet, unfortunately. No, it's not that simple.

Okay.

So after that paper was published, there was another paper that studied what happens in that setting. So that paper was done by Maharshi Ray, Troy Lee and Miklos Santha at roughly the same time and they ask what happens? What's the equilibrium, right? What strategy should quantum miners use? And I guess I want to say that kind of even more broadly, I'm now going to say the drawbacks of that paper. I want to emphasize, these are great researchers. I am in good terms with them. That's the state of the art, right? They have done nothing wrong. Still, there are drawbacks in their paper, which I'd like to mention. And they are clearly stated in the paper. I am sure they'll agree to that. That's the main drawback of that paper. Okay? Still, I want to emphasize again, this is really lovely and, and nice research. So they analyzed what the strategy should these quantum miners use.

Now the main question here is how many Grover iterations should I do? It turns out to be really complicated. This, even though it sounds like a simple one. So after maybe 70 pages of game theory analysis, they give the answer but with a crucial simplification. So this is already extremely hard. This is 70 pages of hard work in a simplified model. The main drawback is this is a one-shot game. So they only consider what happens if you have a one shot. You need to decide on the number of iterations of Grover algorithm to apply if you, you're lucky if you're successful, great. Otherwise you lost the game, and that's it. In real life you can restart, right? Yeah, you can. It's an iterative game. The good news about the result by Lee, Ray and Santa is that they can analyze the probability of forks and that it is low.

There are two bad news. The first is that in order to mine, according to this equilibrium strategy, the miner needs to know the hashing power of all of the other miners. This is very different than the optimal strategy today, which is quite simple, right? Mine as fast as you can. So here, the more information you have about your competition, the more efficient you are and this may hurt decentralization. The second aspect is the one that I already highlighted. This analysis holds only for the one shot game instead of the iterated game. So we don't have a good understanding about the equilibrium in this case. And for example, maybe there are many equilibrium which could pose a problem.

Super interesting.

Can I ask you two clarifications? Just as someone who's not super, super familiar with mining, you had mentioned sort of checking, is that an action that like members of the network know you all? You also had mentioned the clock, and I'm not sure I fully understood what, or the real clock or something. What does that mean?

Okay, so for the second problem the second question is kind of easy. So each block contains the timestamp.

Yeah.

This timestamp in Bitcoin and Ethereum is barely used. You kind of use it for difficulty adjustments. Things like that. What I'm saying, no, no. Now it's going to play a real, a much more important rule for the type ranking rule. I'm not sure what are the implications of that? Maybe there are attacks because of these changes. I don't know. It's still, I guess, to be determined. One clock time is I look at the time that I have on my wall or on my real clock.

Yeah.

It might differ from the one that I see in the block. So suppose maybe my hand clock says 8.15 and maybe the timestamp inside the block could be 8, it could be 9, it could be 8.30. I don't know. It could be any time. Currently at Bitcoin we almost ignore that. And in most cryptocurrencies, this plays really a minuscule rule. Now I'm saying no, it'll play an important role for tie breaking. So that's the main change here.

I sort of understand that, but I'm just thinking like, so you sort of said somebody has 8.25, somebody has 8.15, but the person who's receiving it, I guess it has to be eight 15 for them at that moment. But like, would they

Sure. If you were honest, if you're honest, you plan to mine for 15 minutes. So the timestamp that you put in your block would be 8.15. You include that in your block. You remember that it's a field that you as a miner choose or have to add to your block. You could put any value you want. There is no way I could force you to do anything but then I can check whether that value makes sense or not. Currently, it's used mainly for difficulty adjustments. Meaning once every 2 weeks we compute the new difficulty and we see how long these, these 14 weeks of proof of work actually took. Right? That's how we use it today. That's why that stamp timestamp is even there. Otherwise you might say, why do we even need the timestamp? That's why it's needed or mainly why it's needed. What I'm saying now that we'll have another role as a tie for the tie breaking rule. Does that make sense?

Kind of. Except that the person who's doing the tie-breaking is the new block creator right? It's the next miner who's going to make a choice.

No, no

No, it's not

No, no, no. So Anna, you have found a block, you've found a successful block. You mined honestly. Kobi mined the block with while using the aggressive strategy. Right. In some sense, he was cheating. I call it aggressively because maybe some people wouldn't want to call it cheating, but between me and you, it's some sort of cheating. Now the point is that I, as an outsider don't care so much, right? I just need to choose. We need a tie breaking rule who cares, it's not such a dramatic, it wouldn't have such a dramatic effect, at least classically, but now it does. And the way that we want to do it is for me, or honest miners should mine on top of the blocks that mined honestly, or mind peacefully using the peaceful strategy rather than the aggressive strategy. That's the idea. And I can realize by looking at this timestamp and comparing it to the wall clock and understand that you were using the peaceful strategy while Kobi used the address aggressive strategy, and therefore I mine on top of you, at least if I'm honest.

So if I try to maybe rephrase it a bit, I think that the way that I kind of make sense of it is that because I'm using Grover's algorithm and I can't look at the results in this period of 25 minutes, I have ahead of time to say this is what's going to be the time in 25 minutes. And that's why when I look in 25 minutes, I want to have the correct timestamp but if I can't look in the middle without breaking the whole thing and restarting it. So if I look in 15 minutes, it's already going to have this future timestamp because that's, that was when I was supposed to look.

Perfect. Exactly.

We're talking about these breakthroughs that sort of like, change these dynamics. I mean, I think even though you've sort of said quantum computing may be many, many years off, how do we actually kind of transition from what we're doing now to these? Like if there are more breakthroughs or if these computers come online, like it sounds like it could be really disruptive if it just sort of happens without us really having any prep. So yeah. How do you transition?

Sure. So first of all, it's kind of sad in some sense that the biggest implications for quantum computing are actually sad news for the rest of us. In the sense that we don't care so much for factoring or discrete log or order finding, other than the fact that it's, the hardness assumptions are used for cryptographic protocols. So what that means is that once quantum computers are available, the most immediate concern is the bad consequences of that. Meaning, you know, our conversations are no longer private, our channels are no longer authenticated.

Encryption is broken.

Yeah. Encryption is broken, authentication is broken as well. So we don't know that the channels are authenticated. So for example, if I surf to my bank's website, this green lock not only says that I am I have a confidential discussion with my bank. It also mean that it's actually my bank. The channel is authenticated. Unfortunately, if you have a quantum computer, you could break that authenticated channel. You could try forge and try to communicate as if you are my bank, even though you're not. Now this problem was realized early on, and recently there was a NIST standardization for post quantum cryptography. So post quantum cryptography is classical cryptography, which is secure against quantum adversaries. Meaning it's a different set of protocols, right? It's a different encryption scheme other than the one we use to today, such as Elgamal or RSA or your favorite asymmetric key encryption.

And instead we use a different scheme, which is based on different hardness assumptions, things which are different than factoring discrete log, etcetera, such as learning with errors. This is, for example, a problem which I won't explain what it is, but it's a problem which is believed to be hard even for quantum computers. And why do we believe that? Because we've tried to solve it for 20 years using our brains. Right? And no one has found a quantum algorithm for that. No. This is a kind of a weak argument, right? We never had, no one can really tried,

Haven't found it yet

But at least the attempts, the smartest people on earth haven't solved it using their brains. That's the state of the art. And now NIST, the National Institute of Standards has decided on these new standards for post quantum cryptography, mostly for key exchange and for digital signatures. And now we have these new standards for these problems. It's not really finalized, but I won't get into these intricate issues, but probably in the next year or so, we'll definitely have implementations and everything that we expect to have from these standards. And that's the way to kind of prepare. Now, there are two things to remember for encryption. If you switch to post quantum cryptography, once a quantum computer is available, you're still at risk. Remember that the adversary could have saved the communication and save the communication from a month ago and a month later, once he has this quantum computer, he could break those messages. Right?

I see.

So especially for encryption, it's really important to have this gap. Right. If you believe that a quantum computer will be available in the next 20 years, and you want your communication to be private for 10 years, you have a budget of 10 years only right.

To transition into this new thing.

Exactly and transitioning takes ages. That's the thing we know from many, many examples. And therefore, it's kind of important to do it early on to have these standards to start implementing them, using them, learn whether they're broken or not, things like that before it becomes really urgent. And I guess for digital signatures, it's less important because if you, it doesn't matter much if I now surf to my bank's website, and the only thing I carry that it was really the bank, it doesn't help much for the adversary to break the digital signatures a year ahead. The adversary needs to do it now to break the communication to kind of forge and, and break the authentication. So there's a distinction there between encryption and authentication.

But going back to that encryption example you just gave, like what if they just saved all the encrypted things now and just wait 20 years? And so you maybe you can't decrypt the immediate things that are being talked about, but you could decrypt the past basically.

Yes.

Or deenencrypt. I don't know if that's. So that's already, we're already a danger of all of our encrypted messages eventually being read.

Yes.

Whoa, that's scary.

I think it's some something like fundamental right? And I think that you know, some systems are designing it such that, you know, they're already using, for example, plausibly post quantum safe algorithms for things like anonymity, like the Zcash people do, but they use other let's say discrete log based methods for soundness. And that's something that system designers should really pay attention to.

I want to mention one more interesting kind of architecture design choice. Another approach is to use something called hybrid cryptography. So the main downside of using post quantum cryptography is that we have little evidence that it is secure. On the other hand, we have all the reasons to believe that the classical or the pre quantum schemes are broken once quantum computers arise. So one way to get around this problem is to use both and that's called hybrid encryption. Meaning you encrypt your message using the first scheme, say the pre quantum scheme, and then encrypt that using the post quantum scheme. And as long as one of them is secure, you're golden. Okay? So that allows you to enjoy both worlds. Of course, there are some downsides, for example, post quantum schemes are usually less efficient, longer, much heavier, especially when it comes to digital signatures. but I guess we can discuss that in another show because there are, you know, specific aspects there that needs to be kind of addressed.

Got it. And actually, I was going to say, like we've unfortunately run out of time on this interview. There was a topic that we mentioned earlier, which was quantum money, which we didn't get a chance to touch on. Maybe we can just quickly mention maybe some other types of topics that people might want to explore, and hopefully we get a chance to do another show where we get to go into those as well.

Sure. So another interesting question that we studied recently, and I would definitely be happy to share, is techniques to deal with this migration. What happens if a quantum adversary becomes a reality and how do we deal with that kind of broadly and even more specifically in settings such as cryptocurrencies. And one technique that we introduce is called signature lifting. It allows you to take a pre-quantum scheme, meaning a scheme which is not secure against a quantum computer. And from that, create a different signing algorithm and a different verification algorithm, which uses the same keys. So you keep your keys, but change your algorithm.

Interesting.

So that's the new insight. Hmm. And it allows you to do it in a way which still allows you to use, say your Bitcoins, right? That you need to sign messages and verify those, etcetera. You could still use that you could use, still use your old keys to do just that in a way which is secure against these quantum adversaries.

We had also talked before the show, you had sort of mentioned this concept of the quantum canary. Is that also a talk we could do at some point in the future? Maybe you can just say what that is really briefly.

So the idea of a quantum canary is very similar to canaries, which were used in coal mines.

The canary in the coal mine. Exactly.

Yes, The idea is that canaries are, you know much more, much smaller dose of these gases killed them. And therefore once you see the canary dies, you, you know, okay, I need to get the hell out of here. Right. The idea of a quantum canary is similar. We want to create a small dosage of quantum in some sense, right? What does it mean that to create a challenge

What does it meant to break something?

Exactly that you need a smaller quantum computer to break. Ah, right. So you create a challenge which is easier than the full blown one so that you get a head warning and that allows you to create policies such as, you know, one month after the canary dies this and that is not allowed anymore. You have a different set of rules. We change the cryptocurrencies underlying rules to take into account that the quantum era has started.

Wow.

Or is going to start really soon.

This is awesome. I mean, all of this is so fascinating. I feel so relevant. I want to say thank you so much Or for coming on the show and sharing with us kind of your journey, like kind of helping to define some of these different categories, the breakthroughs, what they mean. I think we are definitely due for a follow-up episode with this one because it does sound like there's so much still to talk about. But thanks.

Thank you.

Thank you so much.

So I want to say thank you to the podcast team, Rachel, Henrik, and Tanya, and to our listeners, thanks for listening.