Episode 297 - Quantum Cryptography Part 2 with Or Sattath

Transcript

[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 this week Nico and I chat with or satat and revisit the topic of pre-quantum postquantum and Quantum cryptography this is the second episode I've done with or and I will be adding the link to the previous episode in the show notes if you want to check that out

before listening to this one in this conversation we cover how we can transition from a pre-quantum environment to a postquantum environment looking at existing systems like Bitcoin and ethereum we also talk about the challenges in these designs and the complications that can arise when moving between these two states we then discuss the history of quantum money and the more recent work on this topic before we kick off I want to let you know a little bit about ZK hack Istanbul our IRL hackathon happening November 10th through 12th just want to remind you that if you haven't already be sure to get your application in and if you have been accepted be sure to RSVP only those at RSVP will be admitted we've added the link in the show notes and we hope to see you there now Tanya will share a

little bit about this week's sponsor Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission of a truly secure internet Alo has interwoven ZK proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's unparalleled in its approach Alo is ZK by Design dive into their programming language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps as Alo is gearing up for their main net launch in q for this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at

al.org so thanks again Alo and now here's our [Music] episode So today we're here with orat assistant professor at the Ben Goron University in the computer science department his research is focused on Quantum cryptography welcome back to the show or thank you for having me so this is our second time doing an episode on Quant cryptography with you Nico is joining this one as the co-host hey Nico hello hello super happy to be here yeah so in our last episode we did get a chance to cover quite a lot of ground we explored the concept of quantum cryptography that is cryptography built for a quantum computer environment we also looked at some of the breakthroughs

in the space the Grover's algorithm Shores algorithm and the difficulties of Bitcoin mining in the presence of multiple Quantum adversaries but at the end of the episode we sort of went through all these other topics that we could have covered and this is what we're going to get a chance to dive into today and I will add the link to that in the show notes for anyone who hasn't heard that episode I definitely recommend listening to that one first because I think it lays quite a lot of foundation for this one I wanted to pick up from where we actually ended the last episode one of the topics that we didn't get a chance to really cover was this idea of the migration from a prequantum to a postquantum environment you

mentioned it like in two sentences but yeah can we talk a little bit about what that entails what would it even mean to make that migration sure so just to give the um terms involved so we talked about Quantum cryptography which is the field of protecting against adversaries using Quantum Computing meaning you need a quantum computer and maybe a quantum network to use these uh tools post Quantum cryptography on the other hand is classical cryptography which is secure against Quantum adversaries and prequantum cryptography usually means cryptography which is secures against

classical adversaries but not against Quantum adversaries so maybe I should reward even that question so it's not really prequantum to postquantum that would just be the same type of cryptography potentially it's prequantum to Quantum cryptography so I guess we'll talk about both of these options during this episode today I hope we'll get to the second one like purely quum cryptography but this would be in the second part if we'll get there okay got it as we mentioned in the previous episode cryptography is based on the idea of turning a lemon into a lemonade in what sense we have a hard computational problem which sounds like

a lemon right you can't factor numbers efficiently you can't find the discrete log right efficiently which sounds like a lemon and you turn it into a lemonade why is that important in cryptography because you want to find something that the adversary cannot do so here is the thing that the adversary cannot do right the adversary cannot factorize integers etc etc now what's the problem as was mentioned in the previous episode some of the problems which are hard for classical computers such as factoring and discrete log are in fact easy for Quantum Computing because of sh's algorithm and some of its variance so what do that mean it means that some of

our protocols at least are not Quantum secure right if you have a Quantum adversary he could break your scheme and in particular almost all of the asymmetric cryptography which is used in practice is prequantum meaning a quantum computer could break it and specifically the digital signature is used in most cryptocurrencies so what that means is once Quantum adversary or quantum computer is built our system is not secure anymore and although this is relevant for almost all modern systems that use cryptography which is basically everything used in practice uh I won't

touch upon all the various aspects and try to concentrate this uh meeting discussing only the context of cryptocurrencies MH so how do we deal with this uh challenge so one approach or the main approach is to switch to a different hardness assumption and there are quite a few such assumptions and indeed there is an ongoing standardization process for postquantum agreement and digital signatures done by the nist National Institute of Standards and we already have uh several candidat Cates for both of these Primitives but unfortunately these candidates are not

as well-rounded as the classical counterparts so one of the top candidates which is most suitable for cryptocurrencies is called Falcon and the parameters which are relevant for cryptocurrencies are quite uh interesting right what are you interested in terms of the performance of digital signatures the area of cryptocurrencies right so there are actually several things you could look at you could look at the public size you could look at the signature size and you could look at this CPU time for signing and verification and maybe also on memory constraints right and for example if you look at the public key size and

signature size together in Falcon it's roughly 1 and a half kilobyte if you look only at that size compared to roughly 100 bytes in most cryptocurrencies such as Bitcoin and ethereum right so you're already an order of magnitude above why that important even if we only look at the signature size so imagine a system such as Bitcoin whereas the block size is kept fixed right if the signature size goes 10 times uh bigger it means that your throughput goes down

by a factor of 10 right so it's not only of the computational resources by the user that we we are concerned by the system as a whole and uh unfortunately the throughput in a cryptocurrency drops by a factor of 10 that's a big deal I would say another secondary interesting aspect is kind of more in in the periphery of these questions uh for example these days we have uh Hardware wallets right these Hardware wallets use really tiny CPUs and maybe they won't be able to use some of these candidates I don't think anyone even even tried to do

that as far as I know right because they are much heavier to use maybe they need lots of memory Etc so that's another kind of interesting aspect I almost wanted take a quick break there and sort of ask you about these new signature schemes and all these new standards so as you said like we start from lemons and we want to make lemonade what kind of lemons are we using here and are all the candidates using the same lemons oh that's a good question so first of all I would say that I'm not an expert in that area there are several lemons one of them is the learning with errors problem which is tightly related to questions related to luses so is the shortest

Vector problem Etc there are others as well but unfortunately all the candidates for signatures that were kept as the finalists use the same family um and that's why they made another attempt to look for more candidates because that's a kind of a bummer right we want to have a some diversity there yeah diversity so that if something breaks Etc that's the main point another important relevant uh approach is called hybrid cryptography which we'll uh hopefully get to in the rest of the episode sounds good so in most

cryptocurrencies there is already a risk in some sense right there's something which we call unsafe coins what are unsafe coins uh these are bitcoins eth whatever that once that there's a quantum computer they are at risk the adversary could loot those coins specifically in Bitcoin roughly onethird of the Bitcoins are unsafe I'll share the link for the paper that studied that question and there are two main reasons for that and I guess we even need to understand how most cryptocurrencies used and why aren't all of them yeah unsafe when you say onethird that sounds

so counterintuitive yeah so interestingly if you get ecdsa public key you could get the secret key using a quantum computer right so at this point the adversary could Forge messages on your behalf so that sounds really bad interestingly in Bitcoin the standard approach to use a an address is actually not to post your publicy instead you post something like the hash of your publicy and as you may remember for that quantum computers are not so good for these types of questions you need to use Grover's algorithm which was discussed

previously and that only gives you a quadratic advantage that's not such a big deal so addresses in which the public key is hashed these are safe now when do you reveal the public key when you spend it right when you spend it instead of saying just okay this is my signature you basically say okay this was my public key you could check it by hashing it and see that they agree and then you attach the signature and if you haven't ever signed a message using your signing key your Bitcoins are safe does this then mean that like 2third of Bitcoin addresses have never signed exactly really oh I

didn't know that not sorry let me be more precise it's not 2/3 of the addresses it's 2/3 of the coin coins okay right these are not exactly the same things okay if you want to know the number of transaction this is like 70 million roughly that are unsafe this is the number interestingly the ones which are unsafe usually or at least the the biggest ones in terms of volume in some sense are the ones by Satoshi so there are very few but they are you know worth lots and lots of Bitcoins so so the the mismatch here is quite large so as long as you use something which is called P2 PK pay to public hash as long as you haven't reused an address which is the

best practice your Bitcoins are safe interestingly this is not the best practice in ethereum right so different cryptocurrencies have different approaches to these questions and therefore e theorem is more prune to these attacks but under that assumption your coins are are safe interestingly as I mentioned Satoshi used a different standard in the very early stages which is called P2 PK and therefore most well we don't really know etc etc but we believe that most of his coins were unsafe for this weird technical reason okay uh so so you might think that okay maybe for the safe coins we

we're okay because their public key has not been revealed and therefore okay we'll simply switch to post Quantum cryptography before the quantum adversary takes our money so what's the problem there suppose now there is a Quantum adversary and you have money that you want to spend okay how do you switch to use the postquantum cryptography right MH how do you prove that you're the owner so as soon as I do as targeted by the quantum adversary right exactly in order to spend that money you need to post the transaction to the menol right once it's in the me public key or public which reveals your publicy once it's in the

menol the adversary could break it and post an alternative transaction which steals all your money interestingly this question was raised uh I think in 2013 already by vitalic butterin and he kind of uh gave a first shot I guess that's a way to describe it solving this issue so what he suggested was to use a very simple approach to get around this issue instead of Simply posting your transaction we'll use something which is called a commitment scheme in a commitment scheme you first commit to a message and then reveal it now if you committed to something there's a way to

do it in a way which is secure against Quantum adversaries basically you hash the message so instead of just revealing your transaction you post commitment or the hash of that message to the blockchain then you wait a few confirmations so that things wouldn't be turned around against you and then reveal the transaction so that's the approach that he kind of uh suggested as a way to get around this problem you see because at the uh Second Step after you reveal in order to steal your money the adversary has to do this commitment a few blocks behind so that's too late for the adversary to do that I hope that makes sense mhm that does yeah okay but there's a gap here in this argument

which I don't know if he's spotted already or it wasn't mentioned definitely in his proposal it was mentioned by the way by others but I think that in his blog post it wasn't mentioned can you think about it it's kind of interesting I want to give the audience as well a minute to think about it where's the problem here and I already mentioned that it's related to the commitment just to go over it again though so do you put forward your key towards the commitment scheme or do you create a commitment scheme that includes so basically you just think about it as you instead of posting the transaction itself at the first stage you only post the hash of the transaction mhm and wait say 10 blocks and then reveal the transaction itself okay and everyone

agrees that in order for a transaction to be valid it first has to be committed to and then revealed 10 blocks or more after as long as there is no commitments it's invalid you know after the reveal phase the adversary could break it right he could reveal your secret key but he's he has lost the race because it's too late right it's already published on the blockchain now and there's no way for him to post a competing transaction okay but you're looking for the hole in this is it that just by posting the commitment schi or the hash you're already revealing no because Quant computers cannot like uh undo the hash they cannot break the the properties of

a hash function efficiently is it a case that we need very strong censorship resistance because at the point where I'm going to reveal the stuff I committed to if you censor me H then suppose you know yeah yeah that's actually not so much the issue interesting right yeah how do you post the commitment who pays for the commitment the gas the gas that's the is the gas the gas it how there's no way for you to prove that you're the owner and therefore you have no way of paying gas yeah so the fee turns out to be a really important loophole in this argument you see this is why the proposal he made wouldn't satisfy this

problem it's not fully yeah it doesn't solve this this issue of gas would by having gas like you create the hash would it cause the reveal or it just you couldn't do it if I'm allowed to Simply post hashes on the blockchain that would be a nightmare and at that point when I'm posing them maybe I'm not the owner there's no way for me there's no way for anyone to be sure that I'm really the owner right yeah so that's the Gap that we kind of uh need to solve do we need a separate Quantum secure chain or postquantum secure chain I guess to be precise um to which we can post commitments with its own fee and then go back to that um so let me take it in two

steps so first first of all this idea of using a commit and reveal scheme was also presented in a paper by uh Miller and boner called Fox coin which had also interesting other ideas but they kind of addressed this question directly about the fees and they were suggesting okay either we have a direct side payment between the user and the minor for example you know use PayPal to pay for the fees or maybe if you have another post Quantum address you could use that that right if you already have a few Bitcoins which are quantum secure to pay for the fees then you could use that address right so these are the two kind of but what do we do with users who

didn't uh this on ramping right they need to get their first postquantum coins how do they do that so in a joint work with my student shy VI borski we showed a different mechanism to resolve the issue of fees and this approach is based on a general technique which we called the signature lifting and the idea there is the following suppose you have an existing Quantum unsafe signature scheme or a prequantum signature scheme with a signing key SK and the public key PK a signature lifting scheme is post Quantum signature scheme which uses the old Keys okay so you use the same keys but with a

different signing and verification algorithm okay kind of weird huh it sounds very so where my intuition is now failing is with discret log based schemes the problem was as soon as I see the public key I can find the private key how do we get around that great great okay so the important ingredient which we need is that there is a something which we call a postquantum step that there's something post Quantum taking you from the secret key to the public key so if you simply use ecdsa there's no such postquantum step so as you mentioned niik indeed the ecdsa scheme which is used in Bitcoin and

ethereum if the publicy is not hashed then there is no such postquantum step because you could simply recover the secret key from the public key okay so you need something else so our approach before getting into the details is based on one of the postquantum signature schemes that was submitted to nist called picnic and this uh scheme has an interesting idea it's based on any postquantum oneway function so let me remind you a one-way function is a function which you could evaluate given X you could evaluate F ofx efficiently but given Y which is f ofx you can't find any pre-image of y such as X or anything else that evaluates to F ofx

hash functions are a good example such as function more concrete yeah yeah exactly so definitely hash functions are such a one-way function they have even more properties so in picnic the signing key is simply a random X and the public key is simply F ofx that's it uh so it's it's a if you want you could think of it as a transformation it takes a one-way function and gives you a signature scheme so the transformation needs to be be postquantum right but as I mentioned again and nicoo kind of is already troubled right the transformation that we are discussing is not postquantum so

what on Earth am I talking about so the point is that for example if it's not that the public key here is simply the ecdsa public key but the hash of it then we are golden right so that solved the first issue this deals with then that gas issue like the gas issue is taken care of how is it taken care of though I don't really get it because you could already sign messages using your old Keys oh yeah okay everyone knows the hash of your public key the only one knowing that knows the secret key is you and now you have a signature scheme which is postquantum secure okay to even make

that change though like where's the change happening is this happening like on the client software side like I don't definitely definitely you need to upgrade all yeah yeah yeah yeah you need to switch to some kind of a fork probably soft fork or hard Fork it kind of needs to be determined I I I we didn't get into those questions uh at least if you do it navely definitely a hard fork and everyone agrees that the old schemes are gone and then you use the picnic scheme with that specific one-way function as your new verification and signing algorithms right so everything needs to be changed

definitely it's not a it's not a minor thing this is a practical point but I just given the rate of change in the Bitcoin example like I can imagine being very difficult to get that change through sure right like there's a lot of resistance to this sure so in the previous episode we discussed the timelines that people are considering as realistic so we definitely have have some time at least a few years but it is unclear how long do we really have do we have 10 years uh 5 years 15 years that's uh clearly the the the you know fastest we do it is the better right and it will will require quite a drastic change okay

so so again the idea would be that you could use your old keys and sign your messages instead of using ecdsa you use this picnic scheme okay so now there there are kind of various questions one is okay this is a theoretical construction how good is it is it okay and this is the bad news the numbers are terrible okay the like the speed or like the size of the signatures is roughly for shatu 56 it's 600 kilobytes you remember that in in the Bitcoin it was something like 100 bytes it's three orders of more than

three orders of magnitudes longer signatures so that's terrible okay and it's not even precisely what we need that's for shadow 56 here we need to use a slightly different oneway function so I guess the bottom line is that's pretty bad so we'll discuss how to kind of uh optimize it or optimize it in some sense and maybe pay with in other terms but but at least we don't need to kind of use half a megabyte per signature so that's the first thing the second thing is well what do we do with the others coins right coins which are not Quantum safe ah this is because we're still talking about the 2third of the Bitcoin

YES Network or a number of coins that have not been made where public keys are still and in ethereum I don't even have the numbers but probably you know the the the vast majority is unsafe so can't even use that wow so now we're trying to tackle that onethird that has used their public key exactly and the ethereum addresses which was used for you know you spent part of your eth on and bought some ice cream I don't know what do we do with that I want to give the audience a second to think about it the challenge here is that the public key is already revealed which means you already know

the secret is there something still that the adversary does not know notice that at this point if you have a Quantum adversary he knows your secret key it sounds like game over but I'm arguing this is not the case that there is a way to fix that and you still has an advantage over the adversary and I'll give you a hint what you should think about is how do you start using Bitcoin ethereum whatever what's the first thing that you do and how does that process begins the wallet the seed phrase no yes seed phrase okay yes okay you have the seed how is the secret key generated from that seed yeah

uses a hush function yeah and again you have the seed there's a there's a postquantum step here which you could use and again the same idea holds now it's way more complicated whoever is interested can read the paper unfortunately it's really tedious uh if you want I can try to explain why it's not so trivial so wait your ecdsa private key now becomes your public key and the seed becomes your private key exactly wow oh kind of weird but like would it not make sense then to do that just for the entire network like why do the two different techniques for the safe and unsafe that's a great question um honestly we don't know the numbers I

suspect that the one based on the seed is way more complicated because to the very least the proofs are way nastier way way way nastier but I'm not sure how the the numbers will turn out yeah um it's called the derivation path right how do you derive your secret key from your seed right it's kind of complicated and it's not formally it's not simply a one-way function there are several technical things that need to be addressed I'm not sure how they'll turn out but this is definitely an option I mean uh um for most people I'll give you one example where it's not suppose you created a P2 PK right uh pay to public hash address in

2011 there were no HD wallets at the time right so you can't use the other approach because the the user doesn't have the seed right so for those users you definitely need to have these uh the first approach that we discussed and probably it would be more efficient so so probably that's another Advantage I wanted to just do one clarification this is just making me realize something that I hadn't really thought of but like there is no way to from the secret key derive the seed I guess like that's one way always okay because that's the postquantum step there's a hash function there the adversary cannot break that hash okay so that's again that's Grover's algorithm

only a quadratic speed up for things involved in that postquantum step okay and that's kind of a miracle right there was no real reason that the derivation should have been postquantum but people chose a postquantum um you know procedure for for you know really orthogonal reasons which has nothing to do with uh they definitely didn't think about picnic when they derived because the picnic was invented later right so no one could have uh guessed that this is going to be turn this is going to turn out so useful uh but yeah we we can definitely take advantage of it another quick question about this um quadratic speed up does this actually mean like having the number of bits of security yes and

is that not still quite significant sure uh but uh still you know for has reducing the number of security bits by a half is okay you know you cannot parallelize it so that's another kind of big advantage that that cannot be you know so the last issue that we need to address is related to the signature sizes right we remember these are turned out to be 1 and a half megabytes at least instead of 100 bytes so actually what do we do is kind of construct a way to do to enjoy both worlds the user sends a commitment but also the postquantum signature using this uh

signature lifting technique which we discussed the minor post this commitment and keeps the signature just in case the user tries to cheat okay and only if the user fails to reveal the minor post it's on the blockchain and there are many many kind of things that you need to consider and I won't do it here if you want go ahead and read the paper and we try to deal with all the question that arise because of these things like denial of service attacks and many other questions uh but I think we we don't need to get into that in this discussion okay so this sort of fixes our problem I guess next question is how do we know if

computers are around I think you mentioned canor last time what do those look like sure so one of the challenges is when do we make these adjustments right when do we s switch to this postquantum signature schemes you don't want to do it too early because from that point onwards some money will get lost for reasons which I won't get into some money will get burned so you don't definitely don't want to do it too early and we lose efficiency and we lose lots of things so you don't want to do it too early and on the other hand you don't want to do it too late so what are the ways to get around this issue what we propose is to use an idea which was first proposed by Justin Drake called uh

cryptographic canaries these are challenges that are put on the blockchain with a bounty right so imagine you could put a bounty for breaking ecdss or shat 56 or whatever and maybe even with a easier hardness right and for example for our purposes we want to have something which is you know say you could break it with a quantum computer say six months before the one which could break the fullblown scheme ah it's like a slightly easier exactly so you want to publish this uh challenges on the blockchain which are slightly easier and change the policy according to the that for example after this Quantum Canary dies say 3 months later

everyone has to switch to use post Quantum cryptography right and you cannot use the old one because the adversary could use that right so that's where the quantum canaries are used is there a an incentive issue here cuz say I'm trying to build a quantum computer I realize that I beat the canary I don't tell anyone and I know like okay I'm about like 6 months away from doing something big here yeah so actually we have a game theoretic analysis as long there is a competition and you're afraid that maybe ah in you know and I'm six months ahead but you know if someone comes in in in one month and take the Bounty before me then I'm screwed right

so now there's a game theoretic question and and you kind of need to analyze it and of course I'm not so sure how good this is right I it might be a good idea if there's a single entity not so good yeah so it really Builds on the competition between different Quantum Computing manufacturers huh it's a little bit like it's good that it's there but it's somewhat optimistic right like it's sort of assuming that there will be like a fair balanced competition that they kind of know about each other and if people will be willing to agree that to switch to that way before or find another way to kind of figure out when this happens

I'll be perfectly happy so far we've been talking mostly about like using existing cryptography in a postquantum computer world and like all these techniques are just to add something postquantum that we already know will work but are you ever looking at actually making adjustments or these sort of like conversions to Quantum cryptography so this is kind of very interesting because it takes a even historic perspective persective so so historically there were two main routes to construct money right mostly old money used physical objects that are hard to copy such as commodity money cash Etc modern money or the other

approach uses some kind of a ledger that records all the transactions such as bank accounts credit cards cryptocurrencies Etc they all of them use this second approach now interesting ly one of the pecularities of quantum mechanics is uh something called the no cloning theorem oh yeah it says that if you if I give you a Quantum State and you don't know what that state is or how I prepared it there is no way for you to create another copy of it I think in the last episode you started with that example of this um yeah that you could use it for like running a program that one could share if there's a connection between those two entities but someone outside

of it would not be able to actually access this program yes yes yes and why is it relevant for us again more broadly cryptographers are interested in things which are impossible or hard right why because well that gives you a handle on something that the adversary cannot do so this is just another example of that instantiation right no cloning there's a knowing it good for cryptographers right so Quantum money was first in Ed by Steven Winer in 1969 uh you have to understand this is before classical modern cryptography right so this goes way back and he proposed to use this idea of the no

cloning theorem and this was actually the first paper that thought about quantum mechanics in the context of quantum information so in some sense you could make the argument that he's the the father of quantum information in a broader sense right that uses cubits to do computation or manipulate information in arbitrary ways and he invented the first Quantum money scheme which is somewhat similar to credit card in what sense unlike the cash we use today in winer's money you needed to go to the bank to verify your money so you have to communicate with the bank in order to spend it but unlike a credit card the money itself is not associated with any particular entity okay okay who's the

third party in that though what's the third party like who's the bank kind of I don't know the Central Bank the private bank or it would actually be an entity still like you be it's interactive in a way think of it as like most of the money that people use today that there is a trusted third party yeah okay just like that it was 1969 they didn't have any other ideas okay exactly exactly okay what are the advantages of uh winer's money the two most important advantages over cash is the fact that you could digitally move it from you know one place on Earth to the other if you have

a Quantum Communication channel unlike cash we use today and the second one is about the security guarantees you know what stops you from forging the money that we have in our pockets right there's no really formal guarantees about it if you a good enough machine and people that are willing to take the risk most likely they'll be able to do it right it's security by obscurity uh there are no formal guarantees about it whereas in his Quantum money scheme he had a security proof or maybe okay actually uh let me be more precise in 2009 there was appeared the first I would say full security proof of Winer

scheme uh so even though he didn't have the terminology and even the language right because look it was 1969 the notion of a cubit was not invented the notion of the no cloning theorem was not invented he he was essentially Walking on Air his arguments were uh really shaky and it's kind of interesting example because it took 15 years for the paper to get published and it was circulated between some of the more Ecentric people or computer scientists around it was barely known by The Wider Community but still he managed to um talk with others about it such as Charlie Bennett and brassard and and

other that are kind of invented many important cryptographic Primitives based on his ideas and are actually now way more important in some sense because these were practical invention unlike his uh I guess one more point about Quantum money is that this is almost science fiction as I mentioned we don't have quantum computers and in order to have like a functioning money system not only you need to have a good quantum computer you need to keep it right for a long period of time so current quantum computers run for something between a microsc and a millisecond okay this is the time in

which the cuits wouldn't be destroyed in some sense by noise M now if I told you that here take your money for the next millisecond you would be kind of frustrated right uh one of the functions of money is store of value right which means you want to store it for you know the next year or your children right so for that purpose it's horrible and it's unclear when this will take place I didn't actually realize this that you just said that the quantum computer the issue is it's just totally unstable it sounds it w and when you say last long like you're saying you need the computer to last like a couple months or a year or something right like so that it could

actually do something more than the millisecond worth of computation or whatever it's doing exactly we expect a sh's algorithm to take something like a second or or a few seconds so for that you need the noise level to be reduced but okay only by a few orders of magnitude and use some fancy error correcting codes etc for something like qu to money you need a completely different approach I guess the upside is that you don't need all the fancy computation involved so I'm not sure when exactly it's going to happen but I don't expect that to take you know a few years another aspect is that unlike the risks that we talked about you know for these risks you need a single quantum

computer to have a useful Quantum money uh system you need that to be you know uh cheap and and you know ideally decentralized maybe that's even too crazy to wish for you want users to have that right you want the user cell phone to have Quantum capabilities this is decades away that would be my guess I of course I'm not a physicist this is outside my area of expertise but I suspect this will take time that's my personal guess another practical question you mentioned um Quantum communication channels sure cuz I'm guessing we have to exchange cubit how does that happen what does that look like can we do that what kind of wires do we use right so they basically look

like the channels we use today they use five bar Optics but they are way noisier right you need you need completely different approach to handle noise unlike the fiber optics we use today where the signal is repeated many times here a single Photon encodes a cubit right so things need to be done quite differently and the rates are lower etc etc and especially dealing with hops you know between different uh nodes in the network that's a really big challenge but we definitely know how to do that for for short ranges like a few kilometers Etc there is already you know can we reuse the existing fiber optics

infrastructure I don't know enough to tell you I think that the answer is yes but I'm I'm not 100% sure and definitely again there's a huge loss in efficiency so uh that has to be taken into account I want to keep going on the quantum money topic so I feel like you've given a really good history of it and that this idea was brought up but like that is still like very much the central model and it was based on like you said walking on air like it was sort of making assumptions that I guess turned out to be true but has there been any other work on that has there been progress on Quantum money definitely definitely so I guess from from around 2010 there were huge developments the main one was the idea of public Quantum

money so public Quantum money is we still have Central Bank but the bank publishes the bank's publicy and there's an algorithm that uses the bank's public key to verify money okay so this is now way more similar to the cache we use today where you know when Nico and I make a transaction it's actually between niik and I the bank is not involved at all okay um so that was the idea that that came up in 2010 roughly the constructions unfortunately to this day are I would say not based on standard

assumptions we still don't have provably secure Quantum money scheme which is public under standard assumptions I can get into the details or what's the state-ofthe-art but I I would say that there are still lots to hope for is there any sort of decentralized model even being proposed or is it so far off and too complicated no it's actually it has been proposed there are several variants uh one of them is called Quantum lightning and the other is called on-shot signatures I think it's easier to explain the second one even though it's even fancier um in one shot signatures we use something which is

called a common reference string or a common random string which is often used in cryptography say in the common random string we need to have a string that was generated in a way which was honest right and no one kept any secrets and once we have this random string everyone agrees that this is the random string to be used and then we have an algorithm that people could use to generate a onot signature State okay the bad news about oneshot signatures is that we don't really have a candidate construction I mentioned the common reference string but another assumption that we need is that this is only true relative to an oracle now I don't want to get into what

exactly do that mean but we need to assume that there is a functionality that everyone has access to it's tailored made for that purpose it's not like the random Oracle model for those that know what that is and the scheme is secure only relative to that Oracle and we don't know how to construct it from any assumptions in the standard model right even standard assumptions or non-standard there aren't even candidates for that so I guess I want to emphasize that this is a science fiction now not only in terms of experimental setup but also from a theoretical setup we don't know how to instantiate it how does this Oracle differ from a trusted third

party one way to think about is a trusted third party but we prefer not to think about that because for example if you could obfuscate it maybe you could give it to everyone right so the fact that there is a something that it's only a functionality right it doesn't need to to keep a state or anything like that that's a nice Advantage because maybe for example in distinguishability ofation uh could allow you to turn it into something more practical but that's kind of more for the experts Etc this I guess the the the for delay men it basically mean that there are definitely bad news in terms of practicality of that scheme is this kind of like the zkp and The Trusted setup uh similarly yeah very Sim very similar to that but but

again the goal is very very different from that right even though the setup is the same once we have that random string we can use it to issue one shot signature States or oneshot tokens if you wish what do they provide given that state you could sign any message you want so you generate the state the state has a public key and you could use the state that you have along with the public key and generate a signature an adversary cannot generate two signatures that are verified with the same publicy kind of weird so again I could take that take the the random string generate a

Quantum State and the public use the quantum state to sign any message I want that's the thing that I can do what's the thing that I cannot do or any efficient adversary cannot do the adversary cannot prepare a public key and two signatures that fast verification why is that the signing algorithm destroys the state so you have one shot to create your signature right okay that sounds kind of weird how is that all related to uh the question that you ask right Anna mm yeah going back to this like sort of makes like the prequantum to Quantum right yeah or no I

would say look let me even propose a more uh I think interesting idea as a way to transform a system such as Bitcoin to use quantum money so the first thing we need is a random string what random string will we use something from the you know first Bitcoin headers right there's lots of Randomness in there use randomness structors that's uh that that question was studied we have good ways to Generate random strings from that now suppose we want to switch to Quantum money a user will attach a message to the blockchain the blockchain it will have something along this the the next format right I or who who has the secret

key associated with my Bitcoins want to transform my Bitcoin to Quantum money and here is my publicy here is the oneshot signature public key right the first thing I do is I'll create the onot signature State and the public key and post a message saying look the money isn't associated with my Bitcoin secret key instead it's associated with my one shot signatures public key right now when I want to send it to NCO I simply hand over the quantum state to nik nik could use the verification algorithm and he knows that it's valid that's one way another is even more interesting instead Nik will generate another state right and now when I want to spend it

I'll sign Nik right and now we have it's interesting right we have a chain yeah right that goes from my public to nik's public and Nik could go send his money to Anna etc etc etc and since we have this chain and we know that there was no split there were no double spend simply because you could not use your one shot signature state to sign two messages so it really looks like a chain and that's something we proposed with in work with Andrea coladangelo using the quantum lightning and and it can also be done with the onot signature State and get even more advantages uh mainly ones

related to Smart contracts you don't necessarily have to use I don't have to spend my coin to niiko only I can do various other things like multisig Etc just a quick question anyway what you've explain here of we have this chain of signature and we know that there's no Fork because of the properties of this one shot signature does this mean that we no longer need consensus exactly wow you no longer need consensus yeah I should have said that you could stop the blockchain right imagine that everyone transitions to Quantum money you don't need the blockchain anymore wow you just need to make sure that you do need to know what are the final public keys right because that's the issued money

but other than that you don't need the downside if you do that is that there are certain things that cannot be done right there are certain things that Quantum money does not allow but things like ethereum do such as um ethereum name service etc etc yeah and we don't have an alternative for that is it almost like the state of the quantum money is a little bit like Bitcoin like just the level of activity that you could do with it exactly okay exactly so I definitely recommend such a transition for a system such as a Bitcoin uh but not for a system such as ethereum okay although there are some examples of

functions which I don't know but I don't think possible to achieve which are which is done in Bitcoin I'll just give one example which is one out of three multisig this is something that you cannot do in um because the no cloning property doesn't hold for that in some sense you could do two out of three but there's no way to do one out of three so there are some functionality that you cannot do another interesting example is timestamping you know Bitcoin creates a block every few minutes and you could create interesting applications based on this fact and uh indeed uh open timestamps is is one such example which allows you to timestamp documents uh very easily and cheaply and these types

of things cannot be done without the blockchain what about things like like the way that ethereum works the fact that you can do smart contracts and stuff everything you've described sounds like a relatively you know one use case type money transferring system sure but yet has there been thinking around trying to recreate some sort of smart contract platform using Quantum computing so there have been little work on that question and we definitely don't know the boundary what are the thing that can and cannot be done right that's I guess the bad news the bad news is we don't know where the boundary is what things require consensus or on the other hand what are the things that can be

done only using unclone ability properties okay so I would say the following we do have lots of examples for thing that can be done based on no cloning or Quantum money uh Primitives alone this includes things like colored coins this is I think the most interesting example yeah colored coins can even be used for things like um stocks right you could a company could issue stocks uh using this uh onot signature State this would represent a share right the share could be you know uh traded just like cash and payment could be made to that stock by the

company similarly to the weights done with colored coins div uh there are voting rights that this uh state allows you to use because you can sign messages right so if there's a question that needs to be answered you could use your voting rights to sign the message that you prefer uh or the vote that you prefer and there are very various other things again multisig with things like two out of three there are kind of things like saving accounts permanent addresses there there's a kind of a long list of things that can be done but also a long list of things that cannot be done I guess think about all the nfts or other thing that are done in ethereum some of them cannot

be uh done you cannot play a game on such a system not yet not yeah not yet at least I don't think theoretically not yet even theoretically you wouldn't be able to do that and I I'll post the I guess I I'll send the link to the paper that uh suggests this uh line of uh research sounds good and we'll add that to the show notes so since we are on ZK podcast I have to ask can we do arguments of knowledge succinct arguments of knowledge zero knowledge arguments where the soundness guarantees are quantum secure yeah so I know very little about these questions but as far as I understand first of all the picnic scheme uses this approach this exact

approaches you mentioned right essentially you use the secret key and give a zero knowledge proof of some statement okay so it definitely uses that approach but unfortunately unlike the ZK uh proof techniques that we have today which are really have been optimized and are quite efficient Etc that's not the case here and as you've seen right the signature sizes are are 1 half megabytes and I'm not talking about aggregation or or any of the fancier question that are addressed in the ZK literature right so it's worth in every aspect you could think of in terms of practicality I should add though we we

do know of like plausibly postquantum ZK schemes like stuff that is fry based I think our listeners probably have heard those words um relies only on hash functions and so are assumed to be postquantum secure sure but are they as efficient as the other uh Alternatives they're getting there yeah yeah yeah so I don't know if they are getting there then maybe I'm I'm yeah I wasn't aware that they're getting there in a show I did about FH we talked about lattice-based zkps would those be postquantum yes absolutely unless there's something you know you could combine it with other things and then it would not but if that's the only type of

assumption then yeah usually you can uh you know lce based questions such such as a shortest Vector problem or other variants are hard even for quantum computers just to check though the type of underlying Concepts that are not postquantum secure is that like pairing or elliptic curve cryptography is that what is not secure postquantum yeah I guess the vast majority of uh elliptic curve cryptography is not Quantum secure the exception is uh something called isogenes oh yeah but I think that had a problem didn't it it's awfully complicated some of the proposal have been broken okay it's kind of uh

complicated but I I think it's still uh if you wish alive there's still there's still hope that that that it's not dead end H but it's definitely extremely complicated and I guess one of the reasons why it didn't work in the N uh challenge right the proposal which did use that were not chosen some of them were broken and and others were you know simply inefficient or not not secure enough compared to the Alternatives one more thing do you know if anyone is looking at using the unclone ability property for ZK and argument type stuff because I think the ones we did mention the ltis based stuff that I've seen the hash based stuff doesn't bring in this

new element of En clonability so there are definitely other related questions uh which we kind of mentioned before uh which is called unclonable cryptography and some of these Primitives do use ZK proofs for their security analysis right I wouldn't say that it's directly related to the questions related to snarks or anything like that as as a technique it constructs different things using ZK techniques you see what I'm saying I'm not aware of any unclone ability arguments being used uh simply for the sake of vanilla ZK proof so another

interesting crossover moment between ZK and Quantum cryptography you've mentioned the common reference string model and you've mentioned um proofs of Destruction in zkps like we have this thing of a trusted setup like someone comes up with a seed generates a big string and the proofs are only secure if this person deleted the Original Seed are these prove something we could use here so there is something which is called um proof of delici and proof of Destruction which uh appears in in various different um Concepts in Quantum cryptography I'll give you one such example it's called Quantum encryption with certified deletion so what does that mean so usually if I give you the

cipher text and then later give you the secret key you could decipher it and reveal the message right in some cases you want to make sure that I gave you the cipher and I I want to make sure that you gave it back to me right classically there's no way to know in the quantum setting there is instead of encrypting it using a classical message I could take my message and encrypt it using a Quantum Cipher and I give you a Quantum State then I'll ask you to give it back to me or do a test to check that you destroyed it this is called a proof of deletion I give you a challenge I'll tell you look please measure the state

in in this and that basis and you will tell me ah I did and the outcomes were this and that and now I know that you destroyed my message okay and even if it later on I'll give you the secret key the original message is gone you could not recover it even after I'll give you the secret key and this is the type of thing that you cannot achieve uh in the classical setting right if I give if I give you the classical Cipher there is no way me to be sure that you have destroyed it another interesting use case is the gdpr right where services are supposed to delete the information if the user chooses to sorry but how do we know that they deleted the

information there's no way for them to prove that they have deleted it right so this is another interesting use case where they could prove that yeah I'll do a check and make sure that they really have deleted we're almost at time but I just wanted to quickly check back on something that you had mentioned earlier and said you might be able to give a bit of context on later and I know this is a bit of a switch of topic but it would be the hybrid cryptography sure what is that actually so one of the with postquantum cryptography or actually any mix of cryptography is that sometimes we don't really know how secure it is okay so imagine that we switch to postquantum graphy and it turns out that it wasn't

secure maybe even classical computers could break it right unlike the hardness assumptions which are used in classical cryptography which have been tested for decades yeah these ones are kind of new so simply switching to it might be uh risky so how do we deal with that risk yeah so one approach is called hybrid cryptography in which you use both in a way that in order to break it you need to break both right so think of an encryption scheme imagine that you in order to encrypt a message now you use two schemes so think of it like an onion right in the first level you use the prequantum scheme and in the second layer you use the postquantum scheme now

in order to open it up you need to break both of them and this is nice because that allows you to kind of enjoy the benefits of both worlds on the other thing what you lose for example the length right each one doubles the length then now you you pay the factor of four instead of just two but for some cases this is really important definitely in the early stages where we won't really know for sure how secure things are you sort of mentioned though the security challenge like if you combine these cryptography could you ever create a new security vulnerability somehow or do you feel like it's always additive like Security Plus security yeah yeah you definitely need to be careful about

these things this is a great Point uh there are generic ways to do the things but you know you need to be careful and prove that things are secure Etc there are ways that aren't known to do that in a secure way but yeah as usual don't uh how's it called this uh rolling crypto sorry don't uh run your own cryptography don't crypto don't roll your own crypto exactly nice this reminds me a little bit of an earlier conversation where it was about like friy security f but when you comb the two can sometimes actually interrupt like create problems in that combination this idea sort of popped into my head or I want to say thank you so much for coming back on the

show and covering with us all of this great additional info I feel like I mean I'm really glad we did a second one this was an episode in its own right we talked about like completely different things so yeah thanks so much for sharing all this with us it was wonderful thank you so much thanks so much thanks Nico too pleasure this was fascinating from the beginning to the end cool all right I want to say thank you to the podcast team Henrik Rachel and Tanya and to our listeners thanks for [Music] listening