Bitcoin: The Quantum Threat Creeps Closer

Quantum computer and Bitcoin. Here is a hot series that is not about to fade, especially after IBM’s latest experiment.

Cryptography and Bitcoin

Before explaining IBM’s results, let’s take the opportunity to simply recall how bitcoin works. It’s not that complicated to get a good idea of it.

The bitcoin uses several cryptographic algorithms (math). One of them is a hash function called SHA-256. It is especially with it that bitcoin miners work.

The job of a hash function is to transform any amount of data into a “hash.” Under the hood, a hash is just a number. A very large number. Cryptography works with very large numbers.

“Mining bitcoins” means passing all the data of a block (a few thousand transactions) through the SHA-256 grinder. The goal is to find a hash lower than a target number (by trial and error, thousands of billions of times per second, hence the electricity consumption).

The miner who first finds a valid hash can add a block to the blockchain and receive the reward (a little more than 3 bitcoins currently). Miners create a block about every ten minutes.

That’s the “mining” part.

The other major cryptographic aspect of bitcoin concerns the construction of transactions. This time it’s about so-called “public key” cryptography. This is what would be at the mercy of a powerful enough quantum computer (and not SHA-256).

A wallet is not much more than a program generating key pairs used to build transactions. Creating a transaction means creating a “utxo,” that is, a little piece of code that locks a public key to bitcoins (a number).

The principle is that only the private key can unlock the bitcoins.

Very well. So, concretely, what is the threat?

6 small bits

It is mathematics that secure bitcoin. It is basically impossible, within a reasonable time frame, to calculate a private key from a public key. It would take hundreds of millions of billions of years for the most powerful classical computer in the world to accomplish this.

But not if one has a powerful enough quantum computer. And the fact is that the day J is arriving faster than expected since IBM has just demonstrated again the feasibility of such a quantum attack.

The American giant has just successfully broken a 6-bit ECC key using Shor’s algorithm with its IBM_TORINO quantum computer of 133 physical qubits. IBM had already succeeded in breaking a 5-bit key using the same processor in July.

Should we worry? Yes and no. What is worrying (for bitcoin) is that it works. What is less worrying is the key size.

A 6-bit key is insignificant cryptographically. That means the solution space is 64 (2⁶). A common PC would break such a key in a few microseconds.

This experiment is therefore a proof of concept rather than a threat to bitcoin and its 256-bit keys which are 2¹⁵⁰ times larger. The gap to bridge is still astronomical. It would require millions of physical qubits and probably new advances in quantum error correction.

We are not there yet. For example, IBM’s largest processor, Condor, has 1,121 physical qubits. IBM’s roadmap only predicts 200 logical qubits by 2029. Yet, more than 2,330 logical qubits would be needed to hope to break a bitcoin key in less than a month.

But beware… IBM still thinks it can make it by 2033:

Is this the end of bitcoin?

Not at all. The quantum threat will potentially be real within a 3 to 10 years horizon. The Pauli group believes it is not impossible that bitcoin could be broken between 2027 and 2033. More likely 2033 than 2027.

So we must act as soon as possible to test hypotheses, rotate keys, create post-quantum roadmaps and ensure that bitcoin has nothing to fear on day J.

The problem is that we do not yet have a perfectly ideal solution. Post-quantum cryptography algorithms (for example, Kyber or Dilithium algorithms) would translate into a net reduction in the number of transactions per block (larger signatures and keys).

Our article on the trade-offs: Bitcoin, the quantum threat is approaching.

Moreover, the Bitcoin protocol is not that easy to change (which is a good thing). We currently have proof of this with the op_return controversy… Wallets must be upgraded to support post-quantum cryptography. Hardware wallets will also need new firmware.

Above all, every bitcoiner will have to move their bitcoins to post-quantum addresses. This won’t happen overnight.

Let’s finish by highlighting that your bitcoins will be vulnerable to a quantum attack if and only if you reuse your bitcoin addresses. You must never do that. Generate a new address for every transaction!

In total, about 33% of BTC are currently vulnerable. Approximately 6.36 million bitcoins. Of this grand total, 4.49 million BTC are vulnerable due to address reuse. The rest are vulnerable due to very old types of addresses (mainly bitcoins from Satoshi Nakamoto).

Don’t miss our article on this topic: Check if your Bitcoins are threatened by the quantum computer.