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 process similar to the above AND operation, several processes need not be calculated, but all are calculated simultaneously.

What attacks are possible with quantum computers?

By the way, it can be understood 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 methods have an extremely long running time - 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) can be an encryption or hashing function, this algorithm is also a threat to various cryptographic functions.

What is the current state of quantum computers?

Various 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. That is why the "worst case" is to be assumed: hidden hackers or the NSA could already use 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. To crack ECDSA encryption, the Shor algorithm would reduce the computational burden of finding a private key from a public key by a factor of 10 ^ -34. 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 be done 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 again in such short time 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 not physically 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.

According to the motto "Be your own bank", it would also be desirable if the individual Bitcoin user is not only crypto-fit, but quantum safe. In part two of this article series, we therefore discuss what possibilities we have for better protection of our Bitcoins.