Episode 288 - Quantum Cryptography with Or Sattath

Transcript

foreign [Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online [Music] this week Kobe and I chat with or satut 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 ore 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 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 will 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 [Music] 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 plancky II proving system polycon 2.0 will change the way we experience web 3 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.gg forward slash zero X polygon to learn more contribute or to join in on building the future of web3 together with polygon and now here's our episode [Music] so today Kobe and I are here with or satat assistant professor at the bengurion 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 Kobe 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 what I'm 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 that arise from these changes and also what are the benefits um 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 statement there is a theorem called the no cloning theorem which states that Quantum generic Quantum States cannot be copied and for example this is useful for various tasks and at least I gave 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 right um and output the 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 Kobe 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 exactly okay 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 can be could be run on your computer Kobe could be run the same

the same program as well right yeah I'm just thinking about it in the context of uh 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 more 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 yeah okay so for mp3 we know this you cannot do that right there's no okay this is like a cat and mouse game and there's no way to do it yeah but for copy Quantum and the

same thing for for MP like Quantum MP3s right if there's a way for me to run the 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 um 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 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 um so it provides new capabilities and I'm trying to uh 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 like would Quantum cryptography work on Quantum in quantum computers only exactly okay so for most of quantum

cryptography uh 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 you know it costs a few thousand dollars and you could buy these boxes connect them via um an optic fiber and you have a way to share keys in a way which is uh in some

sense more secure but I don't want to get into that that's a very uh specific application and I guess my point is that for Quantum Computing there are elements which do not require full-blown quantum computer but definitely for all the topics that I'll discuss today they require a full-blown scalable noise tolerant quantum computer this is 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 are 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 uh revise in a natural setting and uh what's 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 uh 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 uh 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 uh an important parameter at least for me that's the way I look at it I'm actually curious how much how much of the physics do you have to know or handle day to day for example you know when

when I'm working as an engineer I I don't really look at the physics part of things I just you know things are abstract the way for me are things abstracted the same way for you when you're 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 abstracts it the way similarly for you that you don't really need to understand the low level physics that governs say the way your hardest disk performs or your memory

performs or your screen performs similarly uh Quantum Computing provides really nice and clean abstraction 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 and 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 um Bell inequalities if you look at what happens in physics this is usually given as a master course

uh level and it requires quite a deep of 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 have come 50 years ago I don't think that this approach would have 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 uh or looking at uh things more from an information theory side rather than you know a particular

implementation turned out to be really powerful useful and clarifies the the really underlying uh ideas and allows you to kind of focus on the the essence rather than aspects which are not so fundamental but you as a researcher are you like in the work you're 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 notable okay um which is kind of weird um 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

um I prove theorems I uh you know design protocols I do everything you know on on my computer on my classical computer and 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 uh 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 is you know is sometimes really hard right so the quantum computers we have today are unfortunately not enough to gain intuition uh regarding whether algorithms work or not Etc um because simply they are 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 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 so it does not simply allow you for exponential parallelism yeah this is not the case instead it's slightly more complicated so if you remember before I told you that like to think about this Lego blocks right then 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 Gates and gate not gate maybe addition multiplication something

some simple operation that you're doing and if you do it 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 the 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 con to 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 does it mean you can do more complicated combinations in a weird way like you can I'm just thinking of the sore example or the nand like taking two and you know if you want to make a multiplication you have to kind of add a lot of ads 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 the qubit is and it could take a while uh I'll just say that unlike a classical bit which can be either in zero or in one yeah a qubit

could be in a superposition meaning it has some weight or amplitude on zero and another amplitude on one okay and the transformation that you're allowed to do is far richer instead of doing being able only to do these classical transformation that we're used to such as and or not and and you have a few more options okay now one of the interesting aspects is that these weights could be negative this is this is very different than probability Theory you could have negative weights and the idea 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 two passes 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 they're the correct answer will be in substance boosted and designing Quantum algorithm turns out to be a really hard problem we had a few breakthroughs and I'll mention maybe two of those breakthroughs that you're done in the 90s so the first major breakthrough that happened uh was done by Peter Shore 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 uh efficiently what is this factoring problem and why is it such a breakthrough the integer factorization problem is quite simple uh if I give you 15 you need to give the to spit out the number three and five 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 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 uh 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 so 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 yeah to the adversary so if you're working twice it's as hard it will be you know much harder for the adversary yeah exactly right so that's the thing that we're 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 Watsons so the way I look at cryptography is making 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 algorithm but in cryptography we turn it into a lemonade and we'll use it you use it you use it yeah okay so we use this fact that the it is 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 they 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 if it is done efficiently it breaks some Concepts I guess or it could 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 yeah so we can't use that protocol anymore wow so that in some sense it's a win-win scenario that's the the nice thing about cryptography either you have a secure protocol or you had a breakthrough algorithmic uh Improvement right which is which happened here we had an algorithmic improvement which means that the the protocols might not be secure once a quantum computer gets to be

realized full-blown quantum computer right uh so so that's the main breakthrough that's 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 discrete log and um various other uh related problems order finding uh discrete log over various like it could be on various groups all these problems are sold on a quantum computer so many of The cryptographic Primitives that we use today mostly for public encryption and that your signatures are actually broken

by a quantum computer theoretically not actually yet not actually yet of course we need a Quantum maybe to do that right 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 uh it's something to consider right whether Maybe someone who's someone does have such a computer within we just don't know about it is it always through given the Decades of research that you have to redesign um say a whole algorithm like Shores 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 Shores algorithm can be generalized to something called The Hidden subgroup problem and they're definitely interesting questions there for example we know how to do to solve this problem for a billion groups these are commuting right okay these are groups in which a b equals b a but we don't know for uh how to solve this problem for non-abillion groups 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 um there are quantum walks there are families of quantum algorithms um I think it is fair to say that Quantum algorithms are extremely challenging um there have been developments in the area but at least from my perspective uh the grand breakthroughs were done in the 2000 and it's becoming harder and harder to squeeze uh and get nicer and nicer Quantum algorithms I hope that you know once the quantum computer gets realized

we'll have you know really new ways to test our theories and construct new algorithms simply by you know trying right which is something we cannot do today we we you know we're somewhat limited by the the uh our techniques for proving and for example you know like recently for example the the uh developments in deep neural networks and reinforcement learning and all these areas have been done by uh trial and error right which is something we cannot do today so maybe there's hope that once quantum computers will be realized we'll have uh a fresh new algorithms and and developments uh but

it could be the other way around right that will have a Quantum winter once a quantum computer gets very light and it turns out that yeah we can't uh do these uh miraculous things that we all hope to be possible so I'm not sure what would be the case 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 n you spend only square root of n unlike Shores 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 is okay so so the 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 X One X2 up till x n I promise there's a single I such that x

i is 1. your goal is to uncover that I I don't tell you anything beyond that now you're classical you can ask me okay please reveal curtain number five and I'll open that curtain the question is how many curtains do you need me to open in order to find you know the bit which is the needle in the landing stack got it exactly right so the needle is the index in which x i equals one and all the other is the hey 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's open all of them you go one by one right you ask me okay please open curtain number one I'll open it to you you'll go over 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 can 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 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 okay why that's familiar that sound um relevant for something right this is proof of work of course yeah right so here you should think about the problem as finding the nouns 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 and steps rather than

doing these end steps now already you could see that I said that there's a needle in the haystack but what if there okay needles in the haystack liking the problem with finding a monster clearly lots of good nonsense so classically if you have K nonsense 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 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 definitely okay it is and

that's the Breakthrough this is the actual creation of the algorithm yes 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 for tons of problems wow finding collisions for uh 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 before it just would give you a quadratic Advantage whether it breaks it or not is a matter of interpretation I see okay yeah

actually actually what does it mean um practically to have this quadratic Advantage like how would it change the structure of like the mining network of proof of work great great okay so we can definitely go into that uh it was widely believed that the changes wouldn't be so dramatic okay but I don't think uh this is correct so I'll explain what exactly uh 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 clearly they'd be more efficient so you might say okay so who

cares the difficulty will increase exactly it's still it's still hard right yeah and recently or like in 2019 Uh kojo current I'll indeed even prove that in a simplified model called the Bitcoin backbone protocol with a single Quantum Miner indeed there are no drastic downsides to the security I want to mention one more really interesting fact um two years ago roughly neriment Gower noticed an interesting um phenomenon it turns out that if you have a single Quantum minor the optimal time to mine is

15.93 minutes okay it's an analytic solution to a function called the Lambert function for reasons reasons which I won't get into but that's the optimal time to run if you're a single weak one to mine like they have a specific Quantum minor any Quantum minor 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 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'll 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're the only Quantum Miner so the other one would be classical and The Sweet Spot is exactly 15.93 uh of course the first thing I did was look at the you know the distribution that like what happens now in the blockchain and you know it's supposed to be a geometric uh sorry an

exponential distribution uh I didn't see any bumps I was uh that's reassuring or disappointing depend on how you look at it so this basically means no one's been able to use one of these things right had you seen the box would it mean like oh wow someone's deploying this okay look for the bump if you start seeing a bump at 15.93 uh you know something really interesting happened I wish there was an automated you know alarm that would uh send me an email once this happens but uh yeah I don't know still didn't happen as far as I know at least okay and that's it um so the the message here is that as long as there is a single Quantum Miner

we're safe that's the uh message we get from both papers even though we don't have a 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 why is that that's slightly tricky and I'll try to explain this was discovered in 2018 by me that paper is called on the insecurity of quantum Bitcoin mining yeah and I think the reason is not too complicated suppose you're a classical Miner and now

you hear about another block propagating through the network what do you do you simply switch to mine on top of the new block right nothing really interesting happens other than you switching to mine on top of the new block now suppose you're a Quantum Miner and everyone are quantum mining their blocks right now when you mining using a Quantum Hardware you need to choose how much time should I run my Grover's algorithm how many iterations should I apply should I apply them for five minutes for 20 minutes for 15 minutes I'll do these steps and only at the very end we'll measure 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 right I plan to mine for 25 minutes and she planned to mine for 15 minutes only now she was lucky right she found a success she successfully found the block what should I do I already run my algorithm for 50 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 couldn't stop there's nothing stopping me in Grover's algorithm I could apply as many iterations as I want and stop whenever I want yeah I spent 15 minutes even though I plan to spend maybe more once I hear about Alice block I'll measure okay and all the network will measure for similar reasons okay and therefore the rates of block will increase dramatically unlike now that the foregrate is really low and is related to block propagation

reasons right now there are blocks that are Forks roughly once a day a day or maybe more even right that happens because maybe Anna and I have found the 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 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 the way to get around this issue again it's kind of delicate uh kind of tricky I hope I'll be able to explain the idea the idea is the following um currently the there's uh the tie breaking rule what happens if Anna and Kobe have mined the block at the same time roughly at the same time on which one would I mine on top of Anna or Kobe currently the rule says mine on top of the one you've heard first yeah right

who it doesn't matter much pick the one which you've heard first the idea would be to change the tie breaking rule 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 plan to mine for 25 minutes when you start mining suppose we

all start mining at 8 pm right you plan to mine for uh 25 minutes so the timestamp in the block that you will find if you're successful would be a 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 timestamping hair block will be actually 8 15. it's really close to the wall clock time whereas if you're using this strategy which I call the aggressive strategy right you use the you've heard about Anna's block and you decided to in some sense cheat and measure yeah your

timestamps will be a 25 so when I'll hear about your block I'll say no no no I go with Anna hmm I hope this makes sense okay because you have to decide on Dust up ahead of time so yeah yes yes you measured prematurely and I can 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 okay now you say okay it restored the variance no no okay not yet not yet unfortunately no it's not that simple okay so after that paper was published there

was another uh paper that studied what happens in that setting so that paper was done by marashi Ray Troy Lee and miklosstantine roughly the same time and they asked 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'm 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'm sure they'll agree to that that's the main drawback of that paper okay uh 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 the only consider what happens if you have a one shot you are have a chat 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 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 uh 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 equilibria 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 would mention 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 what does that mean okay so for the second problem the second question is kind of easy so each block contains the timestamp yeah um this time time 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 gonna play a real a much more important

rule for the typewriting rule I'm not sure what are the implications of that maybe there are tax because of these changes I don't know um it's still I guess to be determined wall clock time is I look at the time that I have on my uh wall or on my real clock yeah it might differ from the one that I see in the block okay right so suppose maybe my hand clock says 8 15 and maybe the the timestamp inside the block would be eight it could be nine it could be 8 30.

I don't know it could be any time currently the Bitcoin we almost ignore that and in most cryptocurrencies this place is really a minuscule rule now I'm saying no it will imply play an important rule for tie breaking so that's the main change I sort of understand that but I'm just thinking like so you sort of said somebody has 825 somebody has 8 15. but the person who's receiving it I guess it has to be 815 for them at that moment but like 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 you include that in your block okay right

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 two 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 uh that's why that time stamp 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 uh what I'm

saying now that will have another role as a type 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 so Anna you have found the blog you've found a successful block new mind honestly Kobe mind the block with while using the aggressive strategy right in some sense he was cheating I can't mean it aggressively because maybe some people wouldn't want to call it cheating but between me and you it's some sort of cheating okay um 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 uh effect at least classically but now it does and the way that we want to do it is for me or honesty miners should mine on top of the blocks that mind honestly or mind peacefully using the peaceful strategy rather than the the aggressive strategy that's the idea and I can realize by looking at this time stamp and comparing it to the wall clock and understand that you were using the peaceful strategy while Kobe used the aggressive strategy and therefore like

man 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 a head of time to say this is what's going to be the time in 25 minutes and that's why I when I look in 25 minutes I want to have the correct timestamp um but if I 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 time stem

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 I think even though you've sort of said Quantum Computing maybe 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 uh 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 yeah 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 serve to my bank's website this green lock not only says that I'm have a confidential discussion with my bank it also means that it's actually my bank yeah the channel is authenticated unfortunately if you have a quantum computer you could break that authenticated Channel you could words and try to communicate as if you're or my bank even though you're not now this problem uh is 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 and say encryption scheme other than the one we used to today such as El Gamal 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 Etc so 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 like no and no one has found a Quantum algorithm for that no this is a kind of a weak argument right we've never had no one happy yet but at least yeah at least you the attempts the smartest people on earth haven't solved it using their brains that's the state of the art and now Nest 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 don't 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 uh standards and that's the way to kind of uh 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 say save the communication from a month ago and a

month later once he has this quantum computer he could break those uh messages right so especially for encryption it's really important to have this uh 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 exact thing okay 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 to have these

standards to start into implementing them using them learn whether they are 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 if I now serve to my uh Banks 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 address needs to do it now to break the communication to kind of Forge and break the authentication so there's a distinction there between encryption and Authentication 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 the encrypt I don't know if that's yeah so that's already we're already in danger of all of our encrypted messages eventually being read yes whoa I think it's some something like fundamental right and I think that you know some systems are are designing it such that you know they're already using for example plausibly post Quantum safe algorithms for things like anonymity like the zikish people do but they use other

um let's say discrete log based methods for soundness and that's that's something that system designers should really pay attention to I want to mention one more interesting kind of um architecture design choice another approach is used to some use something called hybrid cryptography so the main downside of using post Quantum cryptography is that we have little evidence that it is secure okay on the other hand we have all the reasons to believe that the classical or the pre-quantum uh 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 yeah meaning you encrypt your message using the first skin say the pre Quantum scheme and then encrypt that using the post Quantum screen scheme and as long as one of them is secure you're golden okay so that allows you to enjoy both worlds of course the Downs there are some downsides for example post Quantum schemes are usually less efficient longer much heavier this especially when it comes to digital signatures but I guess we can discuss that in that in another show because they're you know specific aspects there that needs to be kind of

addressed got it and actually I was gonna 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 as 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 um one technique that we introduce is called Signature lifting it allows you to take a break one to scheme meaning a skin which is not secure against the 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 and that's the new insight 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 Etc so you could still use that uh you could you 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 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 Cannery is very similar to canaries which were used in Coal Mines right the canary in the coal mine exactly yes the idea is that Canada user you know uh much more much smaller dose of these

gases kill 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 the quantum Cannery is similar we want to create a small dosage of quantum in some sense right what does it mean Something challenge something exactly that you need a smaller quantum computer to break 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 Cannery dies this and that is not

allowed anymore you have a different set of rules we change the cryptocurrencies uh underlying rules to take into account that the quantum era has started or is going to start really soon this is awesome I mean all of this is so fascinating I feel so relevant uh yeah 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 tour listeners thanks for listening foreign