Can a quantum computer destroy Bitcoin?

Could quantum computers harm Bitcoin? Of course, elliptic curve cryptographyhas been carefully studied since thethe topic of quantum computers has become mainstream. It is worth recalling that Bitcoin is designed to eliminate the need for trust through cryptographic proof. But this doesn't only apply to Bitcoin. The two most common cryptographic algorithms areRivest-Shamir-Adleman (RSA)and elliptic curve cryptography (ECC). And, as a rule, the information that you exchange over the network is encrypted using RSA or ECC. But, these systems are vulnerable to attacks from quantum computers. A sufficiently powerful quantum computer can be a security issue for any online interaction.

From the translator:

Quantum computer- a computing device that usesphenomena of quantum mechanics for data transmission and processing. A quantum computer, unlike a conventional one, operates not with bits - capable of taking the value either 0 or 1, butqubits, having values of both 0 and 1.In theory, this makes it possible to process all possible states simultaneously, achieving significant superiority over conventional computers in a number of algorithms.

Encryption Today and Shor's Impact

Encrypting messages allows only an authorized recipient to read them. In turn, the security of encryption depends on the complexity of decryption without a key.

For example, RSA relies on a complex problemfactorization of numbers. It is easy to multiply two primes, but taking the resulting number and getting these two numbers back is difficult. It takes more time than the age of the universe to compute a single 4096-bit key on a classical computer.

Note translator In mathematics, factorization or factoring isdecompositionobject, such as a number, into the product of othersobjects or factors that, when multiplied, give the original object. Integer factorization for large numbers is a very difficult task. There is no known way to solve this problem quickly. Its complexity underlies some of the public key encryption algorithms such as RSA.

However, quantum computers solve problemsdifferently than classic computers. Shor's algorithm is able to find the basic factors of numbers and can solve the factoring problem faster than a classical computer.

Note translator In 1994, American mathematician Peter Shor discovered a quantum algorithm that surpassed its classical counterparts.

This means that someone who is purposeful enough and has a powerful quantum computer can theoretically get your private key from your public key.

Learn more about private and public keys

Read more:Bitcoin: An Introduction for Developers

You cannot give the private key to anyone, because... it can be used for an unwanted transaction[money may be stolen from you]... In general, as quantum computers are constantly improving, the security of RSA is called into question.

RSA has existed since 1977 and is still used today.day. Later, it was recommended to use ECC because there are shorter keys and higher speed. However, ECC is also vulnerable to Shor's quantum algorithm.

Therefore, recent scientific advances in quantum computing make the long-term security of RSA and ECC rather questionable.

In 2015, due to fears of such attacks, the NSA announced that it planned to replace the recommended ciphers from the Suite B list with “quantum-resistant” algorithms. In January 2019, NIST[US National Institute of Standards and Technology]published a list of 26 algorithms thatcan resist attacks by quantum computers. And although a few of them are indeed worthy candidates, and it is simply worth choosing the best one - cryptocurrencies have a rather specific architecture and different standards, which makes the transition much more difficult.

How much power does a quantum computer need to destroy Bitcoin?

How powerful should this “Bitcoin quantum killer” be? Microsoft Research said[August, 2018]that breaking discrete logarithms on elliptic curves will require fewer qubits than for a 2048-bit RSA key, which requires at least 4000 qubits.

Note translator 4096 qubits to be exact. In 2015, the number of qubits to crack a 2048-bit keyRSA was estimated at 1 billion ...

However, these are ideal "logical" qubits. Many more physical qubits are needed to fix errors and other necessary processes.

Although, for a standard 256-bit key, about 2500 qubits are needed. And yet, John Preskill, in his lecture on quantum information, noted that[for full result]quantum computers will need about 10 million physical and 10 thousand logical qubits.

In general, modern quantum technologies are stillfar from it. Not so long ago, at the end of 2017, IBM announced that they were able to create a system with 50 qubits, and in early 2018, Google announced a system with 72 qubits. In turn, the IonQ company, using ion traps, presented a quantum computer with 160 qubits and performed operations on 79 qubits.

Additionally, DWave has released itssystem with 2048 qubits, but, it is based on quantum annealing, and cannot use Shor's algorithm. However, here, ultimately, the goal is to create sufficiently powerful quantum computers for the purposes of science: chemistry, optimization, machine learning.

And although this is still a long way off, it will still affect those cryptocurrencies that are in circulation today.

The quantum computer threat to cryptocurrencies

Despite the fact that up to powerful enoughquantum computers suitable for such a task are still far away - this is still a future threat to modern cryptocurrencies. Therefore, it is important to think about it today.

The main problem is that quantumthe computer can calculate the private key used to sign a transaction based on the public key that is visible during the transaction. Therefore, it is possible to make unauthorized expenditure[commit theft].

How do you reduce this threat? There are only a few weaknesses that potentially allow quantum computers to gain access to coins.

Public key

First, the attacker must obtain an openkey. And although the wallet address is based on a public key, it is hashed by algorithms that are currently not susceptible to attacks by quantum computers. However, during the transaction, the public key is visible.

For each transaction, the owner authorizes the transfer of the coin to another address by signing the hash of the previous transaction and the public key, and then adds them to the end of the chain.

The easiest way to see what happens during a transaction is to see the code in action. To do this, you can use the pybitcointools service:

