Will quantum computing undermine the security of cryptocurrencies like Bitcoin?

A Quantifiable Risk

Quantum computers, for all of their press, will not be used in everyday applications such as running word processors or playing games. Rather, they will help with large data processing tasks and problem solving. However, while most individuals on this planet only have positive intentions for such inventions, there are others who have malicious intentions.

Quantum computers have an incredible ability to perform multiple calculations simultaneously, unlike conventional computers. For example, modern computers could never brute force hack a 256-bit key by going through every combination whereas a quantum computer could achieve this with ease.

To put the speed difference into perspective, Google's D-Wave 2X quantum computer can solve algorithms 100,000,000 faster than modern computing devices. This means that brute force attacks on security protocols will suddenly become viable which will cause serious issues with global finance, computing, and information as a whole. So it comes as no surprise that Bitcoin is at serious risk from quantum computers becoming commonplace.

 

D-Wave quantum computer. Image courtesy of D-Wave Systems, Inc. [CC BY 3.0]

 

Bitcoin and Cryptocurrencies

Bitcoin, as well as other cryptocurrencies, have become increasingly popular for many reasons.

  • Cryptocurrencies enable near full autonomy, allowing individuals and businesses alike to purchase goods and services without revealing their identities (as individuals have addresses which are not associated with names or information regarding the owner).
  • The system relies on encryption to keep wallets (which essentially store user Bitcoins) secure so that others cannot access the Bitcoins.
  • Bitcoin is decentralized which means that there is no Bank of Bitcoin or a single server that is responsible for the entire system (this could lead to abuse). The Bitcoin system is maintained and supported by all computers on the network with all transactions being recorded in a public ledger.

But, without encryption, the Bitcoin system would never function and users would have next to zero confidence in the currency. Therefore, the security of Bitcoin and encryption is paramount for it to be a successful and useful cryptocurrency. So what will happen when quantum computers are introduced?

 

Bitcoin, the most famous cryptocurrency is heavily dependent on encryption. Image courtesy of BTC Keychain [CC BY 2.0]

 

Firstly, Bitcoin wallets use 256-bit encryption which is the only real defense against theft. But quantum computers would make quick work of determining private keys and therefore would compromise most, if not all, wallets on the system. This would either lead to Bitcoin being worth next to nothing or the Bitcoin system as a whole being abandoned.

On top of that, Bitcoin mining (the process of finding unclaimed blocks that return 50 coins when discovered) would become trivial and result in a sudden rush of Bitcoins in circulation. This increase in Bitcoin availability would cause hyper-inflation and thus a fall in Bitcoin value.

Bitcoin, however, is not the only victim of such a security breach. All other cryptocurrencies, online transaction systems, banks, financial institutions, websites, log-in systems, governments ,and even file encryptions would all be at risk.

 

 

If You Can’t Beat Them, Join Them!

Quantum computers are a threat when using conventional security protocols which rely on modern computers being too slow to ever crack keys larger than 128 bits. But what about a different type of security protocol that is not designed for conventional systems? What about quantum cryptography?


Read More


In quantum physics, there is a phenomenon which in itself is truly amazing: quantum superposition. Simply stated, if unobserved, a particle's state is not known and is said to be in a superposition (i.e., the spin of an electron is in all possible states). Once the particle is observed, the superposition is lost and the particle takes on a specific state. Then there is a second phenomenon called quantum entanglement whereby two particles are entangled so that, if the state of one particle is known, then the state of the other particle can be deduced.

These two phenomena, when combined, can be used to transmit quantum states from one user to another: this information could be a key that is to be used to decrypt a message using conventional systems. In classical computing, sending a key over a network unsecured is really dangerous as anyone can eavesdrop, obtain the key, and then decrypt any information that is then passed between the two users.

But in quantum cryptography, the key that is sent “unsecured” is in a quantum state. If the eavesdropper reads the key, the superposition state will be lost and therefore the original recipient will detect the loss of superposition and discard the key. Once the key has been passed, conventional encryption can be used to send messages (where the quantum eavesdropper has to then brute force attack the key). This method of key distribution is called Quantum Key Distribution.

 

 
The Bloch Sphere is used to represent a qubit. Image courtesy of Glosser.ca (own work) [CC BY-SA 3.0]

 

Currently, there are cryptographers working on the issue and are developing cryptographic methods to fights against quantum computers. For example, Llew Claasen, executive director of the Bitcoin Foundation, said that solutions are currently being worked on so as to keep the system immune to quantum technologies. However, as the Bitcoin system is decentralized, the entire system has to agree to the new change. This task may prove more difficult than designing the new system, itself.

 

Summary

Quantum computers pose a threat to encryption in general, which, if left unchecked, could cause serious worldwide damage (digitally). When quantum computers make their debut, new forms of cryptocurrency may arise which are designed to work with quantum systems to keep transactions and wallets secure.

Tech companies and governments alike need to realize this danger soon and begin to think about alternative cryptographic methods for data protection.

 

Comments

3 Comments


  • ronsoy2 2016-12-02

    First, brute force cracking is obsolete with virtually all significant entities using timed access for account passwords. Try three times wrong and you are locked out for an hour. No matter how fast your computer is you can only try three times per hour. Useless. In other systems where timed access is not practical, a change to unbreakable encryption can be implemented. Under current USA law, unbreakable encryption is illegal. (felony!) If everyone starts using it regardless, the law becomes instantly unenforceable so will end up like all other unenforceable laws: ignored. So the the quantum computer issue is moot.

    • rempred 2016-12-02

      Bruteforcing usually doesn’t refer to a password prompt, it refers to cracking encrypted data files or password hashes that have been acquired.

  • Jonathan Cressman 2016-12-02

    Robin Mitchell should read the bitcoin spec.

    Bitcoin uses eliptic curve asymmetric encryption which could be broken by a quantum computer if the attacker knew the public key.  However the public key for an output (unspent coin) isn’t published in the block chain when the output is created.  Instead the hash of the public key is published.  When an output is spent the spender publishes his public key and signs the spending transaction.  A person wanting to steal this bitcoin must then grab this published transaction, calculate the private key from the public key, sign a new transaction assigning the coin to himself, publish this new transaction and hope the new transaction gets included in the block chain before the original. 

    Other Points:
    1) The 256 bit hashes in bitcoin are safe from quantum computers, the best algorithm for finding pre-images (Grover) is order 128, still very safe. 
    2) Mining - mining is the process of finding numbers that when mixed with the transactions hash to a number less than the difficulty level.  Grover’s Algorithm might help a bit but all that would happen is the difficulty level would go up so that on average only one block is added every 10 minutes (25 coins at present). 
    3) Now lets assume our attacker not only has a quantum computer but he also has a really fast one (and he has a really fast classic computer because breaking ECC using Shor’s algorithm requires an obscene amount of classic computation).  If so he might be able to grab a published transaction and create a fake one and have a non-trivial chance of having his fake transaction included in the block chain.  This isn’t going to happen in the next 10 years.  In the mean time the bitcoin protocol will just switch to a different signing algorithm.  (a Merle signature scheme that only needs to sign 16 messages wouldn’t be to big, but I’m sure we will come up with something better in 10 years).