Nicolas Portmann

Software Engineering Security Engineering Applied Cryptography Performance Optimization

Quantifying the Quantum Threat

2022/04/09 Nicolas Portmann pqc

Quantum computers are no longer an abstract idea as they were when Peter Shor developed his efficient quantum algorithms for discrete logarithms and factoring [S94] in 1994. And while there is still a lot of progress to be made until the quantum computers developed by IBM, Google, and the likes are practically useful. We should, nevertheless, consider the implications of large-scale quantum computers while we still have time to react. Like Peter Shor developed his quantum algorithms before physicists at Oxford University built the first 2-qubit computer in 1998, we should have our strategy for coping with large-scale quantum computers before they pose an actual threat.

One of the most frequently asked questions about quantum computers is "How big is the threat to classical cryptography posed by quantum computers?". Unless an unknown player secretly developed a quantum computer far ahead of the R&D departments of billion-dollar companies such as Google, the answer is unsurprising that there is currently no threat at all. However, if we look into the future, things aren't as clear-cut.

Mosca Theorem xx: time that products and data must remain secure
yy: time it takes to migrate to post-quantum cryptography
zz: time it takes until cryptographically-relevant quantum computers will be available

In his theorem [M15] illustrated above, Dr. Michele Mosca pointed out that if x+y>zx + y > z, you should be worried. As cryptographers, we can do nothing to impact zz; cryptographically-relevant quantum computers will become available, and we can do nothing about it. xx is also out of our control for the most part. Some information just has to remain secure for a relatively long time. Even if you decide to skip reading the following more technical remainder of this post, know that the only thing we can affect is yy. Acting now to make our organizations and systems crypto-agile is the best thing to focus on to prepare our systems for quantum adversaries.

crypto agility is not as much about using protocols that support various cryptographic algorithms and key lengths. It is about being able to make and execute the decision to swap protocols or primitives in a live system. This is just as much an organizational challenge as it is an engineering one.

The Metrics

To quantify the threat posed by quantum algorithms, we need metrics to measure and compare their efficiency. Its requirements in space and time typically define the performance of an algorithm. On traditional hardware, we usually compare the memory consumption and the runtime of algorithms. Terminology aside, not a lot changes when analyzing quantum algorithms. The metrics we use to compare the efficiency and space-time tradeoffs of quantum algorithms are the number of logical qubits (space complexity, also referred to as the width of a quantum circuit) and the gate depth (time complexity, best measured in the number of sequential Toffoli gates) [KHJ18] required to execute the algorithm.

Logical vs. Physical Qubits

Manufacturers of quantum computers like to advertise with big numbers. The latest IBM quantum computer packs 127 qubits [IBM21]. They are, however, prone to error and not directly useful in the business of breaking cryptographic algorithms. To satisfy quantum algorithms, we need clean, error-corrected "logical qubits". Many physical qubits can be arranged to encode one logical qubit [ED+21]. Recent estimates indicate that 20 million physical [GE19] (or 4096 logical [HRS17]) qubits are required to break RSA-2048. A quantum algorithm's requirements in space are measured in logical qubits, while quantum computer marketing material usually refers to physical qubits.

Gate depth

Quantum gates are the building blocks of quantum algorithms. Taking the total number of gates as the measurement for the time complexity would not be accurate, as each kind of gate introduces a different overhead to the total runtime. The runtime is therefore often expressed by the number of Toffoli gates in the circuit because [KHJ18]

  1. all quantum mechanically allowed computations can be implemented by Toffoli (and single) gates.
  2. circuits based on Clifford gates don't provide an advantage over classical computing. Toffoli gates are non-Clifford gates and are essential in delivering a quantum benefit.
  3. logical Toffoli gates are expected to be the primary source of time bottlenecks in real applications.

The Quantum Impact on Classical Cryptography

The quantum algorithms we know today impact different areas of classical (pre-quantum) cryptography differently. As we will see later, asymmetric cryptography based on the factorization of integers (e.g., RSA) or the discrete logarithm problem (e.g., ECDH) is impacted most. Symmetric cryptography (e.g., AES) is also impacted but to a far lesser degree.

RSA

Shor's algorithm for factoring integers [S94] is the primary cause of concern for asymmetric cryptography schemes such as RSA [RSA78]. The security of RSA is based on the fact that it is infeasible to infer the private key from the public key. The public key contains the modulus nn and the exponent ee. Factoring the prime factors (pp and qq) of nn - which is not computationally feasible on classical hardware - allows for a full recreation of the private key dd. The following table lists the space and time requirements to break different key lengths (security levels) of RSA.

