[This is part of a continuing series on quantum computing. For the first part, click here.]
Once people understand the threat that quantum computers pose to classical cryptographic algorithms like RSA and ECC, the next question that always gets asked is: when is it likely that such a computer will be available? This was one of the key questions that drove the creation of the ANSI X9 Quantum Risk Study Group. The study group’s report does not include an explicit answer to the question, though there are many, including NIST, highlighting that such a computer could be available in the next decade or so. This article will give some background and explain the challenges involved in trying to determine exactly when a cryptographically relevant quantum computer will be available. The short answer is: it could be sooner or later than we think, but we can’t take a chance on it being later.
Qubits and Shor’s algorithm
Current quantum computers are built out of small numbers of qubits that are relatively unstable. These computers pose no threat to classical cryptographic techniques, no matter how long they run. Still, they are a huge leap forward to the state of the art not so long ago — when quantum computers didn’t exist at all. A cryptographically relevant quantum computer is one that is capable of using Shor’s algorithm to break RSA with 2048-bit keys, or ECC with 224-bit keys, the minimum keys sizes used to protect information today.
Because of how Shor’s algorithm works, this requires several thousand qubits. However, not all qubits are created equal. Qubits have a natural tendency to interact with their environment and change state. This happens faster for some qubit technologies than for others. Errors may also be introduced as qubits interact with each other as part of individual computations (referred to as “quantum gates”). Again, the error rate depends on exactly how the quantum computer is implemented. It is extremely unlikely that a first-generation quantum computer with thousands of qubits will have the qubit stability necessary to threaten ECC. Therefore, simply extrapolating qubit numbers doesn’t work.
Instead, early quantum computers will need to make use of error correction to run Shor’s algorithm. Error correction allows multiple physical qubits to be combined into a single “logical” qubit. Exactly how many qubits are required depends on the quality of the underlying qubits. This makes it very challenging to track progress in the field, as numbers of qubits are commonly reported, but the qubit error rates are often not. When comparing two quantum computers, it is important to make sure it is an apples to apples comparison, i.e. that the stability of the qubits is taken into account, and not just the number of qubits.
Moore’s Law and current economics of quantum computing
Several analyses have attempted to determine whether there will be a Moore’s Law for qubits that can predict when a cryptographically relevant quantum computer will be available. While this may eventually work, there are a number of challenges with these sorts of analyses. As mentioned above, numbers of qubits cannot be compared unless they are the same quality. And the quality of future qubits is likely to be better than the present quality. So drawing a one dimensional graph is not very helpful. A second problem is that quantum computers with non-trivial numbers of qubits are a recent development, so there are very few data points as to how quickly quantum computers are getting better. Extrapolating from a handful of data points is always dangerous. Also, as pointed out in a report by the National Academy of Sciences, Moore’s Law is really more of an economic consequence than a technical one. Faster, more powerful computer chips allow computers to be used for new things, which causes revenue to increase, driving further investment in faster, more powerful computer chips. And while lots of investments are currently being made in developing quantum computers, how useful they turn out to be for solving non-cryptographic problems may significantly impact future research funding. Quantum computer revenue growth is difficult to forecast at this point, as we await the introduction of the first commercially viable quantum computers. Still, economic models are rarely linear and one breakthrough would lead to a rush of investment and innovation.
Assessing technical progress with building cryptographically relevant quantum computers
Of course, the technical difficulty of building a quantum computer is relevant as well. Even if we have a rough idea of how many qubits of a given quality are required to threaten cryptographic algorithms, it may be very difficult to predict when a quantum computer of a given size will be feasible. This is because a variety of different methods are still being investigated for constructing qubits. It’s not known yet publicly whether the technology that will be used to build the first cryptographically relevant quantum computer exists. What technology ends up being used may end up having a huge impact on how quickly quantum computers scale, once they are available.
If the technology is significantly similar to methods that are currently used to build integrated circuits, then we have an extensive body of experience to draw on in how to rapidly construct relatively large-scale systems, and cryptographically relevant quantum computers may appear pretty soon after the development of stable qubit technology. On the other hand, if the qubit technology is less similar or scales poorly, then it may take a longer time for quantum computers to grow larger.
Will the industry be prepared when quantum computers break current algorithms?
A related question, which we have much more experience with, is how long it takes to replace cryptographic algorithms. Historically, these transitions have taken decades. There are still a few places in financial systems where the original Data Encryption Standard is being used. Transitions from RSA-1024 to RSA-2048, SHA-1 to SHA-256, and early SSL/TLS to TLS 1.2 have similarly taken a very long time and are still ongoing. As with other crypto transitions, PQC is likely to take time and not be as simple as a simple drop-in replacement for compromised algorithms when we discover the need. The effort needs to begin much sooner. Sadly, it is likely that vulnerable algorithms will still be in use by the time quantum computers arrive.
So what can be done today, what technologies are available to address the threat from quantum computing, and how can organizations start planning for the coming post-quantum transition now? That will be the subject of the next “DigiCert on Quantum” update.