How quantum computing will break blockchain — and what to do about it
by Andrei Povarov
We've all heard about quantum computers and the threat they represent to blockchain security. However the common belief is that quantum computers do not exist beyond lab prototypes, making the threat rather hypothetical.
The truth is that quantum computers not only exist, but they also are available commercially. Today anyone can easily access a quantum computer in the public cloud and do programming experiments, including the RSA cryptosystem-breaking Shor's algorithm — although no one has yet reached the full power to crack existing blockchain applications.
IBM's quantum computer available in the cloud, IBM Q, has already acquired a community of more than 60,000 users, who have already run more than 1.7 million quantum computing experiments.
And while the first publicly available IBM Q system had the modest power of only 5 qubits, last year it was upgraded to 17 and then 20 qubits, And, in a recent announcement IBM said it had successfully developed a processor prototype with the power of 50 qubits.
Another provider, D-Wave, which sells commercial quantum computers to NASA, Google, and Lockheed Martin, declared many more qubits in the chip (a recent announcement specified a prototype with as many as 2,000 qubits).
However this is a different count, as D-Wave systems use a principle called annealing, or adiabatic quantum computing, to deal with a certain class of optimization problems — as well as lately with machine learning and artificial intelligence. D-Wave quantum computers are not yet well known, as opposed to IBM Q.
Will these developments lead to the imminent death of today's blockchain, banking and internet security as we know it? Yes. And this moment is coming closer and closer, given the pace of progress.
So what is so special about quantum computers? As opposite to computers that operate with traditional units of information — bits with a value of 0 or 1 — quantum computers work with qubits (i.e., quantum bits), which have values of 0 and 1 simultaneously, a feature called superposition.
The unusual nature of qubits creates some interesting effects and can be used to solve traditionally hard-to-crack tasks in a fast, easy and elegant way. A simple analogy would be the task of finding an exit in a huge maze.
The traditional way to do this would be to check all possible routes one by one, which could take an extremely long time. If instead, you send out an army of investigators, each with a different path to check, you will find the exit much, much faster.
Similarly, instead of trying to find a secret key by exploring different combinations one after another on a traditional computer (prohibitively impractical) one can simply use a quantum computer to tackle all possible combinations at the same time.
How many qubits are needed to check a certain number of combinations? Each qubit being 0 and 1 simultaneously, the combination of N qubits will represent 2N options existing simultaneously. Thus increasing number of qubits means exponentially increasing power — IBM's move from 20 to 50 qubits in fact means a tremendous increase in capacity.
It is not yet enough to crack bitcoin; the necessary qubit number to compromise private keys is estimated to be around 1,500. But how soon could we get there? What can be done to prevent the quantum threat? And what strategy should your company pursue, considering this global uncertainty?
Andreas Antonopoulos has presented Interesting arguments that if there were quantum computers capable of breaking today's RSA cryptography, their owners wouldn't disclose their existence by using them to steal bitcoin, a rather a negligible target compared with far more serious financial, military, nuclear assets.
Antonopoulos likens this to the British who, having cracked the Enigma code during World War II, still allowed cities such as Coventry to be bombed to disguise the fact that they were in possession of the Enigma decryption techniques.
However, this argument might not be such good news after all, since the theft of cryptocurrencies can be carried out gradually (as in the Mt Gox case), and without anyone realizing that wallets were being cracked by a quantum computer and not by unknown hackers who obtained private keys in ordinary ways.
Finally there could be individuals within these powerful quantum organizations who could act on their own to crack public blockchains for the sake of personal profit — like the FBI agent who stole approximately 1,600 bitcoins while investigation the Silk Road case.
More optimistic (at least for cryptocurrencies) is the fact that cryptographic methods are normally upgradable by design without major rebuilding. With the introduction of new quantum-resistant algorithms, they could be upgraded for superior security— hopefully, before it's too late.
Such algorithms do exist and are already being developed, including symmetric cryptography in which quantum computing using the Grover algorithm can only insignificantly speed up the process — as opposed to the dramatic quantum gain on asymmetric schemes using Shor's algorithm.
By the way, bitcoin employs both cryptographic schemes, which means that wallets (private keys and asymmetric cryptography) would be easy to crack through quantum computing, but mining operations (SHA-256 and symmetric schemes) would remain relatively safe.
Research is also ongoing for asymmetric schemes. Interesting directions here include lattice-based, code-based and multivariate cryptosystems, among others — some of which have been under discussion for the past few years.
So, should the strategy be simply to wait or to hurry up and upgrade to a new and yet unproven cryptography? Some recent studies estimate that it will take 10 years to attain the power to break Bitcoin security. But we really don't know what will happen.
This brings up the classic innovator's dilemma when embracing emerging technologies: Moving too early could mean risky investments into a solution that ultimately might not be adopted; acting too late could mean exposing critical assets currently protected by a blockchain.
The blockchain industry should start managing this strategic uncertainty now, on the eve of the inevitable arrival of full-power quantum computers.