Published on September 30th, 2019 📆 | 6029 Views ⚑
0How 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.
Gloss