I have seen a lot of comments from people who are aware that quantum computers pose an impending threat to most cryptos but they are confused or fuzzy about the details. This is to be expected, it is a complicated topic, to say the least. I wanted to make a post to explain what the problem is, what solutions are on the horizon and some common misconceptions about quantum computers. This should be approachable for anyone who knows the basics of how a blockchain works, so don't feel intimidated by the quantum aspect.

Me: I am a professor whose research is in applied cryptography. I am also currently in the process of prepping a class on quantum computing that I will teach next semester, so I am pretty well situated to know the issues. I don't own any cryptos and don't care at all about tokenomics, price action, etc. This post will be purely about the technical aspects of blockchains/cryptocurrencies.

What is a quantum computer?

First off, it is not something that is very intuitive. If someone tries to explain it to you in simple terms, you are probably not getting a clear picture. A common layman description of a quantum computer is that it is like a regular computer, but instead of having bits that can be 1 or 0 it has quantum bits that can be both 1 and 0 at the same time. This part, is actually true. But usually the next step of the explanation is that since these quantum bits can be both 1 and 0, a quantum computer can do computations on all possible values of an input at the same time.

This would be crippling for cryptography because the security of every cipher/signature/whatever comes from you knowing a secret key (stored in your wallet) and other people not knowing that key. "Not your keys not your crypto," right? If a quantum computer could try all possible keys at once, it would be able to break every type of cryptography¹!

Fortunately, this is not the case. In reality, quantum computers are much more complicated and significantly less powerful than that. They do have capabilities beyond normal computers, and it does take the form of a kind of parallelism, but it is highly restricted. You can only leverage it if you are solving a problem that is particularly suited to the strange structure of quantum computing².

I won't try to explain exactly how a quantum computer does work, that is best done in a much longer-form format. What I will do is say that, from an outside perspective, you can get all the context you need from understanding that there are some specific quantum algorithms that can solve some specific problems substantially faster than the best algorithms we know of on classical computers. Outside of these algorithms, quantum computers don't have any special advantages or powers that we currently know of, and there is no reason to expect that they would.

Shor's algorithm: This is the big one. The reason people talk about quantum computers so much. The reason I am making this post, ultimately. Shor's algorithm is a quantum algorithm that is able to break encryption schemes based on factoring or the discrete logarithm problem, which include RSA, DSA, ECDSA and DSS. If these sound familiar to you, it is because they are currently what secure 99% of blockchains and near 100% of the internet in general. It doesn't do anything more than that, but that is quite a lot.

Grover's algorithm: This is a bit of a weirder one. Grover's algorithm is a quantum algorithm that can do a brute force attack on anything in sqrt(N) steps instead of the normal N steps, to try N possible keys. This is a more general attack, that works on essentially any form of cryptography¹. Fortunately, reducing N steps to sqrt(N) steps is actually not that powerful. It functionally halves the effective size of the key you are using. And we already are using some pretty large keys. sqrt(N) steps would still take you longer than the age of the universe to break existing ciphers. Moreover, there has been some research lately that suggests that in practice, Grover's algorithm would be even less effective than we think. This one is not a big worry.

Curent state of quantum computers: Shor's algorithm is really powerful, and it is as bad as people say, specifically for RSA, DSA, etc. Fortunately for us, it seems we are still several years away from it being implemented in practice, and that is with the most aggressively optimistic timelines for quantum computing. The biggest number they have been able to factor with it, on existing computers, is 21. For reference, a normal RSA modulus is a number about 1200 digits long. There will have to be a titanic engineering effort to scale up quantum computers to useful sizes. This is for a lot of reasons that I won't get into here, but the gist is that quantum bits are very unstable and the more of them you have, the more likely they are to break.

Blockchain impact

Let's fast forward a few years (or decades) and imagine that we have a functional, scaled-up quantum computer that can execute Shor's algorithm against normal-sized RSA, DSA, etc. keys. What would happen if this was released onto the world and blockchains looked basically like they do now? Well, the big problem is that with Shor's algorithm, you can take a public key (wallet address) and very quickly calculate the private key from that. This would let the owner of the quantum computer hijack any wallet that they want and generate transactions to drain the wallet of all its coins. This would probably crash the price of all cryptos into the ground immediately since they would not be trustworthy any longer, so there wouldn't be much of a financial benefit for this person, but it would certainly destroy cryptocurrencies as we know them.

Sounds bad, right? As I said before, quantum computers are not all-powerful, though. Hash functions, for instance, are not vulnerable to any quantum attacks. Proof-of-work would still be completely fine. A quantum computer would have no advantage in mining and would not be able to take over the BTC network.

But what about that whole every wallet getting drained thing? Fortunately, we have several great candidates for post-quantum signature schemes that could replace the broken ones. These are based on hard problems that are not factoring or discrete logarithm. There are strong reasons to believe that there are no quantum algorithms that would be able to break these. However, we still have a pretty significant problem...

Migration

If you want a quantum-secure blockchain, there are two options:

1) Start a new blockchain with a post-quantum signature scheme.

2) Migrate your existing blockchain to a new post-quantum signature scheme.

Since there are already (imo) way too many blockchains, and we don't want to lose all the value in existing ones, migration is going to be necessary. But there is a problem: how do you give every wallet a new key pair? The best you can do is to have a fork where you have every wallet create a new wallet that uses the new post-quantum signature scheme and signs a transaction to transfer all their coins to the new wallet. This is bad because there are millions of wallets, and not everyone would know to do this! It requires manual interaction from the owner.

Some chains have already done this, and it worked out generally okay, but they were more niche chains where it could be assumed that the holders are more active and aware of the community and events. With BTC and ETH there are people that hold them for a long time and don't bother to check what is going on. It would also be a field day for scammers, giving fake advice on how to migrate that actually steals all your coins.

Post-migration: This part is really interesting to me. Sometime after the migration, eventually a quantum computer will succeed in breaking the old signatures. This means that all those old, dead wallets (Satoshi's for instance) will be drained because they never upgraded to the new post-quantum cipher. Unless the new fork puts a time limit on upgrading old wallets, which would effectively destroy the coins of anyone who didn't upgrade in time. There are a lot of intricacies to this that I think will be quite surprising.

Conclusion

If you read this far, thanks! Hopefully this was interesting or helpful to some folks. The bottom line is:

1. Quantum computers are a threat, but not a catastrophe. We have new ciphers that are quantum resistant and are already being deployed.
2. Quantum computers are not magic and they don't break all cryptography. They are basically only good against RSA and DSA/ECDSA, it just happens that we really rely on those a lot.
3. Migration will be tricky and have to be done carefully. Probably a lot of people will lose access to their wallets. Keep an eye out for any plans that your favorite blockchain might have to migrate, because it will require you to do something manually to upgrade your wallet and it might be time-sensitive.

Happy to answer any questions you might have about quantum/crypto/anything and would love to hear what everyone thinks about this topic!

¹ Except information-theoretically secure stuff, but it isn't very practical.

² We technically don't actually know what the limits of quantum computers, or even regular computers, are. You may have heard of the P vs NP problem. There is also an equivalent question about quantum computers P vs NP vs BQP. In this post, I am assuming the widely-held belief that P < BQP < NP. This means that quantum computers have some additional capabilities that classical computers do not, but they cannot solve all problems in NP.