You can't withdraw your privacy: PQ analysis of Kohaku privacy protocols

Transcript

Hello everyone, thanks for coming. So yeah, I'm going to do um a small presentation on uh the postconum analysis of the privacy of Kohaku. So before I start, let me present our team. So we are three engineers working in security. Um the first one is Nicolola Bakam. Probably you know him. He's um hardware specialist. So he's working on the security of hardware. Um previously co-founder of Ledger and now working with Renault and I. So Renault and I are working in cryptography and uh we are mostly developing like efficient uh gas efficient um verification contract in solidity and also hardware

implementation like postquantum signature in hardware and for privacy protocols. So we designed um elliptic curve cryptography for hardware wallet for privacy protocols. If you want to look our to our website we have several demonstration if you're interested. Um yeah, I wanted to start with um a quote from Coinbase report where they're saying that ZK proof is basically by construction safe against a quantum computer because the output is of fixed size while the input can be of unlimited size which is true. So it means that

grow 16 is like perfectly zero knowledge. But when you have um um privacy protocol, you usually have extra data that are put on chain like commitment, cipher text, nifiers. And actually the privacy break that you can have with a quantum computer comes from uh these uh extra data that are on chain. So here I'm going to try to dive into the quantum attacks that you can do on this uh data. So what what a quantum computer can actually do if we want to simplify a lot it's affecting mostly only the public key cryptography. So actually some part of the public key cryptography for

example factorizing numbers like in RSA if you know it and uh also for computing discrete logs on specific groups like elliptic curve or finite fields and mostly the symmetric cryptography is kind of safe which is a good news but in Ethereum we have lots of part of Ethereum that are actually using public key cryptography. So what happens um at the execution layer we when you sign a transaction you're actually signing with ECDSA. So mostly the execution layer is broken.

The consensus layer is using uh pairing based cryptography. So it's also broken because it's a discrete log on a finite field. And for the privacy it's still a bit unclear. So I'm trying to clarify this part on the privacy side. So if there is one thing to reme to remember from my presentation is this slide where there is a distinction between authentication so when you sign transaction and the privacy so two different deadlines in terms of quantum attacks why because the authentication you need to have a quantum migration after before the the day we have a quantum computer but on the privacy side all the bites that you are putting on

chain now can be stored and decrypt it later once we have a quantum computer. So there is like kind of two different deadlines that are really important. So to remember authentication you need to migrate before we have a quantum computer and privacy all what is encrypted today needs to be quantum secure now if you don't want to be to have a privacy break uh after we have a quantum computer. So I'm trying to look at quantum attacks on three privacy protocols that are pushed by Kohaku. Uh Kohaku is an SDK that um is pushing privacy protocols

and there are three main protocols now. Tornado cache, privacy pool and rail gun. And they share some properties but are also very different. And now I'm going to try to explain how you can attack this protocol in the on the privacy side using um a quantum computer. So first to start I'm I'm going to explain how tonado cache that works and this was the first protocol that was uh integrated into Ethereum and it's not so complicated. So when you want to shield some tokens, you're actually uh adding a commitment into a Merkel tree. So you send some fonts from your public account

to a specific contract and this contract is updating a Merkel tree with a commitment. And when you want to unshield the found from this contract to a new address, you compute a nullifier which will be some byes that will um ensure that you you won't be able to unshield twice and you will also prove using a zk proof that the commitment so that the nifier is actually linked to a commitment that you own.

So if we look at the details uh commitment and nullifier are computed using a pedison hash. It's um a hash function that is based on elliptic curve. So you take your bytes you convert it into numbers in a specific way and then you compute a multiscala modification and this hash function is a bit specific. So if you in the case of commitment and nifier of tornado cache if you substract the commitment to a nifier you'll have a function that doesn't depend on on the nifier key and then if you have a quantum computer you can actually use sh algorithm plus small latis so you can actually break the

privacy and get a link between a commitment and a nifier. This doesn't really work uh 100% chance. So you still have 15% chance that the pre- image of the hash that you find is actually wrong. And so that's why it's not properly breaking the privacy but more shrinking the anonymity set. But once you go into a private um a practical case, you actually break the privacy. Why? Because so you will run your quantum algorithm on a commitment and the nullifier.

You'll get a link between the commitment and the nullifier. But still you have 15% chance of failing. But once you have this, you can also look at the address of the shielder and the address of the unshield. And then you can check other commitments, other nifier. And then you can run again the quantum algorithm to find a second link. And then the probability of failing is decreasing. And as long as you have several commitment and nullifier, this probability is going to zero and then you're pretty sure that uh you have a link between the two addresses.

