Making existing protocols Post-Quantum Safe - Lukas

Transcript

[Music] All right, thank you for the introduction. So, hello everyone. I'm Lucas. I'm from Hopper, which uh is a privacy uh incentivized mixet and it's partly one of the reason why we do care about postquantum cryptography because Hopper is like essentially a new version of tour which with incentivization. So we have a large um off-chain part uh next to the onchain part which could also be made uh postquantum already. So that's why we're uh we're actually turning towards this direction already as well. Um so I guess uh everybody's

has already seen pictures like these. So the question is what will actually happen when these expensive looking chandeliers kind of start to make something really useful and that's where actually most of the cryptography we see in the blockchain world like elliptic curves um hash functions or zero knowledge proofs might become endangered and in a sense that uh the quantum computers whether they're real or not already they might endanger elliptic curves because the uh ECDLP can be essentially effectively broken by quantum computer of of certain size. Uh zero knowledge proved based

also on DLPS or bilinear DL uh DL ECDLP could be could be broken as well with those. So the question is um what happens next right? So there are what what actually becomes broken right when there is a quantum computer. So um we have obviously the problem with the most used curved probably uh sect P2K1 becomes broken. private keys can be recovered from any transaction and a funny consequence is that basically anyone with a quantum computer could eventually claim their Satoshi right um in fact all of the ECC not just this curve all the ECC is broken as well signatures can be forged and uh

long-term secrets uh can be can be therefore recovered um and as I said the pairing based cryptography which are based on which is based also on ECDLP elliptic curve discrete log block uh will be uh endangered as well. Um but you might say, okay, quantum computers are not real, right? Or maybe they're not yet real, right? So the migration nevertheless in the in the off-chain world is already happening. So for example, there's this uh very often cited oops very often cited go back. Oh, okay. Sorry. very often cited

um study by Cloudflare uh where they actually uh looked into how many people or how much traffic that goes through Cloudflare is already utilizing uh postquantum and there is like almost like a triple increase in 2025 compared to the year uh 2024. That's just traffic that goes through Cloudflare and traffic which originates from from humans. So it's not machine generated traffic and other notable protocols actually already employ postquantum like there's there is um a postquantum wire guard uh proposal SSH already employs a postquantum cipher suites so it's not just TLS and also various encrypted services utilize uh

email encrypted services already utilize postquantum cryptography and the I the idea behind that is Because if this these are not just data in transit but data at rest and these are especially vulnerable to something called harvest now decrypt later right so basically if there's an adversary which hopes that there will be a quantum computer in the future could gather data now and uh decrypt them later so that's why this this uh this migration is already taking place and there's been multiple standards already standardized uh by NIST for postquantum cryptography and The recommendation is to be fully postquantum uh latest by uh 2035. So in 10 years 10 years from now. Um so what

are the alternatives right we have right now. So as I said there is uh NIST has selected some standardized postquantum algorithms. So uh there's algorithms for signing and also something called key encapsulation which for some of you who who you know come from the background knowing knowing about RSA encryption or encryption using elliptic curves like algamal or ACS um the key key encapsulation is basically a rebrand of that right so uh it's asymmetric encryption meaning key encapsulation um and these that besides these if you say okay I don't kind of would like to trust what not what NIS proposes or doesn't fit my purpose. Um there are also some good uh great quality

finalists which are uh which have certain pros and cons compared to them and there's also an ongoing crown to for additional postquantum signature schemes. Right? So um if we uh then look at some other stuff uh in in blockchain that's uh would be most uh notably zero knowledge proof systems. Uh there are some good examples which are uh thought to be uh postquantum safe. Uh most notable examples would be zk stark or plunk where you replace kzg with something called fast solomon read iOP where you get something called plon stark which is already thought to be postquantum secure and some other example would be like something called pq snark.

Um basically uh some classical algorithms are also not subsessible not sus susceptible to quantum computers. So you you if you're using uh like hash functions of of uh which are long enough or symmetric encryption which the key where the keys are long enough they're you're kind of fine. Uh there are some examples of algorithms which have also information security meaning that they're basically unbreakable by anything or even some weird alien technology that comes in the from the distant future. And the example most widely used is a Shamir shar shamir secret sharing scheme. However, it's in its raw form, right? So when you use something like a verifiable Shamir

