The quantum computers are coming! Is this Bitcoins end?

Regularly journalists report the danger that quantum computers are supposed to mean for Bitcoin and many other cryptocurrencies. But how dramatic is this threat really? This article discusses the topic quantum computer on the example of Bitcoin.

A look into the virtual forest of leaves shows that quantum computers are presented as a threat to Bitcoin and other cryptocurrencies. Whenever updates on the current state of development are presented, the respective authors point out what this development would mean for encryption.

The picture is dystopian: All encryption can fall victim to the quantum computer, our accounts and thus our privacy are defenseless against the theft of anonymous hackers or the NSA. With regard to the threat to RSA encryption, this may even be true.

Recently, this fear is linked to the trend of cryptocurrencies: with quantum computers, Bitcoin would be at the end, the wallets could be emptied, and the whole system would go down – or so some circles represent Cryptogeddon.

The concern is not entirely unfounded and has led to several projects already using encryption algorithms that are quantum resistant. So you promise that the wallets themselves are unhackable for quantum computers.

In that respect, it is understandable that many Bitcoin investors wonder why Bitcoin is not taking action. In order to answer this question, this article aims to assess the endangerment of Bitcoin by quantum computers.

What can a quantum computer do?

To correctly assess the danger of quantum computers, it is important to understand their capabilities and limitations. First of all, the article would like to outline what a quantum computer is.

Classic computers are digital computers that process information about zeros and ones. A bit can be either 0 or 1. More complex information is realized over more bits, processing them via logic circuits. For example, an AND circuit gives a 1 only if a 1 is sent over both inputs. For an AND operation, four possible combinations result, which in the worst case all have to be calculated in order to arrive at 1:

0 AND 0 returns 0
1 AND 0 returns 0
0 AND 1 returns 0
1 AND 1 gives 1

A quantum computer stores information in so-called qubits. These make use of phenomena of quantum mechanics. Some readers will know the thought experiment “Schrödinger’s cat“: A psychopath locks a cat in a box, into which he has placed a randomly opening capsule of hydrogen cyanide. If this opens, the cat dies. As long as the box is not open, the cat can be described as both dead and alive. Transferring to qubits means that they can not be written as 0 or 1, but as 0 and 1 at the same time. One can imagine accordingly that in a similar process as the above AND operation not several processes must be calculated, but all are calculated at the same time.

What attacks are possible with quantum computers?

In the above, one can imagine that quantum computers can dramatically reduce the running time of algorithms. And that is not purely speculative: Even without a quantum computer, scientists have already developed algorithms that have a certain relevance to the security of Bitcoin. The goal of the Shor algorithm is to factorize large numbers, which is relevant to many cryptographic processes. For example, RSA is based on the fact that factorization techniques have an extremely high duration – and are therefore indirectly endangered by quantum computers.

In addition to the Shor algorithm, the Grover algorithm is also known: this involves searching within an unsorted database or inverting a function. The Grover algorithm thus allows for a function f (x) = y to calculate the x for a given y. Since f (x) may be an encryption or hashing function, this algorithm is also a threat to various cryptographic functions.

What is the current state of quantum computers?

Several companies and institutions have already developed quantum computers. The company D-Wave Systems is said to have developed four computers. D-Wave 2000Q will work with a total of 2048 qubits. However, one can hear several critical voices calling into question the properties advertised by D-Wave Systems. In addition, according to Edward Snowden, the NSA is working on a cryptography-focused quantum computer. As a detectable maximum you can see the 70 qubit computer from Google.

Statements of the form “that’s the earliest in 20 years” has often refuted the reality of the third millennium. Therefore, it should be assumed from the “worst case” that hidden hackers or the NSA is already using quantum computers.

Is it possible to crack Bitcoin’s private key with quantum computers?

An often-mentioned problem is that ECDSA encryption can be cracked via this Shor algorithm via quantum computer. This is a very big problem because you generate the public key via the ECDSA encryption from the private key. In order to crack an ECDSA encryption, the computational effort to determine a private key from a public key would be reduced by a factor of 10 ^ -34 using the Shor algorithm. Even a very slow machine that can do a calculation per second would not even take two days to find the private key.
Is everything really insecure then?

What many often overlook, though, is that in the case of Bitcoin, there are two encryptions between the attacker and the private key. That one must determine a private key from a public key is known. This can happen via the Shor algorithm, as shown. The attacker will normally not see the public key itself, but its hash. This hash is the wallet address.

Specifically, the following cryptographic processes interlock: From the 256-bit private key, you can generate a 512-bit public key using ECDSA encryption. This turns a SHA256 algorithm into a checksum, which you can turn into the wallet address. The attacker does not only have to determine the private key from the public key. He must first generate the public key from the wallet address.

In principle, hackers can crack SHA256 using the Grover algorithm. However, this algorithm only achieves quadratic acceleration. This means that an attack on a SHA256-generated hash requires about 2 ^ 128 or 3.4 * 10 ^ 38 arithmetic cycles. Currently, supercomputers in the world can handle about 10 ^ 17 arithmetic operations per second. This quantity is assumed to be the upper limit. In principle, it can not be assumed that one can prepare a so-called entangled state at such short intervals after successful measuring processes. A quantum computer with so many qubit operations per second would need only 107.9 billion years to find the public key instead of 4 * 10 ^ 52 years. This is still much bigger than the age of the universe!

Admittedly, there is another algorithm that promises a cubic runtime optimization. With this, a quantum computer, in the case of 10 ^ 17 qubit operations per second, could crack the connection between wallet address and public key in 15 years.

Even assuming a supercomputer that is physically physically not possible and using a comparatively unknown algorithm, the hack cost would dramatically outweigh the benefits.

What is Bitcoin doing and what can you do?

It turns out: Bitcoin is comparatively quantum safe. Of course, this is only as long as no one develops a better algorithm than Grover for finding the public key. So it’s still interesting to see if Bitcoin developers are even addressing this issue.

True to the motto Be your own bank, it would also be desirable if the individual Bitcoin user is not only cryptofit, but quantum safe.

image by shutterstock