When Eliptic Curves Break: The Transition to Post-Quantum Signatures — Marija Mikic | BU

Hi everyone. As Miros already said, I'm Mario Mikic. I work as assistant professor at Faculty of Mathematics, but also I'm cryptography researcher and co-founder of Mathematical Academy. So, Mathematical Academy is a kind of organization where we are working with talents in the field of mathematics, physics and cryptography. And for example, last year our participants won 76 medals on the state competitions.

So, at Mathematical Academy we collect awards the way the blockchain collects transactions, but only with the last failed ones. So, a large part of my work is connected with young talented people, difficult mathematical ideas, and the question how to explain them clearly. But today, I want to discuss about different difficult questions. What happens when elliptic curve breaks? And how can we prepare before that happens?

So, Ethereum depends on elliptic curve cryptography not just in one place. There are layers. The first layer uh the first layer is accounts. Internally owned accounts use elliptic curve digital signature algorithm over secp256k1 elliptic curve to sign transactions. The second layer is consensus.

Validators use BLS signatures in order to sign attestation. And the third level is application and protocol level. And there are some of components there that are using elliptic curve cryptography. For example, KZG is using elliptic curve pairing. So, elliptic curves are protect not just the wallet.

And the most conversation about quantum attack begins with wallets. So, we have a user user sign transaction. And then user public key become available publicly. So, attacker who has, for example, significantly powerful quantum computer can use Shor's algorithm in order to solve elliptic curve discrete logarithm problem and recover private key of the user. And this is not on only for wallets and users.

Uh the same quantum treat can be applied on BLS keys of validator, KZG commitment scheme, or SNARKs. So, uh Shor algorithm is very democratic. He did not He He doesn't attack only users. He gives wallets, BLS uh signatures, uh KZG, and zero-knowledge proofs, SNARKs, the same bad day. But today, there is no cryptography relevant quantum computer.

Uh there is no machine that could break elliptic curve digital signature algorithm or BLS signature. But we can see here the period from 10 to 15 years, and this is not the prediction of the QDA. This is just the reasonable planning period ex- uh evaluated but by experts. So, we have Ethereum, and Ethereum is very large system. And Ethereum has hundreds of millions of user, thousands of validators, many different wallets.

So, migration of system of that size requires years. So, I think that the question when the quantum computers will arrive is important question. But, more important question is how well or quickly Ethereum uh can prepare before that happens. We still have time. This is probably the most common sentence in discussions about quantum risks.

We still have time. And probably this is true. But, we also know that standardization, implementation, auditing, wallet integration, user migration will require years. And quantum timeline is a is like crypto price predictions. Everyone has one, and no one wants to see it again 2 years later.

So, Ethereum has multiple uh post-quantum uh migrations, not just one. We already talked about that. We need to change accounts, consensus, data, zero-knowledge proof, and privacy. So, we need to change elliptic curve digital signature and BLS signatures with post-quantum alternatives. We need to change KZG commitments with hash post-quantum commitments or lattice-based commitments.

We need to change SNARKs with post-quantum SNARKs or STARKs. And privacy is very important. Why? Because the privacy changes timeline. Um for example, if you have ordinary signatures, uh the danger begins when attacker can recover user private key and made for forged transactions.

But for the privacy point of view, uh the danger comes earlier. Why? For example, if you are using stealth addresses protocol, uh then you are using that protocol in order to um in order to obtain privacy. You don't want that the recipient um uh that the recipient being linked with uh his uh transactions. But now, uh we can uh collect the data and record the data and decrypt later when quantum computers arrives.

So, from the privacy point of view, we need to think earlier. We need to think now. So, let's talk a little bit about stealth address protocol. How usually works stealth address protocol? So, we have recipient and the sender.

And first, recipient will published his meta address on some kind of register. And his meta address is usually his public viewing and spending key. And then, we have a sender. Sender will go to that registry and find the meta address of the recipient. He will use his own secrets and combine with this meta address in order to obtain shared secrets and calculate new one-time address of recipient.

After that, he can send the assets to this new one-time address. And from the pri- recipient perspective, he will go to some other registry. He will calculate his share key. He will calculate his new address, and he will calculate his spending key. So, he's the only person that can spend the assets.

This was the the idea behind stealth address protocol. So, uh we can think on this way. For example, Miros is attacker, and Miros don't need to break protocol today. So, today Miros will record everything, and then just wait to finish I my presentation. Uh he will wait until quantum computer arrives, and then Miros will use Shor's algorithm in order to solve discrete logarithm problem on elliptic curve, and see all the secrets, all the private keys of the user.