Note that the T-Depth in the table below is merely an estimate as no exact numbers are provided in the paper quoted below. The estimate is provided based on the given order of the total gate count O(n3logn)O(n^3 log n)

Algorithm Security Strength # qubits T-Depth (roughly!)
RSA-2048 112112 40964096 8.581098.58 * 10^9
RSA-3072 128128 61446144 6.8710106.87 * 10^{10}
RSA-15360 256256 3072030720 3.6210123.62 * 10^{12}

Source: [HRS17]

ECC

An elliptic curve private key is a random number in the range of 1..n11 .. n-1, where nn is the order of the group of point GG. The public key QQ is a point defined as Q=GkQ = G*k. The elliptic curve discrete logarithm problem (ECDLP [HL15]) is the computationally hard problem of determining kk given the points QQ and GG. Using Shor's discrete logarithm quantum algorithm [S94], the ECDLP becomes computationally feasible under the requirements listed in the table below.

Note that the requirements for breaking RSA keys of equivalent security strength to ECC keys are roughly equal in time but more complex in space.

Algorithm Security Strength # qubits T-Depth
ECC-256 128128 23302330 1.1610111.16 * 10^{11}
ECC-384 192192 34843484 4.1510114.15 * 10^{11}
ECC-521 256256 47194719 1.0510121.05 * 10^{12}

Source: [RN+17]

AES

Grover's algorithm [G97] can be used in known-plaintext attacks [JN+19] that take a reversible quantum implementation of the AES [NIST2001] cipher as well as some plaintext/ciphertext pairs and will search for the corresponding key. Multiple (2 or 3) plaintext/ciphertext pairs are required to ensure Grover finds the correct key. All requirements to break AES at different security levels are listed below.

Algorithm Security Strength # qubits T-Depth # PT/CT pairs
AES-128 128128 33293329 1.7410211.74 * 10^{21} 22
AES-192 192192 39693969 7.4510307.45 * 10^{30} 22
AES-256 256256 69136913 3.3710403.37 * 10^{40} 33

Source: [JN+19]

Various proposals have been made to improve the security of symmetric algorithms against quantum adversaries [GT12], [BUK19], but none of them have been considered for standardization. It appears as if Grover's algorithm cannot be improved upon or parallelized to achieve significantly better results than presented above [Z08]. There may, however, be entirely different attack vectors against symmetric cryptography outside of Grover's algorithm [BSS21], [HHL09].

Estimates by Experts

A more subjective quantification of the quantum threat can be found in the 2021 Quantum Threat Timeline Report from the Global Risk Institute [MP22]. 46 Experts estimated the likelihood that quantum computers will be able to break RSA-2048 in 24h in different time frames.

Survey by Dr. Mosca and Dr. Piani

Source: [MP22]

The majority of experts questioned estimate a likelihood of 50%, or above that in 15 years from now, a quantum computer will be able to break RSA-2048 in 24 hours.

Conclusion

On the one hand, it will probably take us years until we see the first quantum computer with a cryptographically relevant number of clean, logical qubits (> 4000). Even once this milestone is reached, it may still be infeasible at first to run quantum algorithms with a depth of trillions of Toffoli gates as required to break RSA or ECDH in a reasonable amount of time.

On the other hand, we have to expect the capabilities of quantum computers to grow at an exponential rate, following a quantum equivalent to Moore's law [DS13]. Additionally, we must assume that our most sensitive information communicated today will be stored now and decrypted later - once quantum attacks on current classical cryptography become feasible. We should also consider that it takes certain industries years to develop and adopt new standards. This leaves us with an immediate need for action to protect our data with long-term security requirements [BSI20], [ANSSI22].

The key points to remember are:

  • Quantum computers will break asymmetric cryptography based on factorization or the discrete logarithm problem in polynomial time.
  • Symmetric cryptography is relatively safe against quantum computers. Doubling the key length (e.g., from AES-128 to AES-256) for long-term keys is currently sufficient.
  • Delaying the adoption of quantum-secure cryptography is risky due to "harvest now, decrypt later" attacks.
  • Standardization of post-quantum cryptography is still ongoing, and the maturity level of the candidates for standardization should not be overestimated [ANSSI22].