So conclusion for a tornado cache is that the elliptic curve is breaking the the privacy and when you use metadata you you can be sure that you have a link between two addresses. Uh the second protocol is privacy pool which is working in the same idea as tornado cache. Of course there are differences that I won't dig here but the idea is the same that you update a merkel tree but this time they change the hash function. They use poson hash which is not based on elliptic curve scalification.

So commitment and nullifier are using this hash function and at the protocol level this uh first version of um of privacy pool is quantum safe because of this new hash function. One issue with this first version is that it's a bit limited in terms of functionalities and privacy pool decided to migrate to a new version v2 which is a UTXO model. So basically all what you can do in the transparent model you can do it in the private model and when you do when Alice want to do a transaction to Bob she's basically computing a newifier for her note and adding a new note in the Merkel tree but

now she needs to send the private information to spend the note to Bob. So how you do that? You encrypt the note information and you send it to Bob or you put it on chain in in the case of blockchain. So how you encrypt the data you use ECDH which is a standard key exchange and you send you encrypt then using ECDH and as here is where it's again broken by a quantum computer because this ECDH is based on elliptic curve and again a quantum computer could just decrypt all the cipher text and get all the links between the transaction.

The good news is that now uh to fix this issue, you just need to uh change the encryption scheme. So instead of using a ECD, you can change to something else and then it's going to be quantum safe. And this encryption side is not part of the contract. So you can even keep your pool, keep your contract and uh use another encryption and it will work um the same. Now I'm switching to the wallet level just for a few minutes uh just to explain some specificities of tornado cache and privacy pool in terms of hardware integration. So I mentioned

that you need to compute a zk proof that links a commitment to a nifier and this zk proof is actually quite big. It's like 300 kilobytes. It looks not so big but for hardware it's quite big because we have like a few um a few kilobytes uh available in the RAM. So we won't be able to compute this ZK proof on the hardware wallet. So usually when we we we are stuck like this we delegate this computation to a host to a software wallet and we ask for the software wallet to compute the zika proof.

But this doesn't really work because the hardware wallet is here to keep the spending key on the hardware wallet. But in order to compute the ZK proof on the software, we need this spending key. So it's we we are kind of stuck with this proof computation on the host. And so that's why you can't really use tornado cache or privacy pool using a hardware wallet. And uh it's one feature that is a bit um annoying. You still have some hardware friendliness in the sense that you can derive the spending key on the hardware and then you export the the signing key to the host. But this is not hardware

security because the key is like leaving the device and going to the to the host. And so now I I want to also mention that how you derive your spending key will also affect the quantum security. So when you want to derive your spending key, you have several options and fat solution was actually implementing and specifying a solution for Kohaku first where you use you start from the seat phrase and you use hash functions to get the spending key the nifying key which is actually standard and uh it's so it's postontum by default

because it's using only hash functions and if you want to do this uh export importation of the spending key from a hardware. You just need to design a simple um hardware app and you'll be able to export the keys. But then Kohaku decided to move to another way of uh deriving keys where you sign an an Ethern message sorry and then from this signature you derive the spending and unifying key. So for the hardware friendliness, it's quite nice because you don't need to have any new app. You can just use the Ethereum app.

But in terms of quantum privacy, it's um an issue because uh Ethereum signature is ECDSA. So it's again broken by a quantum computer. So if you want to have at the wallet level the private the quantum privacy you rather use the fat solution derivation that is using only hash functions. So this is at the wallet level and now I'm going back to the protocol level with the third protocol which is a rail gun. So it's uh also a UTXO model. So again all what you can do on the transparent model you can do it on the private model which is a nice property but as for privacy pool they are

encrypting the note so Alice is encrypting the node to Bob using something very similar to what I mentioned before and so if you have a quantum computer you can break ECDH and decrypt everything in terms of hardware integration it's uh diff a different story because the contract is a bit different and instead of computing the proof from the spending key you compute the proof from a signature. So what you can actually do in rail gun is that you compute the signature of the transaction on the hardware wallet using the spending key. The spending key is staying on the device and then you export the signature and the host is

computing the zk proof only from the signature of the transaction. So this mean that you really have um hardware security and you can use a hardware wallet and um for rail gun we did a proof of concept of how you could change the encryption to get something quantum safe. So we started from the implementation and we changed the ECDH key exchange to have hybrid encryption. It means that we have still ECDH security but we also add MLM which is the standard for postquantum encryption by the NIST.

Uh we use the key derivation as a fat solution specified. So we use hash function for this. We could also implement the hardware integration for now it's blind signing but we also have clear signing integrated into it. You can have a look at the website. It's a of course it's a proof of concept but it's just a a way to show that it actually works. Uh what is nice is is that it's working with the production contract. So you can actually use the the the contract of rail gun in mainet and do your transaction using this uh hybrid encryption. And if you want to adapt this to privacy pool it's pro probably possible just to show you how it looks. Um so in

