When Should We Prepare for Quantum Computers to Break Cryptography?
Now that we have described quantum computing and how quantum computers could break the cryptography underlying many blockchains, we must assess how soon the blockchain community should worry about this threat. Is quantum computing science fiction, or science fact?
By The Praxxis Team, October 10, 2019.
This post is part of a series on quantum computing. To make sure you don’t miss a post from Praxxis, download the xx collective app to receive updates on your smartphone.
Now that we have described quantum computing, and how quantum computers could break the cryptography underlying many blockchains, a critical question emerges: how soon should the blockchain community worry about this threat? Are we in imminent danger of quantum-capable adversaries breaking blockchains and stealing cryptocurrency, or is quantum computing still more science fiction than science fact?
To address these questions, we should look to the current state of the art. Building on our understanding of quantum computing , we can identify the two barriers standing in the way of progress: the challenge of scaling up quantum computers to thousands of qubits, and the challenge of getting all those qubits to work together. We can then assess how difficult it will be for each of these barriers to be overcome.
Assume Incomplete Information
The first step is to recognize that we will not be able to produce exact answers to these questions. In addition to the impossibility of predicting a scientific breakthrough that has not yet occurred, we must contend with the issue of secrecy. A fundamental lesson from the history of cryptanalysis is that achievements in this field are often hidden from public view. The World War II effort at Bletchley Park to break the German Enigma encryption devices was not declassified until the mid-1970s. In fact, much of the value that an adversary would gain from breaking a cryptographic system relies on keeping the news a secret.
Is it likely that secret research is underway in the field of quantum computing? Given the importance of cryptographic systems to governments, businesses, and financial systems, there are strong incentives for funding quantum computing research. For example, we know that the US government is currently investing $1.2 billion in quantum information science research, and private quantum computing startups have raised nearly half a billion dollars from venture capital in the past two years. We should not assume that the results of this research will be announced.
Barrier 1: Build a Computer With Thousands of Qubits
The first challenge is scaling up the number of qubits in a quantum computer. While Google’s recent achievement of quantum supremacy was accomplished with a 53-qubit device, using Shor’s algorithm to break the RSA cryptographic system would require a quantum computer with several thousand qubits. Every one of these qubits would need to be cooled to near-absolute zero, protected from energy interference, and connected via quantum entanglement with every other qubit.
How soon could quantum computers this powerful be developed? The progress of standard binary computers over the past 50 years has followed Moore’s Law: that every 18-24 months the number of transistors on a microchip doubles. If quantum computers advance at a similar rate, with qubits doubling every 18-24 months, a quantum computer capable of breaking cryptographic systems is roughly a decade away.
There are reasons to think this estimate may be too conservative. First, quantum computers with 2,000 qubits are already available for sale, and computers with up to 5,000 qubits have already been announced. Note that these are quantum annealing or adiabatic computers, which means that the qubits in these devices are only connected to a few of their neighbors, rather than part of a fully-entangled network of qubits. Second, when it comes to quantum computers, manufacturers can call upon 75 years of experience in binary computers, so dramatic gains in scale may be possible.
Barrier 2: Get All the Qubits to Work Well Together
The great potential of quantum computing is achieved by arranging all qubits in a state of entanglement with one another, so that a quantum computer with X qubits can be in a superposition of up to 2X states simultaneously. This superposition of a vast number of states is what allows a quantum computer to achieve unprecedented computational speed. To date, it has been difficult to increase the number of fully-entangled qubits, due to the challenges of decoherence and fault tolerance.
Quantum Decoherence. When a quantum particle such as a qubit is in a superposition of states, it is said to be quantum coherent. If a particle were perfectly isolated from outside forces, it would maintain coherence but be impossible to observe or manipulate, making it useless as a computer component. Yet when a particle is imperfectly isolated, it begins to lose coherence through interaction with the surrounding environment. In effect, the particle ceases to act in accordance with quantum mechanics, and starts acting in accordance with classical or Newtonian mechanics. This process is known as quantum decoherence.
For a quantum computer to perform valuable work, it must carefully balance this tradeoff between isolating qubits and interacting with them in a way that yields data. Compounding the difficulty is the fact that qubits must be made with particles small enough to be subject to quantum mechanics. These subatomic particles are extremely sensitive to outside forces and must be very precisely observed. Both these facts create opportunities for faults to occur in a quantum computer.
Quantum Fault Tolerance. In response to the difficulty of managing quantum decoherence, lots of effort has gone into developing ways to cope with both faults caused by outside interference and faults in observation or measurement. Many systems draw upon the distinction between “physical qubits,” physical components within a quantum computer, and “logical qubits,” a sometimes-theoretical construct capable of performing quantum operations. Some proposed systems use up to 10 physical qubits to perform the work of a single logical qubit, multiplying the size of a functional quantum computer.
This challenge may be less imposing than it seems, as fault tolerance and mitigation efforts are as old as computers themselves. When ENIAC, the world’s first general-purpose electronic computer, was unveiled in 1945, it used vacuum tubes as binary bits. The vacuum tubes were notoriously unreliable, frequently causing the entire computer to break down. These faults were greatly reduced with the introduction of the transistor a few years later. Similar breakthroughs may be in store for qubits.
Lastly, if achieving a fully-entangled system of qubits turns out to be impractical, it may not be necessary. Recent research indicates that a quantum computer with 20 million qubits only attached to their nearest neighbors could break 2048 bit RSA encryption in eight hours.
Warning: You Are Being Recorded
Given the unpredictability of scientific progress, and the likelihood of secrecy, forecasting exactly when quantum computers will break blockchain crypto is a fool’s errand. With that said, while the barriers to quantum computer development are difficult to overcome, there is no evidence that they are insurmountable. One day soon, a quantum computer capable of applying Shor’s algorithm to cryptography will be produced. The blockchain community would be foolish to ignore this threat until that day comes.
We live in an age of pervasive data monitoring and collection. By 2025, the world will store 175 zettabytes of data (that’s 175 trillion gigabytes). Public blockchains, by design, keep a publicly-accessible record of all transactions. Any data created today, protected by a system susceptible to quantum cryptanalysis, may be decrypted by a future quantum computer.
Is it reasonable to consider quantum cryptanalysis an inevitability, and implement quantum-resistant cryptography today? Perhaps it would be more reasonable to wait until the world’s largest and most powerful cryptographic institution takes this problem seriously. Once the US National Security Agency gets serious about quantum cryptanalysis, then the blockchain community should take action. One catch though: the NSA has already directed government agencies to halt work on quantum-susceptible cryptosystems more than four years ago .
The NSA is taking quantum computing seriously. So should we.