secret sharing scheme, that verification part is no longer postquantum uh secure, right? But in its raw form uh the secret sharing scheme is um OTPs one time pass obviously not very practical. So u most likely people won't be start using it because uh they want to be safe from postquantum. Um so uh what it looks like for the signatures right so if we look at this table uh for the green lines you see that there are the pre-quantum technology that means elliptic curves and integer factoring. You see that there's uh public key sizes and signature sizes you you're already familiar with uh and uh there is a comparison of how fast they

are uh compared to uh compared to the new postquantum standard and what's the what's the what's the size of signature. So you see a drastic increase of uh public key size signature size which obviously brings uh an engineering um challenge depending on your use case and signing uh used to be in pre-quantum world also quite faster. I picked some other uh interesting algorithms basically best in their own category. So, uh, depending on what you're optimizing for, you might opt in for something different than what NIST actually tells you to be a standard because these are also good quality, possibly not yet broken uh,

candidates. Uh, because, as I said, this was just a a selection. Uh, there's many more. There's a whole zoo of postquantum signatures. Uh, you see the dark dots, which are signature algorithms. the stars are um the standard algorithms or the standardized one and you see the signature size on the left side and public key on the right side. So, for example, if your project wants to have super uh small signatures because you're transmitting data a lot uh and you want a trade-off in a public key size, you uh have have a higher public key size, you might be looking somewhere in this area, right? So, uh the pre-quantum algorithms, this is ECC actually. So, very small keys, very

small public key size. You see, not many of them are actually getting closed uh close in this um in this space. So the practical problems as I mentioned uh sign and speed ver sign and verification speed is improving for sure signature sizes poses bigger problem uh because obviously for example if you decided okay I want to use uh only postquantum signing in ethereum uh and then you would like to for example aggregate these signatures as it already happens in in uh in ethereum in uh in proof of stake uh then you have to transmit quite a lot of data right so there are solutions um and uh which which actually trying to tackle this uh

aggregation. So for aggregation naturally you wouldn't choose the hashbased like SHLDSA but you would use likely something with algebraic structure. There's also some interesting recent development in aggregation via snarks. So you basically um you basically do not aggregate the signature itself but you aggregate a proof of that given that if the proof actually itself could be postquantum safe then you might be you might be good as well. Uh let's take a look at the other type of algorithms which is the key encapsulation algorithms. This is a table uh a similar one. So we have the pre-quantum stuff and here I picked just two uh NIST finalist. So there's a situation slightly different from the

engineering perspective. You again deal with an increased public key size and private key size as well. But these algorithms tend to be much much better than the pre-quantum algorithms for encryption. Right? So uh in terms of speed, the these are awesome in terms of expansion of the public key size and cipher cipher text size. uh there might pose some problems again when you transmit a lot of data encryption uh and and then uh you end up with a lot of packets being actually transmitted uh that might hit performance quite badly.

Um so again the practical problem here is uh that chems directly replace the ephemeral defing agreement. uh that's not a practical problem. That's that's uh that's basically way how they're used to be the way they're used. Um what the problem is here that there's a notable cipher text expansion as I mentioned and uh the public key. So exactly so if you're if you're uh exchanging the ephemeral keys very often you have to deal with an increased amount of of data being transferred. Um, in addition, if you built more complex protocols out of or used to build more complex protocols

out of elliptic curse, for example, you probably use the uh additive or multiplicative group structure. Um, so this is not there. Obviously it could be partially mitigated uh from the engineering point of view by using something called chem combiners which is an original uh an original scheme uh a scheme developed for creating hybrid schemes. I'll be talking about that in the next slide. Um and in in this way you could mitigate for missing algebraic structure. So you could basically put on put in different public keys together and then basically derive one shared secret in a similar way like you would used to do in in in

