Quantum Computing and Blockchain

Mustafa Inamullah
Jul 27, 2018 · 6 min read

An Honest Introduction to Quantum

Popular science journalism severely overestimates the applications of quantum computing. Quantum computing is fantastic at doing a small, specific subset of calculations, but it won’t be able to magically “try all the answers” in parallel.

At MIMIR, whether we are presenting at conferences or working directly with our growing customer base, we’re often asked by existing companies if incorporating blockchain is worth it for them. One of the most prevalent causes for concern that we hear is that “quantum computing will soon make blockchain obsolete, so why bother advancing the tech?.” Hearing this question enough we’ve decided to put the threat of quantum computing into an honest and realistic perspective. In short, quantum will not be the end of blockchain and it is not as all powerful as you may think it is.

However, there are areas which Quantum computing is likely to disrupt inside of encryption and cryptography. This is true in the case of blockchain technology. Quantum has the ability to crack the encryption and signature schemes used in cryptocurrencies. However, there are several adaptive measures taking place that aim to help prevent the quantum threat.

To understand where the Quantum threat exists, we first need to understand how encryption works. A lot of this will be a gross oversimplification for explanatory reasons.

RSA vs ECC Disclaimer

For the purpose of understanding, we will be using the RSA (Rivest–Shamir–Adleman) cryptosystem. This is the system used by HTTPS. RSA Encryption uses prime numbers and factoring to create a one-way function that makes it easy to encrypt something yet very difficult to reverse-engineer the data from the encryption.

Bitcoin and Ethereum do not use RSA. They use ECC (Elliptic Curve Cryptography). ECC still relies on a one-way function, except instead of using prime numbers and factoring, it relies on points on an elliptic curve. ECC produces much shorter keys and is applicable in the use of signature schemes.

When you are trying to crack a private key through RSA encryption, you are basically trying to find the correct prime factors of a really big number. When you are trying to crack a private key through ECC, you are basically trying to find a “random” point on an elliptic curve. Though they are different, their relationship to Quantum computing is very similar. Whether it is finding factors or points on a curve, quantum computing poses a threat. That being said, the concepts of prime numbers and factoring are much easier to grasp than elliptic curves.

How Encryption Works

Data is sent to your public address. The person sending that data will encrypt the data against your public key. Your public address is the hash of your private key and is basically just a shortened, public, and more convenient version of your public key.

This data can now only be opened by your private key. This level of cryptography is well-understood, but how does it work?

Your public key is basically the product of two very large prime numbers. Your private key contains the two prime numbers that were used to create your public key. Extremely large prime numbers are used.

We will use a relatively small prime number to demonstrate this. We know 13 and 17 are both prime numbers. To multiply them together is easy. But if I asked you to find the prime factors of 221, it would take you a little bit. The only way to do it is to check one by one which prime numbers go into 221 and find the correct pair. Do this with prime numbers that have an enormous number of digits and factors, and you find yourself with a near impossible task.

Cracking current private keys would take modern computers more time to crack than is feasible in a single generation and that is an understatement. Blockchain uses asymmetric security encryption which is hard to crack. They do this by enveloping data inside of computationally difficult math problems. It’s a lot of backwards math, that is difficult for our computers to handle.

That is, until Quantum came along.

Quantum Computing Explained

Traditional computers use bits. Everything is stored as a 1 or 0 or, in other words, as true or false. This happens through teenie tiny switches called logic gates that are basically “on” or “off”.

This binary system means that, when a computer is searching for prime factors or random points on an elliptic curve, it will go through and test each option one by one. This makes certain computations heavily intensive.

Quantum computing replaces bits with qubits. These give quantum computers exponentially improved abilities to do certain mathematical calculations. Qubits have the ability to be in both states (0 or 1, true or false) at the same time. This may sound confusing, but don’t try to rationalize it in your head. Understanding the superposition and interference of qubits is a daunting task for even some of the hardest working physicists out there. But not all hope is lost. Here’s what you need to know:

Qubits will allow computers to use more efficient methods to solve certain computational problems. Shor’s algorithm will allow quantum computing to use far more effective routes when solving these cryptographic challenges. These types of calculations can take several years for a traditional computer to process. A quantum-based computer could optimize its efficiency and solve the same level of complexity in a fraction of the time. This would allow one to crack the private keys on most blockchains quickly and efficiently.

However, Quantum is still far from reaching a point where it poses an immediate threat to blockchain.

The Future of Quantum and Blockchain

It’s not that easy to make a quantum computer. Qubits are highly sensitive and can only properly be used in very specific conditions. Among others, Qubits have to be stored at a temperature extremely close to absolute zero.

To make things worse, the more Qubits you add, the harder it is to maintain the system. As of now, the best thing we have is IBM’s recent 50 Qubit computer. So how many qubits will we need in a computer to defeat encryption?

Estimates show that ECC is actually faced with a more immediate threat than RSA encryption.

Cracking a 224 length ECC key would require 1300 qubits from a quantum computer. The rough RSA equivalent 2048 length key would require about 4096 qubits.

This means that ECC will be one of the first cryptographic schemes to get hit by quantum. RSA however, will likely not be too far behind when you consider the growth rate of this technology.

But blockchain is not doomed. Ethereum, for example, is well underway on their efforts to countermeasure the threat posed by quantum. Quantum resistant keys are already being developed. Short-term solutions, like using quantum to generate truly random numbers within cryptography, are also being looked at. The technical community is well aware of the threat that quantum poses and they are handling it.

So although Quantum may eventually pose a threat to blockchain in the future, it’s not an imminent threat nor one that will come as a surprise. It’s a threat that can be overcome and is being worked on now. At MIMIR, we believe in the developer community for blockchain. And so long as the success of a platform is determined by its developers, we think it’s safe to assume that blockchain is and will remain in good hands.

One year ago, Vitalik, founder of Ethereum, said this: “Ethereum is also going to be optionally quantum-proof with EIP 86 and Casper, because it will support any signature algorithm that the user wants to use.” Blockchain technology is in its infancy and will continue to evolve. For this reason, quantum will not be the end of blockchain.

DISCLAIMER: The content provided on this site is opinion and commentary on topics related to the blockchain universe. IT IS NOT INTENDED TO BE NOR SHOULD IT BE RELIED ON BY YOU FOR ANY REASON AND IS PROVIDED “AS IS” WITH NO WARRANTIES OF ANY KIND. You are responsible for your own decisions and for properly analyzing and verifying any content.

MIMIR Blockchain Publication

News, education and thought leadership from an exciting…