Quantum computing, theorized for decades is finally becoming a reality today. Companies such as IBM have created functioning machines which make use of 5 qubit processors, realizing the theory and demonstrating to the world that it is possible and that we will continue to see progress in the near future. This progress has generated its share of media hype, as quantum computing has the capability of defeating standard cryptosystems previously considered secure against regular digital computers. We will not likely see quantum computers with sufficient power to defeat standard cryptosystems for quite some time, but we do know that many cryptosystem-reliant technologies are theoretically vulnerable. This includes cryptocurrency technology.
Quantum computers use the properties of quantum mechanics, such as superposition and entanglement, to create qubits. Unlike digital bits, qubits are not limited to the two states of on or off and therefore have greater possibilities which can be taken advantage of by quantum algorithms. Shor’s algorithm is one of such algorithms, first formulated in 1994, which can be used to complete integer factorization problems in polynomial time, a previously unsolved issue in computer science. This presents a new issue for digital security, as modern asymmetric encryption algorithms are largely based upon the concept of the discrete logarithm problem; a function which is easily calculated in one direction and computationally infeasible to reverse (before the age of quantum computing, that is).
Shor’s algorithm and its variants can be used to efficiently defeat standards designed around the difficulty of integer factorization, such as RSA, or standards based upon the discrete logarithm problem, such as the Diffie-Hellman protocol and elliptic curve cryptography. In fact, the NSA has practically suggested that organizations should skip from upgrading RSA to elliptic curve cryptography and instead make the transition to quantum resistant algorithms. The NSA, aside from what it takes from academia, also makes its own advancements in cryptography with well-funded, internal projects, so they are likely one step ahead of the public. The dangers of quantum computing may be closer than had been previously imagined.
When quantum computing reaches sufficient levels of sophistication, public-key cryptography as we know it will be dead. Unfortunately, this includes the current conception of Bitcoin, as blockchain technologies will be vulnerable to attacks previously deemed impossible. Bitcoin key creation is managed by ECDSA, a standard using an elliptic curve algorithm to determine a private/public key pair. A randomly generated private key is created and multiplied against a predetermined point on an elliptic curve, creating a private and public key pair. The public address then goes through a series of processing through several hashing functions and modifications to create a Bitcoin address. So not only are Bitcoin’s private-keys protected by elliptic curve multiplication, but the created public-key is also protected by a series of hashing functions which are impossible to reverse, even with the theoretical powers of quantum computing.
One-time Addresses are Safe
If a user never spends any Bitcoins and simply receives funds with an address that user is safe, because the hashing process makes it impossible to see the public-key used to generate the address. However, to spend the funds the owner must reveal the public key to the network and sign the transaction with his private key. It is at this point that the user’s funds may be at risk to new quantum computing attacks. Essentially, the elliptic curve algorithm used to generate the public key can be theoretically reversed by quantum computers, revealing a user’s private key and making it possible to hijack a user’s balance. Once the private key is revealed any balance remaining with that address would be entirely compromised, as the attacker would have both the private and public key, allowing him to spend any of that addresses leftover funds.
Luckily, it is recommended practice to use Bitcoin addresses only one, although not all users do this.
Bitcoin mining is also dependent on SHA256. Bitcoin miners must find solutions to specially designed hashing problems in order to authenticate transactions on the blockchain and be rewarded with newly created Bitcoins. However, quantum computers could potentially take advantage of Grover’s algorithm for a quadratic speedup in hashing, basically halving key lengths. This could be used as an advantage in Bitcoin mining, as it would greatly speed up the rate by which a miner using a quantum computer could find solutions. It is technically possible to mitigate the effects of Grover’s algorithm by doubling the key length size to maintain the same difficulty as before. However, this spawns new issues, such as the block size limit controversy, which brings to light the enormous difficulty of implementing a hard fork, such as migrating to more difficult hash algorithms. There has also been a considerable effort in keeping the blockchain maintainable in size, yet the blockchain is still enormous, so a change that might increase standard block sizes would be undesirable.
Luckily, the risk presented by Grover’s algorithm is minute compared to the security risks presented to elliptic curve cryptography. The appearance of quantum computers using Grover’s algorithm in mining is more comparable to the appearance of ASIC hardware mining rigs, which some thought would greatly damage the Bitcoin network when they the first appeared a number of years ago. SHA256 isn’t nearly endangered to the extent of elliptic curve cryptography by the new developments of quantum computing, and finding a solution to the hashing problem will certainly be less urgent than finding a solution to the elliptic curve public/private-key problem.
If quantum computing reaches a high enough level of sophistication, it could threaten the integrity of the Bitcoin system. However, this realization highlights the beauty of cryptocurrencies themselves. Bitcoin was originally developed as the solution to decentralize currency, a problem never before solved. It is now developed by a massive community of sophisticated engineers, programmers and mathematicians and kept alive by those who believe in the principles of free trade. It is capable of evolving to adapt to current developments.
There is still plenty of time to prepare, because powerful quantum computers are still a ways off in the future. Vitalik Buterin, co-founder of Ethereum and the Bitcoin magazine has suggested the adoption of Lamport signatures to solve the issue of the elliptic curve vulnerability in the current Bitcoin model. Other solutions have also been proposed, and some new standard will certainly be adopted by the Bitcoin network once quantum computing becomes a real threat. If the current conception of Bitcoin dies, we will adopt a system more suitable to function within the circumstances of the time.
For now, avoiding re-using addresses should be sufficient protection from anything quantum computing can bring to bear in the near future.
 To learn more about the possible effects of quantum computing on modern cryptosystems, see “Post-Quantum Cryptography” - http://pqcrypto.org/