uh two uh one two out of two secret sharing scheme for example using diffy helman um there's another interesting thing actually and it's called multi- message multi-reient uh which is particularly useful for schemes where you have like multiart key agreements and uh when you Compare this to a naive approach where you'll be sending sending like basically public key postquantum public key to all the parties like this uh compared to this one 80% of the size would be reduced. So you could spare really uh precious bandwidth when when doing these kind of multi-party key exchanges. Um but again there are some missing properties and and uh or

non-existing properties in the postquantum world which we were used to use when building a protocol. Um okay so what is the prognosis right exactly so I I was I was thinking okay should I use quantum uh postquantum algorithms should I use pre-quantum algorithms or what should I do so maybe the answer is hidden between like you know if you look back at the at the competition that NIST made and you look at all the algorithms which were submitted as as uh submissions to this competition and you immediately see how many of them actually became broken and some of them broken so badly that people

thought okay is like this postquantum security even a thing is it even possible the most notable example is psych which was thought to be like the one which had the most the smallest key sizes right but it was broken basically over a weekend and nobody expected that it was almost like in in one of the latest finalist lots of these algorithms were actually weakened Right. So these algorithms uh have much less security than they uh they they were it was thought they would have. Um that means um things still change even after the standards were being uh standardized things could still get

broken and that's why the industry actually tries to counter that. Um and by broken I mean broken with a classical computer right so it's a a thing thought to be postquantum secure but it's broken by a classical computer a non-quantum attack so that's why uh as I mentioned TLS SSH these commonly used protocols are deploying something called hybrid schemes which uh basically means for example for signing you submit two signatures one with a postquantum algorithm the other one with a pre-quantum algorithm and that thing is actually valid if both of the signatures are are valid uh at the same time. The same thing would apply for chem. So use

secrets from both classical um uh classicalally derived key encapsul key encapsulation algorithm like x255119 or uh and use it together with the material you decrypt from the chem uh post which is postquantum secure. So but obviously um this uh has another worsening effect towards bandwidth. You know, you don't have to transmit just the large keys, postquantum keys or postquantum cipher text or postquantum signatures, but you also have to transmit the classical ones, right? So, but it has the added benefit that you're not betting just on a single card, right? So, at this point, you're saying,

okay, if a postquantum algorithm gets broken, then I still have this classical one, which is a time- tested one, uh, in in the mix, right? So that's where the chem combiners actually came into place and uh in this key exchange for for example uh they're used to combine a classical and postquantum chem um to make think uh secure in a hybrid way. The question is do we have hybrid solutions for zero knowledge proofs? uh I haven't seen many actually but uh the thing is like we shouldn't bet on think to not to become broken because we think it's postquantum secure the

question is whether we should actually have a similar hybrid approach also for for zero knowledge proofs so uh yeah that's about it that's uh here are some references I'd use and yeah any questions thank Thank you. Does it work? No.

Does it? Yeah. Yeah. Thank you. Thank you for the talk. Was really inspiring for me. Um I have two questions. One of them is um how quantum computers are going to affect the consensus. I mean find the hashes and find the blocks create the blocks. Second about the the final slide you said about this hybrid solution. So did you mean that we are going to we should use classical and postquantum signatures together? Well it's it's so okay. So in that case you know if we already rely on classical I mean then we shouldn't be little bit weaker than the current one.

Okay so to your first question first. So in in consensus you're basically transmitting signatures right which are getting aggregated by uh basically finding the you know random to create the hash. you you would assume that you're able to basically break uh the keys which are which you make signatures uh with right so you would able to recover public keys uh private keys from the public keys and then basically uh in a consensus you could like transmit uh attestations which are not signed by the actual by the actual validator right so that might uh that might kind of there are not yet attacks being developed which would assume quantum computers but

the assumption The assumption is when these nefarious things are possible and uh these are kind of not the assumption of the security model or a threat model then uh you know nobody knows what is going to happen but probably nasty thing is going to happen. And to your second question regarding the hybrid schemes, um yeah, well basically if you look at TLS, if you look at SS SSH, if you even look at a postquantum wire guard, uh they use these hybrid schemes just to be sure because you know the um the the postquantum algorithms being based on problems which are fairly old and tested, there are fair still fairly new.