Step-by-step algorithm (briefly):

Creating a private key
Generating a public key from a private key
Signing a transaction with a private key
The public key is visible in the transaction code
Sending a transaction

</p>

***

</p>

Although the public key is visible duringconducting each transaction - without first completing the above steps, obtaining a private key will take more time for a classical computer than the age of the universe, so the scheme is safe.

At the same time, for today, for the majority of respectablethe standard is a hierarchical deterministic wallet. This wallet allows you to use multiple addresses. This means that once the private key is used for a transaction, it is no longer valid. Therefore, coins can be intercepted only at the very moment of the transaction.

***

Reusing wallet addresses

Besides the vulnerability of cryptography itself -the security of your coins depends on the exchange. Not all exchanges provide a hierarchical deterministic wallet, so many simply don't reuse the address. However, if they do this, the private key can be used again to sign the transaction. This means that a long-standing transaction can be used to recover the private key and, accordingly, move coins.

Fast enough attacks

But, even if you do not reuse addresses -there is still time for an attack during the transaction. Thus, until the transaction is confirmed, it remains vulnerable. And yet, for a quantum computer, this short time is enough to redirect a transaction.

Craig Gidney and Martin Ecker published an article in May 2019 on how to compute 2048-bit RSA integers in 8 hours using 20 million qubits.

The average Bitcoin transaction confirmation time in June 2019 was 9.47 minutes. However, there were periods when the average confirmation time reached 11,453 minutes - more than 7 days!

Therefore, all an attacker needs to do with a sufficiently powerful quantum computer is to intercept the transaction, charge it with a higher commission, and redirect it to his own wallet.

To prevent this - you can set forreal wallet owners have extremely high commissions for each transaction. But, given the fact that it is the low fees that make cryptocurrencies so popular, this can harm them.

Lost coins

Ideally, it is worth planning the transition to newcryptographic standards long before there was a giant quantum computer. People must manage to move their coins before the time when real risks arise. Over time, elliptic curve cryptography will become insecure, and the value of the blockchain may go to zero. The transition will solve the problem of a quantum computer, which in the future can gain full access to cryptocurrencies.

At the same time, some bitcoins have long been lost - their owner does not have a private key, which is necessary for making transactions.

</p>

Perhaps some of these lost coinsis located on exchanges that have reused addresses, and therefore old coins remain vulnerable. If you get access to the public key, then through Shor's algorithm there is a chance to restore these old coins.

And if the person who receives these coins -starts to sell them, then the bitcoin rate may collapse, which will undermine the credibility of the system. Also, additional questions arise. Since the amount of bitcoins is limited, is it worth reissuing these coins? Or will the total capitalization decrease?

Transition to post-quantum algorithms

The above issues matter ifcontinue to use elliptic curve cryptography. However, the problems associated with the growth of quantum computing power can be avoided by changing the algorithm used to generate a public key from a private key. True, it is necessary to choose an algorithm that is truly capable of resisting quantum attacks.

This is called "post-quantum cryptography". The National Institute of Standards and Technology (NIST) is leading efforts to evaluate and standardize post-quantum cryptography techniques because it needs to replace Suite B ciphers that are vulnerable to a quantum computer.

Currently, cryptocurrencies are being tried onvarious encryption algorithms. One approach is to use symmetric cryptography, which is less vulnerable to quantum computing than asymmetric cryptography.

For example, Fawkescoin is trying to solve thisproblem, demonstrating that a distributed network can be implemented using symmetric cryptography. In turn, other coins such as the Quantum Resistant Ledger use hash-based cryptography. After all, hash-based algorithms are still able to resist attacks from quantum computers.

A look at the post-quantum future

Actually, predict the future of technologypretty hard. And it is likely that quantum computing will not be the only technology that will compromise the security of cryptocurrencies. Sometimes it only takes one technological leap to get us where we never thought we were. And it is quite possible that the cryptography standards will have to be updated several times.

One of the permanent properties of technology is thatthat there is always progress and new breakthroughs, even if we do not know what they will be. Not so long ago, Zapata Computing published an article on Variational Quantum Factoring, which can use hybrid Noisy Intermediate Scale Quantum (NISQ) devices with hundreds of qubits to calculate factor numbers. Of course, this technology is not yet well tested and has limitations. Nevertheless, this confirms the fact that there are many opportunities for creating new algorithms and conducting research, which can significantly accelerate progress.

It is possible that quantum computers will never be able to grow to 2500 qubits. However, a quantum computer can solve many other problems, not just using Shor's algorithm.

For example, Google uses quantum modeling to study efficiency issues in the production of fertilizers, which consume 1-2% of the world's energy.

In addition, more users of quantum computers will almost certainly accelerate the impact on the world's economic, political and social problems.

At the same time, for cryptocurrencies, quantum computerscan be considered a potential threat in the long term. Progress cannot be stopped, and technology can be used for a variety of purposes. However, if elliptic curve cryptography is compromised, we will get more problems than just losing coins. Understanding and preparing for the quantum threat is now critical. At the same time, one cannot hold back useful technology out of fear of it.

Already now it is worth asking the following questions: are quantum computers a threat to your cryptocurrency portfolio? Is it possible to build a quantum computer powerful enough to effectively attack Bitcoin? Should you start worrying about it now?