Quantum Attacks on Blockchain and How to Protect Against Them?

• Toshendra Kumar Sharma
• May 04, 2018

Blockchains have helped individuals establish trust over the internet due to their decentralized and secure nature. Bitcoin and other cryptocurrencies employ cryptographic principles to ensure security without relying on a centralized authority. With cryptography being the backbone of the entire operation, it is crucial to examine all of the potential threats that emerging technologies can pose to the future of Blockchains. One of the biggest such threats comes from quantum computers and their ability to use Shor’s algorithm to find the prime factorization of large numbers quickly. Let’s take a look at how this affects Bitcoin and what can be done to deal with this threat in the future.

How Are Quantum Computers Different from Classical Computer?

Classical computers rely on bits of 0’s and 1’s to make binary decisions. These binary decisions are then combined in order to perform complex computations. By comparison, quantum computers are not limited to the binary states of 0’s and 1’s and instead rely on the uncertainty within the atoms to significantly increase the efficiency of calculations. As a result, quantum computers can perform millions of times better than classical computers in some highly specific applications like prime factorization. One of these applications is referred to as Shor’s algorithm which is an existential threat to all kinds of internet security including SSL and TLS encryption along with the private keys in Blockchains. Shor’s algorithm was developed by mathematician Peter Shor in 1994 and simple terms it leverages the power of quantum computers to solve the problem of prime factorization very quickly compared to traditional networks.

Bitcoin’s private key generation and the RSA encryption algorithm which is commonly used in secure commerce websites (Secure Socket Layer), is based on the fact that it is easy to take two (huge) prime numbers and multiply them, while it is extremely hard to do the opposite. That means, given a very large number which has only two prime factors, it is very hard to find the two numbers with traditional computers. With the current classical computers, it would take 2128 steps to solve the prime factorization problem. Now, with Shor’s algorithm, that process is reduced to a mere 1283 steps which are significantly lower and therefore can be computed in a reasonable amount of time. Being able to use Shor’s algorithm efficiently would mean that Blockchains would become vulnerable to all kinds of malicious spend attacks. Additionally, it would undermine the entire cybersecurity that computers rely on presently. That is why public and private key cryptography which is based on asymmetric cryptography, is in trouble. The implications of this change exceed the threat to blockchains and cover nearly all existing applications. On the other hand, symmetric cryptography which is the basis of hashing in Blockchains is harder to break with quantum computers. With the current classical computers, it would take 2256 steps to break symmetric cryptographic algorithms like SHA-256. However, with quantum computers, that process is reduced to 2128 steps which are significantly lower but still very high.

How Bitcoin Will Deal With Quantum Computers

Bitcoin’s design allows both its signing algorithm and the hashing algorithm to be upgraded if quantum computers become powerful enough. Andreas Antonopoulos, one of the early adopters of Bitcoin, claims that present-day cryptography still has about 20 years worth of life left before it would be needed to be upgraded to deal with the quantum threat. Bitcoin uses both symmetric and asymmetric cryptography in hashing and signing respectively. As we discussed, symmetric cryptography which is used in hashing is more resistant to the quantum threat compared to asymmetric cryptography which is used in signing. The good thing is that the Bitcoin protocol has been designed while keeping the quantum threat in mind and therefore can be extended to deal with it in the future if quantum computers become more efficient.