Is Quantum Computing an Existential Threat to Blockchain Technology?

Amid steep gains in value and wild headlines, it’s easy to forget cryptocurrencies and blockchain aren’t yet mainstream. Even so, fans of the technology believe blockchain has too much potential not to have a major sustained impact in the future.

But as is usually the case when pondering what’s ahead, nothing is certain.

When considering existential threats to blockchain and cryptocurrencies, people generally focus on increased regulation. And this makes sense. In the medium term, greater regulation may stand in the way of cryptocurrencies and wider mainstream adoption. However, there might be a bigger threat further out on the horizon.

Much of blockchain’s allure arises from its security benefits. The tech allows a ledger of transactions to be distributed between a large network of computers. No single user can break into and change the ledger. This makes it both public and secure.

But combined with another emerging (and much hyped) technology, quantum computing, blockchain’s seemingly immutable ledgers would be under threat.

Like blockchain, quantum computing has been making progress and headlines too.

The number of quantum computing companies and researchers continues to grow. And while there is a lot of focus on hardware, many are looking into the software as well.

Cryptography is a commonly debated topic because quantum computing poses a threat to traditional forms of computer security, most notably public key cryptography, which undergirds most online communications and most current blockchain technology.

But first, how does computer security work today?

Public key cryptography uses a pair of keys to encrypt information: a public key which can be shared widely and a private key known only to the key’s owner. Anyone can encrypt a message using the intended receiver’s public key, but only the receiver can decrypt the message using her private key. The more difficult it is to determine a private key from its corresponding public key, the more secure the system.

The best public key cryptography systems link public and private keys using the factors of a number that is the product of two incredibly large prime numbers. To determine the private key from the public key alone, one would have to figure out the factors of this product of primes. Even if a classical computer tested a trillion keys a second, it would take up to 785 million times longer than the roughly 14 billion years the universe has existed so far due to the size of the prime numbers in question.

If processing power were to greatly increase, however, then it might become possible for an entity exercising such computing power to generate a private key from the corresponding public key. If actors could generate private keys from corresponding public keys, then even the strongest forms of traditional public key cryptography would be vulnerable.

This is where quantum computing comes in. Quantum computing relies on quantum physics and has more potential power than any traditional form of computing.

Quantum computing takes advantage of quantum bits or “qubits” that can exist in any superposition of values between 0 and 1 and can therefore process much more information than just 0 or 1, which is the limit of classical computing systems.

The capacity to compute using qubits renders quantum computers many orders of magnitude faster than classical computers. Google showed a D-Wave quantum annealing computer could be 100 million times faster than classical computers at certain specialized tasks. And Google and IBM are working on their own quantum computers.

Further, although there are but a handful of quantum computing algorithms, one of the most famous ones, Shor’s algorithm, allows for the quick factoring of large primes. Therefore, a working quantum computer could, in theory, break today’s public key cryptography.

Quantum computers capable of speedy number factoring are not here yet. However, if quantum computing continues to progress, it will get there eventually. And when it does, this advance will pose an existential threat to public key cryptography, and the blockchain technology that relies on it, including Bitcoin, will be vulnerable to hacking.

So, is blockchain security therefore impossible in a post-quantum world? Will the advent of quantum computing render blockchain technology obsolete?

Maybe, but not if we can develop a solution first.

The NSA announced in 2015 that it was moving to implement quantum-resistant cryptographic systems. Cryptographers are working on quantum-resistant cryptography, and there are already blockchain projects implementing quantum-resistant cryptography. The Quantum Resistant Ledger team, for example, is working on building such a blockchain right now.

What makes quantum-resistant or “post-quantum” cryptography, quantum resistant? When private keys are generated from public keys in ways that are much more mathematically complex than traditional prime factorization.

The Quantum Resistant Ledger team is working to implement hash-based cryptography, a form of post-quantum cryptography. In hash-based cryptography, private keys are generated from public keys using complex hash-based cryptographic structures, rather than prime number factorization. The connection between the public and private key pair is therefore much more complex than in traditional public key cryptography and would be much less vulnerable to a quantum computer running Shor’s algorithm.

These post-quantum cryptographic schemes do not need to run on quantum computers. The Quantum Resistant Ledger is a blockchain project already working to implement post-quantum cryptography. It remains to be seen how successful the effort and others like it will prove when full-scale quantum computing becomes a practical reality.

To be clear, quantum computing threatens all computer security systems that rely on public key cryptography, not just blockchain. All security systems, including blockchain systems, need to consider post-quantum cryptography to maintain data security for their systems. But the easiest and most efficient route may be to replace traditional systems with blockchain systems that implement quantum-resistant cryptography.