How long before quantum computers break encryption?

The verdict is in: quantum computing poses an existential threat to asymmetric cryptography algorithms like RSA and ECC that underpin practically all current Internet security. This comes straight from the National Academy of Science’s Committee on Technical Assessment of the Feasibility and Implications of Quantum Computing. The inevitable follow-up: OK, so how much time do we have before we’re living in a post-quantum world?

The short answer is, nobody knows. That’s not for lack of trying. The American National Standards Institute (ANSI) formed a dedicated working group just to try to reach a number. The industry’s best guess is about a decade, maybe more, maybe less. Not exactly what you want to hear if you’re trying figure out how to replace the encryption schemes used for everything from email to the world’s banking systems.

Why can’t we get a more concrete timeline? Because the factors influencing the evolution of quantum computers are notoriously complex and hard to measure.

Numbers don’t tell the whole story

We know that a quantum computer using Shor’s algorithm will require several thousand qubits (the fundamental quantum computing unit representing either 1 or 0) to break RSA or ECC. But that doesn’t necessarily mean the first quantum computers to hit that number will actually be able to crack encryption. Not all qubits are created equal. They inevitably interact with their environment and change state—introducing errors—and some qubit technologies do this faster than others.

The first generation of quantum computers capable of supporting thousands of qubits is unlikely to be stable enough to be cryptographically relevant. So how quickly will qubit quality improve? It’s hard to say. While researchers are quick to publish the number of qubits each new system evolution can support, they rarely share error rates, making it tough to track progress in the field.

Error correction matters

Along the same lines, researchers are working on error correction strategies to help address qubit instability. Here, multiple physical qubits would be combined into a single “logical” qubit, much like in classical error correction. However, the overhead for quantum error correcting codes is much larger; there’s a reason researchers still haven’t produced a single logical qubit. Even assuming we do clear that hurdle (and significant progress is being made), the number of qubits required for error correction will still depend on the quality of the underlying qubits.

Technical questions remain

Another open question in quantum computing: we still don’t know the best way to construct qubits. Researchers are exploring a number of approaches, and it’s possible the technology to build a system with a cryptographically relevant number of stable qubits doesn’t even exist yet. Which technology is ultimately adopted will have a big impact on how quickly quantum computers scale.

If the technology follows the same general path as conventional computing, then the timeline from the first stable qubits to full-scale cryptographically relevant systems could be quite short. But it’s also possible that the technology required for stable qubits scales poorly, or just behaves unlike anything we’ve seen. We have no way to estimate the quality of future qubits compared to present ones or predict the rate of improvement. After all, quantum computers with nontrivial numbers of qubits are a recent development, so there are very few data points to extrapolate from.

Moore’s Law does not apply

It’s tempting to imagine an analog to Moore’s Law for qubits that would help us predict when cryptographically relevant quantum computers will emerge. Unfortunately, we’re unlikely to find one. As discussed, progress toward cryptographic relevancy depends on both the number and quality of qubits, so a one-dimensional graph isn’t helpful. More significantly though, as the National Academy of Sciences notes, Moore’s Law expresses economic consequences as much as technical ones.

Conventional computer chips follow a virtuous circle, where faster chips lead to new applications, which leads to more revenues, which leads to more investment in faster chips. Will the same apply to quantum computers? Maybe, but we can’t assume so. Whether quantum computers will be useful for much of anything beyond a few specific types of algorithms is still an open question in the field.

It’s time to get started

Whether cryptographically relevant quantum computers emerge five, 10, or 15 years from now is almost beside the point. Bottom line, we need to start preparing now. Judging from past cryptographic evolutions (such as the shift from RSA 1024 to RSA 2048, or from SHA-1 to SHA-256), these transitions can take years, even decades.

If you’re developing any system that relies on cryptography, you should be taking concrete steps now to prepare for the post-quantum future. Double key sizes. Embrace hash-based signatures. Build systems that employ multiple crypto algorithms simultaneously. And make sure your infrastructure uses automated, flexible PKI solutions.

Comments are closed.