And after that, he can link these old transactions with recipient. So, when quantum computers arrives, everyone can see all your old transaction and connect you with your old transactions. So, we need to to make migration for privacy point of view earlier. So, in order to obtain this, my colleague Mihailo and I created one new protocol, um where we are we replaced elliptic curve Diffie-Hellman key exchange with module learning with terrorists technique. So, we obtain post quantum protocol.

And we also obtain larger signature and larger keys. Why? Because we wanted to use Kyber for encryption and calculation of the shared key. And we also use the lithium uh signing scheme uh for signing transactions. But today, I do not want to talk about the details of this protocol.

Uh if someone wants to see how we construct the protocol, how protocols works, implementation results, or for example, security analysis, then you can scan this QR code. This QR code is linked with our preprint of the paper because the paper is already published in scientific journal, but without open access. And here, also on that this slide, is one result that especially surprised us. We wanted to create post quantum protocol and obtain that scanning time from recipient's side is lower. So, post quantum stealth address protocol requires only 1/3 of spending time time of our earlier protocol, elliptic curve dual key stealth address protocol.

So, we obtain uh we obtain post quantum security, we obtain uh fast scanning, and this is great. Uh but but this is our first version on our paper. The good news, it works. But there are also bad news. It's far from ideal.

It is like this car. It moves. It reach destinations. But, look it. It's far from ideal.

So, this is what we want to achieve. We want to have the same privacy uh goals, but with less luggage. Same privacy, my uh much less luggage. So, we want to have better signature size. We want to have smaller keys.

We want to have uh post-quantum security, fast scanning, and so on. So, the first picture here was our research prototype. The second picture here is what we usually put in grant proposal. So, uh we obtain already post-quantum security, fast scanning, and so on. But, the main cost of our research paper uh is um bytes.

So, uh in our firstly elliptic curve pairing stealth address protocol, uh the meta address is 66 bytes only. But, now in our construction on post-quantum protocol, we have 5,216 bytes for stealth meta address. So, it is very long meta address, and we have very long signatures. And this is the problem. And we can see on this picture, elliptic curve cryptography packed light, post-quantum cryptography both attract.

So, that's truck here is really the truck that we need to carry. The chain needs to carry this luggage. So, when we are thinking what what signature post-quantum signature to use, we do not need to think only in the way to see how security proofs works. We need to ask what happens when these signatures start to use millions of users and validators on chain. And I think that maybe the most important part for Ethereum is signature agility.

Account abstraction enables to choose uh accounts, of course, to choose which how signature can be verified. And there is one Ethereum improvement proposal, I think 8141 41, uh that support is it on protocol level. So, we we can obtain this and after that, we can uh we can do some pre com- pre compiles in order to reduce costs or to have some L2 solutions. After that, uh we need to uh change the the keys. User can change the keys and move funds before the Q days arrives.

I think that 2029 year is the planning year for uh finishing all implementation post-quantum parts for Ethereum, but I think that this is just the plan, not the fixed deadline. Uh very important here is to have signature agility. Why? Because some users or some application will need different things. Uh so, we need to uh be able to give them to choose uh which signature scheme they will use.

And there is no universal best post-quantum scheme. Here uh we will talk just only two leading candidates. Uh these leading candidates are lattice-based candidates. And uh on the left side, there is Dilithium. We already uh mentioned Dilithium.

And Dilithium has uh 3,309 bytes signature size. But, also Dilithium um finished standardization by NIST. Uh and he has um very easy uh security implementation. On the other side, there is Falcon. And the Falcon has a smaller signature, 666 bytes only.

But, he did not finish yet standardization problem pro- standardization process. And he's very fast and has uh little little signature, but um the standardization pro- process is not over, and the security implementation is complex, more complex than Dilithium. But, with signature agility, Ethereum can use the both of them, and the user can choose which one they want to use. Just replace elliptic curve digital signature algorithm. This sounds simple, but this is just the visible part of the problem.

This is just the top of the iceberg. Behind the surface, there are users, there are accounts, there are accounts recovery, there are uh zero knowledge proofs, there are bridges, and so on. So, replacing elliptic curve digital signature algorithm is it is easy if we ignore Ethereum, its users, its validators, and everything that's made it Ethereum. So, the main message of my today talk is that Ethereum needs to think about migration and transition to post-quantum cryptography. And he needs to thinks about it seriously and to move forward.

Why? Because when the threat becomes real, that then the main problem will not be the math. The main problem will be time. Thank you.