The Truth About Bitcoin And Quantum Computers

Quantum computers are gradually becoming reality. The consequences for Bitcoin and other cryptocurrencies can be dramatic - but are far from uncontrollable. A team of scientists describes what quantum computers do for Bitcoin and how to make the transition to quantum-safe algorithms.

Quantum computers are still science fiction. Devices that bring little power with a tremendous effort. But the quantum engineers succeed in coupling more and more quantum bits - in short: qubits. So Google has recently introduced the quantum computer Bristlecone with 72 qubits. If the number of qubits continues to grow exponentially, the prediction is realistic that quantum computers will be wide enough from around 2031 to become a threat to many cryptographic techniques.

Click on the image to enlarge

It does not burn yet, but it is no mistake to deal with the topic already. Finally, Bitcoins should have no expiration date. A research group, especially the Center for Cryptocurrency Research and Engineering at Imperial College London, describes in a paper how quantum computers can attack Bitcoin and how to protect against it.

The involved crypto algorithms

To assess the danger, one must know which cryptographic mechanisms use Bitcoin and other cryptocurrencies. These fall into two categories:

• Signature Algorithms:
  These procedures consist of a public and a private key. With the private key one signs transactions, with the public one proves that the signature is correct. Cryptocurrencies usually use signature algorithms based on elliptic curves. For Bitcoin this is ECDSA, for some other currencies EdDSA or Schnorr signatures. Under normal conditions ECDSA is considered absolutely safe.

• Hash Algorithms:
  Hash algorithms are one-way mathematical functions that transform a value deterministically into another fixed-length value. It's best to try it on Hashgenerator.de. Bitcoin uses hash functions in two ways. First, the miners must compute hashes with SHA256 to find blocks, and second, the public key of the signature algorithm is hashed with both SHA256 and RIPEMD-160 to form the address. This step is extremely important, as we will see later.

Quantum computers have an impact on the security of these cryptographic algorithms. Why exactly, is very difficult to explain. Let me just quote the researchers: "Just as a classical computer is built out of bits, quantum computers use qubits that have two fundamental states (0 and 1). However, while a calculation is running, the state is a linear combination of both states (a superposition). "One knows this from quantum physics, that a particle is somehow in both states. This super state collapses into one of the two fundamental states as soon as one observes the system.

"This means that a quantum computer with n qubits can internally present the entire span of n-bit numbers and perform all calculations simultaneously. But once you measure it, the state will collapse into one of the two basic states and only output one of the results of the calculations. Quantum algorithms attempt to use this structure to amplify certain base states and increase their likelihood, making the result repeatable and conclusive. For some problems, quantum algorithms can solve complex problems much faster than conventional algorithms. "

And these problems unfortunately include crypto-algorithms.

How quantum computers attack cryptography

You do not have to understand all that in detail. Importantly, there are several quantum algorithms that attack cryptographic techniques in new ways:

• Shor's Algorithm:
  This quantum algorithm accelerates the factorization of integer exponentially. This drastically weakens the security of asymmetric cryptosystems such as RSA and ECDSA. Shor can be used to break the signature algorithms used by virtually all cryptocurrencies (except IOTA).

• Grover's Algorithm:
  This quantum algorithm can search unstructured data and find a hit with a relatively high probability. With Grover's algorithm, one can quadrally accelerate collisions of hash algorithms. This could theoretically be used to mine bitcoins, but it will probably take a long time for this to outperform Asics. If ever.

Since especially signature algorithms like ECDSA are threatened by quantum computers, we will turn to them. With conventional computers, ECDSA is impossible to break. But what happens if quantum computers are able to crack them?

It will be possible to guess the private key using the public key. However, this does not mean that such an operation is trivial or fast. Thus, it is believed that quantum computers with 2,000 to 10,000 logical qubits will be able to break the widespread RSA encryption (so far they reach 72). How long the quantum computer will need, one second, two weeks, or a year, depends on its strength and the number of bits of encryption.

The ECDSA encryption used by Bitcoin is believed to require about 1,800 qubits. However, for each effectively used qubit, a quantum computer must provide numerous physical qubits that correct errors. A cryptographer on Bitcointalk therefore estimates that a quantum computer will need more than 40,000 physical qubits to break ECDSA. And even if this is possible, it will not happen in a second, but will need a lot of arithmetic operations. How many exactly do I not know.

