Originally published in the NOWPayments blog
A close in-depth look at the effects of quantum computing on cryptography, blockchains, and cryptocurrencies.
Over the past few years, top computing companies including Google and IBM have been working on quantum computers — the most advanced and most powerful computers. These computers are built using the science of quantum physics allowing them to solve complex mathematical equations faster than normal computers and even the best of supercomputers today.
As such, these quantum computers are built to analyze mathematically encrypted files such as mobile phone messages, governments’ protected data, and individual financial data stored by banks — as well as private wallet keys on a blockchain, which stores cryptocurrencies.
IBM’s quantum computer at the University of Nairobi (Image: IBM)
The advancement of quantum computers makes all encrypted data vulnerable to hacking and theft. In this article, we discuss the development of quantum computers and why “quantum supremacy” might be the end of cryptography, blockchain technology, and cryptocurrencies as we know them.
Hint: It has to do with security.
Quantum computing is “the use of complex phenomena such as entanglement and superposition to perform computation.” These types of computers differ from classical computers in that traditional computers (even supercomputers) use silicon chips with bits (the language computers understand) represented in 0’s and 1’s during computations — there can only be one or the other, never both!
Intel’s 49-qubit supercharging chip (Image: Walden Kirsch photo)
On the contrary, quantum computers use quantum chips, changing the language to quantum bits (qubits), whereby a digit can take a value — 0, 1’s as well as a superposition of “0 AND 1.” This allows things to exist in multiple states at any given moment on the quantum processor.
These computers are re-known to work on computations much faster than the fastest computers available today. An article published in the Time magazine focusing on quantum computing reveals,
The Sycamore computer (a quantum computer built by Google) solved the random-number problem in just 200 seconds. Even the most powerful traditional supercomputer would require a somewhat pokier 10,000 years — give or take a century — to achieve the same feat.
Notwithstanding, the National Security Agency (NSA) and the National Institute of Standards and Technology (NIST) have both started intensive analysis of scale quantum research across the United States. As of January last year, the latter announced 26 out of 70 submissions on quantum computing will be using NIST funds.
With the advancement in technology, quantum computers pose a threat to encryption if powerful machines are built. Does this mean the end of cryptocurrencies and security?
In these next chapters, we explain how cryptocurrency wallets are secured using “asymmetric cryptography” and the challenges quantum computing poses to this security.
Cryptocurrencies are secured using asymmetric cryptography, a signature scheme which involves solving complex mathematical problems. This simply means blockchains (the underlying technology) generates a pair of “cryptographic keys” — public and private — with a mathematical relationship connecting them. As the names suggest, public keys are available openly while private keys are kept hidden.
To access the crypto wallets, users sign in their public keys using digital signatures (derived from the private key) maintaining the authenticity and security of these cryptocurrency wallets.
‘The one-way function’
Asymmetric cryptography is based on mathematical computations and the principle “one-way function.” This principle simply states that you can derive the public key if you have the private key of the wallet but not the other way around. While not theoretically impossible, this cryptographic algorithm cannot be broken (finding the private key using the public key) as to do so would require millenniums of years and extreme computing power to perform such a calculation.
In the 1980s, the world, with the help of Paul Beinhoff, a professor in nuclear chemistry, welcomed the first variations of quantum computing changing the world of asymmetric cryptography and encryption.
Peter Shor: Creator of the Shor’s algorithm (Image: YouTube)
Fast forward to 1994: a mathematician, Peter Shor developed a quantum algorithm (Shor’s algorithm) that was able to break (decrypt) the first public-key cryptographic system, RSA. This opened a whole new world of encryption, meaning a better and more powerful quantum computer could be used to derive the private key from a public key — effectively breaking any blockchain security through falsifying the digital signature.
To understand how much cryptocurrencies are in danger of a security breach from quantum computers, let’s focus on Bitcoin — the largest and most secure crypto at the moment.
Bitcoin allows a myriad of financial transactions to take place: from simple person-to-person payments to escrow services and other transitionary dealings. In our case, we will focus on simple P2P payments on Bitcoin. P2P payments can be categorized into two main categories — each differently affected by quantum computing.
Pay-to-Public Key (p2pk)
The first, “pay-to-public key (p2pk) addresses are BTC addresses that are represented by the public key. Transactions from this address are publicly available on the blockchain — anyone can obtain the public key. These are the most vulnerable to quantum computing hacks.
Using Shor’s algorithm, a hacker could simply obtain the public key and make millions and possibly billions of calculations to derive the private key in a short amount of time. Quantum computers (on Shor’s algorithm) use integer factorization making it easy to derive a private key from a public key.
P2PK addresses vs P2PKH addresses
Pay-to-public hash (p2pkh)
The second type of address is the pay-to-public key hash (p2pkh). These addresses use a hash of the public key hence not revealing the full public key to everyone. These addresses solve the issues on p2pk addresses such as the lack of “checksum” function and the lengthy nature of the latter.
Unlike p2pk, these addresses do not reveal the public key. The public key is only revealed once the owner sends the amount to a new address. As long as no one sends BTC to the p2pkh address, the public key will remain unknown. However, once funds are sent from the address, the public key is then revealed.
Similar to p2pk addresses, once the public key is revealed, quantum computers can be used to compute the private key. As such, a number of third party digital currency wallet custodians make sure users receive a new p2pkh address after every transaction.
Elliptic curve cryptography (ECC)
Elliptic curve cryptography is a short approach used in public-key cryptography to provide similar security for digital signatures and random number generators to Non-ECC methods. However, the rise of quantum computers could be used to break the elliptic curve cryptography by computing discrete logarithms — now it is possible using Shor’s algorithm.
Could this also be used to “break” Bitcoin and other cryptos?
As seen above, the risk for quantum computers to end cryptocurrency security is real. So far, Google, Microsoft, and IBM have built two- and three-qubit chips. Notwithstanding, Google’s Sycamore computer is a 54-qubit chip computer, and while not commercially available, it shows with unlimited resources, better and more powerful computers will be built to scale.
Google’s CEO, Sundar Pichai, checking out the “Sycamore” Quantum computer. (Image: NBC)
Quantum computers have still a long way to go to be able to break encryption. Given the rapid developments in the field, experts say it will take some decades to have an enough-powerful quantum machine. Vlad Miller, CEO of the Ethereum Express Company said the risks of current quantum computers in decrypting BTC remain low as it would need the rearrangement of the whole blockchain to affect it.
In this sense, blockchain is resistant to quantum computers, and the growth of computing power will not affect the security of the system,” Vlad said.
At the moment, the threat of quantum computers remains low but it raises a reason for the crypto ecosystem to start looking for solutions. In the next chapter, we look at the solutions that allow us to survive quantum supremacy.
Quantum computing presents a long-term challenge for blockchain security and cryptocurrencies. However, some tech firms have started to prepare for life after quantum supremacy. This is a blind-battle in that the actual risks of quantum computing are not yet fully known but quantum-resistant cryptography solutions need to be built.
Andreas M. Antonopoulos, a Bitcoin educator, however, has repeatedly said the effect of quantum computers on Bitcoin and cryptocurrencies could be overestimated. Speaking in 2017, Andreas said even if quantum computing is available today, it is most likely that governments will hoard the technology until they find a “dire need to use it, and Bitcoin is not a dire need.”
Moreover, the Bitcoin algorithm can be changed if there is a consensus allowing prevention techniques once quantum computers hit the streets.
As mentioned above, the quantum computing era has almost arrived but it is still at its infancy stage. While the effects of qubit computing and quantum mechanics are negligible for now, there is a long-term threat to cryptography and other forms of encryption with the rise of the technology still ahead.
Finally, the flexibility of blockchains and cryptocurrencies such as Bitcoin allows developers to switch the algorithm to quantum-safe platforms if need be, such as quantum-proof algorithms offering protection against the rise of quantum technology.