rail gun you have your uh transparent address your 0x address. You have your zero zk address on the left which is two line long and your postquantum private address is a bit longer because you have this mlm key that is quite huge. It's like 1,00 bytes and on the right it's um it's just it scan logs. So you can see the cipher that you send to Bob and you see that one of the cipher is huge because it's the cipher for for MLKM again but this is not very expensive in terms of gas because at the end the gas that you pay

is also the proverification which is quite expensive. So changing to postquantum cipher is not really expensive at the end. And just to conclude, so for tornado cache the issue is from the hash function that is based on elliptic curve. So if you have a quantum computer, you bind it to the metadata and you can break the privacy for privacy pool. The first version was safe at the protocol level. The second version that is a bit more generic is broken because it's using encryption using CDH. But it's possible to fix it by changing the the encryption. And of course, you need to at the wallet level,

you need to use the the derivation path using the pneummonic phrase. And for rail gun, it's also broken because of the encryption. And we provided a proof of concept of um of the the fix using MLAM hybrid encryption. Again, we also use uh the diversion path for the for the seat phrase. And for the next step, so for now it's already possible to fix a privacy protocol to have quantum privacy um on the current protocol. What is more way harder is to have like fully postquantum protocol where also the authentication. So the signature, the

consensus, the star, the proof are also quantum safe. And yeah, that's all for me. So if you have any question, >> thank you Simone. Thank you. We already got a couple of questions on Mircat. So thank you already for asking and feel free to add more if you have. The first one here is is a tornado quantum attack seven uh seven times reduction or would a global attack combinatorally reduce it further?

Um yeah probably can be reduced further but uh that's the estimation that we had from actually I have a slide of the detail of this uh attack that I could also show uh but yeah this shrinking of bioactor 7 is what we had for now and maybe it can be reduced here. >> All right so if you ask this question and want to see the slide feel free to approach Simone afterwards. Um the next one we have here is does this mean that all the work done on Ethereum now is useless and redundant as we will need to migrate to quantum safe algorith algorithms why are we wasting time progressing it >> um no I don't think it's useless I mean

the the on the authentication side uh as I said we need to migrate before the quantum um computer is efficient and on the privacy side yeah it's kind of more urgent but uh as it's quite easy to migrate to something postquantum. So yeah. >> Okay. >> You you're you're not as worried as the person asking this question. Um which cryptographic components of Kohaku are most vulnerable to quantum attacks. >> So for tornado cache it's the hash function itself and for privacy pool and uh and rail gun it's the encryption side. Yeah. Got it. Is it expensive?

Does MLKM increase size of messages? >> Uh so yeah, I was showing this in the proof of concept that we had. It's not something that you will uh write into the contract. So it's not so expensive in terms of gas. So it's basically some logs that you put in the transaction so that the recipient can fetch the data and get his note. So yeah, it's not so expensive in terms of gas. Okay, it's good to hear. How actively is rail gun collaborating on emerging Ethereum standards like EIP8182 to ensure your postquantum privacy layers remain composable with future institutional D5 front ends.

>> Uh I think it's a tough question. I'm not able to answer to this one. >> Fair enough. Yeah, if anybody here has a has an answer to this one. >> It's too technical for me, I think. >> Yeah, fair enough. Um what does it mean for signature to be se separate? What additional function does it provide? >> Yeah, so I was mentioning that in rail gun there is um a way to compute the zk proof without knowing the spending key and that's uh the clean separation that there is in rail gun that you can compute the signature and then export it and compute the proof from the signature. So it's a very nice feature because it's allow you to use hardware

wallet but also you can use multisig. So again something that you do in the transparent model when you use your safe for example and you can do this in the in the private model too. So yeah I would say multisig is another feature and maybe um forgetting other features but yeah already something. >> Okay I see the questions keep coming. We have a little bit more time for questions. So with the development of quantum hardware, will Ethereum need any changes at the EVM level or can quantum resistant security be implemented entirely through new cryptographic algorithms?

>> Let me read again. >> Yeah, it's a bit of a mouthful. So I guess the B question is with new quantum hardware, do we need to make changes at the EVM level? Um yeah I I to be honest I I can't answer to this one. >> That's fair. Okay we take another one here. Can quantum resistance zero knowledge proofs prevent future dean anonymization. >> So yes I I think it's more on the authentication side. So the stark so the the hash function based proofs will enable having like security on the on

the authentication side >> but it's also related to the to the privacy because it's it's a zk proof so it's also hiding this um this link but yeah I would say it's more on the authentication side than the privacy side but we we need it for a fully postontum protocol. Yeah >> I see. Okay, we're running out of time. I see this little couple of questions. If your question wasn't answered, please feel free to approach Simon um right after this. So, give uh one more round.