What happens when the time comes?

But suppose there are such powerful quantum computers that can break with Shor ECDSA in a reasonable amount of time. So what?

The good news is that the quantum computers will still not be able to steal Bitcoins that way. Because addresses are not a public key, but a hash of them, and these are far less prone to quantum cryptography. In other words, anyone who leaves his Bitcoin on an address does not run the risk of being stolen. The advice to use an address only once makes so much more sense.

The bad news is: There is another attack. The researchers call him the "kidnapping transactions" call. Once you sign a transaction, you reveal the public key. This makes the address useless for the future. Worse still, a quantum hacker can capture unconfirmed transactions. Because if the transaction is on the net, the public key is known. This can be exploited by a quantum computer: "Like a double spend, the attacker creates a transaction that transfers the same coins elsewhere, stealing the victim's funds."

Unlike a double spend, such abduction can be carried out not only by the one who is paying, but by any third party. Sending bitcoins becomes a difficult to control risk. The researchers acknowledge, however, that the effort is not trivial even for strong quantum computers: "Since the attacker not only has to create, sign and propagate the alternative transaction, but also first has to calculate the private key using the Shor algorithm, that's timining essential for this attack. "

Depending on the double-spending process, the hacker will have a few seconds to a few minutes to do it all. So even if quantum computers are theoretically capable of breaking ECDSA, that does not mean that they are fast enough to hijack transactions in practice. It is quite possible that such an attack will not only require 1,800 to 10,000 qubits, but much more. Cryptocurrencies with shorter block intervals, such as Ethereum with 13 seconds, should also be able to resist it much better.

Nevertheless, the attack remains problematic. It opens up a weak point in the system that can be exploited systematically, automatically and without risk. In addition, it is also possible to use the attack for DoS attacks or even make selfish mining attacks worse or more profitable for the miner. This would not only jeopardize individual credits, but the system Bitcoin in general.

How can you protect yourself?

Even if it does not burn for a long time, you can not think about it early enough on how to prepare for the day when quantum computers will break ECDSA. Fortunately, there are a lot of options.

On the one hand, you can gain time by increasing the bit number of ECDSA. Depending on the progress of quantum computers, this may or may not help. But it will only be a permanent solution if you switch to a quantum-proof algorithm. The authors of the paper point out which possibilities are already known for this:

• The McElieve system "resists decoding of unknown codes for linear error correction" and is therefore quantum safe. The price is that individual signatures are considerably larger (up to one megabyte).

• There are methods for hash-based signature, which can be attacked by quantum computers only to a very limited extent. The best-known of these concepts is the Lamport Diffie one time-signature, the Winternitz signatures used by IOTA also belong to this family.

• There is also the possibility of forming signatures based on lattices (lattice-based cryptography). Examples are the more theoretical methods GGH and NTRUSign.

It's important, the authors explain, "that the Bitcoin community agrees to implement a good alternative (or maybe more) that replaces cryptography with elliptic curves as the basis of transactions' signatures."

However, this will not completely solve the problem: Because to enjoy the benefits of the quantum-proof algorithms, all users have to move their coins to new addresses. If this does not happen by day X - the day quantum computers can hijack unconfirmed transactions - the Bitcoins will be more or less frozen. At least it will be impossible for large sums to transfer them without a significant risk.

Imperial College researchers are now proposing a solution to this problem: a concept that allows Bitcoins to be securely moved to quantum-safe addresses even after that time. The concept is relatively complex. It forms, as it were, a smart contract that composes a transaction to be valid only after a relatively long time has elapsed, and when evidence of ownership of both a conventional and a quantum secure private key is obtained. With this method you could probably also credit balances of non-quantum-safe addresses safely against all attacks on a quantum secure address.

If you want to know more about the method, you should read the last third of the paper. Time enough you will have for sure.

---

---

Image Sources:

• Post header created by myself
• https://eprint.iacr.org/2015/1075
• https://en.wikipedia.org/wiki/Shor%27s_algorithm
• https://en.wikipedia.org/wiki/Grover%27s_algorithm

Have a nice day!

LOVE&LIGHT