That's one thing. And second thing which is also kind of considered uh not very in favor of trust is that fact that they have fairly comp complicated algebraic structure. So for example like it's it's it's for the researchers and cryptographers it's uh fairly easier to believe in something which is a fairly uh simple algebraic structure and uh it's therefore easy to understand and prove something about it. If you look at for example lettuce schemes which are module lettuce algorithms they're fairly complex they have fairly complex algebraic structure and nobody really knows until time tells if this could lead to some additional attacks. So that's the reason why uh people to be like more conservative they people who want to be more conservative to employ

these hybrid schemes to actually be sure okay we have this time- tested ECC algorithm which has been there for like past 20 years and nobody has broken it so far and assuming there's not a quantum computer coming soon I could combine that with uh a postquantum stuff to be to have like not to bet on a single card pretty much right so the question is whether Should whether should this also happen for zero knowledge proof systems right okay thank you so you are saying that if there is an attack to postquantum and we are still asking for the classical so we are pretty much exactly we have we bet on two cards right so thanks for the for the consens what I meant actually for example we know that the first blocks in

on in bitcoin were already mined by satoshi maybe I don't remember the exact number but maybe 500,000 or even could be 1 million bitcoin it's still there. So um if Satoshi Satoshi is by by the way public keys are not known because it's already hashed there but as long as it's going to move then the the it's it's going to so um I believe either I mean he has to or they have to remove their if there was a public key for Satoshi somewhere out there all hashes then then it would be then somebody could take the public key use a quantum computer break it. Right?

That was just a funny uh consequence that could might be if there was a public key, but it could happen to any transactions being made because from a transaction obviously you can recover the public key that signed the transaction and you can break it if you have a quantum computer. Luckily, we still seem to the latest research by made by Google where like um still about three orders of magnitude in terms of how many cubits uh uh cubits are needed to actually break an RSA for example, right? But it's thought that uh the uh ECDLP algorithms so uh elliptic curves are going to be broken sooner because obviously the amount of cubits you need to break that is is is lower right.

Uh hello so you answered my first question about how many cubits will be enough for attacking the RSA systems or any kind of blockchain activities. But for my instance uh my university recently had 5 cubit uh quantum computer in itself and I don't think that that's will be enough for attacking the blockchain systems or RSAs but will it be enough for uh using the perfect algorithm for quantum computers like it will be enough for attacking the blockchain system with only five cubits if you use a perfect world scenario or is it really required to have so much cubits inside just the attack? Yeah, I would I would uh it's not in the references, but I would uh uh direct you to a nice study by made by Google which

studies exactly this, right? So, uh it's quite recent. I think it was in the past couple days. it went out and they basically say okay so if you want to break uh something like RSA 248 uh 2048 which is in security equivalent to uh uh the elliptic curves used by Ethereum you need something uh which has at least uh 1 million cubits which are not error corrected. So there's still distinction you talking about cubits but there's a distinction you you have to talk about whether the cubit is error corrected or uh general uh error uh cubit which can have errors. So and uh obviously is harder to get those uh those cubits which are which are uh non-er which are

error corrected right but they're assuming that for uh to breaking the RSA you would have to have like a million of error corrected cubits whereas the best quantum computers now have around 100 to a thousand so as I said about three orders of magnitude uh uh somewhere else yeah so does it answer your question yes Okay. All right. But if you use like a real world scenario like real uh kind of thing that the five cubits are really perfectly aligned and there is no errors. So could we assume that if even with the five cubits or 10 cubits right not I'm not talking about right now but maybe in the future with perfect

algorithms can they be resolving the problem that we talked? I think with five cubits you can't break things like uh EC I mean it's depends on the definition of your cubit right but uh I mean if if we mean the same ones I don't think that is possible to to break uh the current crypto with that that few cubits okay thank you so much oh cool uh thank you so much the for all the answers for the talk uh for so round of applause for Lucash [Applause] [Music]