RSA and Diffie-Hellman Cryptosystems

In the Cybersecurity and Cryptography industry, especially in digital communications, some of the most common forms of encryption, such as asymmetric encryption, relies on the inability to quickly solve difficult math problems with classical computers. However, one of these problems, integer factoring, can be solved efficiently with a quantum computer using Shor’s algorithm, which was proposed in 1994 [1]. Integer factoring is the core mathematical problem for the most widely used algorithm today in the cryptographic world: RSA and Diffie-Hellman. These can be found anywhere from instant messaging applications, email, FTP, HTTPS, credit card PoS or even IoT device communication. Therefore, this could pose a huge geopolitical and corporate threat. The two main proposed solutions to solve this problem are Quantum Key Distribution based systems, that require a massive change of infrastructure, and post-quantum cryptography (PQC) standards, which are a change or upgrade on our classical cryptographic systems and can in principle live with our current infrastructure. Both are active fields of research, and there are already several proposals by NIST (National Institute of Standards and Technology), and an NSA proposed timeline since 2022.

Many companies are aware they must design a PQC strategy today, in order to secure their digital infrastructure for the era of quantum computing. What is the timeline for implementing PQC? The resources needed to run Shor’s algorithm is well beyond the capabilities of today’s NISQ devices; therefore, this is not an immediate threat. There are also other factors to consider when designing the PQC strategy, such as how long information is sensitive, or how other forms of encryption may be exposed by quantum computing.

However, a new research paper published in December 2022 proposes a new way of factoring integers that could reduce drastically that timeline and create a higher urgency in the PQC strategies. In this study we evaluate said paper and the implications for the financial industry.

Is classical asymmetric encryption at imminent risk by Quantum Computers?

Factoring integers with sublinear resources on a superconducting quantum processor

A recent publication [2] announced a universal hybrid quantum-classical algorithm for factoring large integers, raising further concerns about the security of RSA. One of the main findings is that the algorithm can potentially factor RSA integers of 2048 bit lengths equipped with a quantum computer of 372 physical qubits and circuit depth of a thousand gates. The number of qubits of this algorithm scales sub-linearly in the bit length of the integer (e.g., only 10/372 qubits for 48-bit/2048-bit numbers), providing one of the most efficient qubit-encoding schemes up to date for factoring. In contrast to the millions of physical qubits and high circuit depths that Shor’s algorithm imposes, far beyond today’s current hardware capabilities. Current noisy quantum computers are projected to have such quantum volumes in the near term. For example, IBM’s roadmap expects to deliver thousands of physical qubits by 2024 [3].

The quantum threat timeline dictates the transition to quantum-safe cryptography. The migration to PQC is a challenge in itself and will require time. If the paper’s main hypotheses hold true, timelines can potentially be shortened by many years. Under these assumptions, the PQC migration strategy would become a crisis management process under tight deadlines. Notice that estimates of the likelihood of Shor’s algorithm breaking RSA-2048 by 2030 remain around 50% [8] given the expectation of a cryptographical-relevant quantum computer.

However, our preliminary analysis indicates that proof of the runtime/convergence of the algorithm is quite vague, which is really the only possible way to challenge the hardness assumption in RSA cryptosystems. One of the study conclusions states: “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA”. The paper also states that results are presented for an ideal basic situation, “QAOA usually works more than one layer and deeper circuit required. Besides, the quantum speedup is unknown, it is still a long way to break RSA quantumly.” The Quantum Approximate Optimization Algorithm (QAOA) is a gate-based optimization solver that variationally updates a parametrized quantum circuit that mimics adiabatic evolution of analog quantum computing (AQC). To improve the performance of QAOA, in theory, we would need to increase circuit depth. However, this results in errors being accumulated, risking counteracting the bonus of the computation. In order to obtain QAOA’s best performance, a balance of the computation bonus and the effect of noise is needed. The analytical complexity of QAOA remains an open question.

The efficiency of the variational methods is largely determined by the computational expense of minimizing a given cost function, which can often be non-trivial, optimization runs can take up days for even a single iteration if the number of circuit measurements and shots is high.

Methods that reduce the factoring problem to combinatorial optimization are not new, on superconducting and special purpose hardware such quantum annealers. Zapata et al. [4,5] published a study about a Variational Quantum Factoring (VQF) method. Considering that factoring requires a single correct answer and approximations are merely random guesses for the integer’s factors, although the success of the algorithm can be quickly verified, by just multiplying the proposed factors.

Scott Aaronson reasoned in his blog [6] that variational algorithms will be roundly outperformed even by classical algorithms that do exploit structure, like the Number Field Sieve [10]. Michele Mosca et al. [7,8] found no evidence that these types of quantum variational solvers would be a viable path for factoring large integers, even for large scale quantum computers. Moreover, how do classical optimizers perform on this type of combinatorial optimization problems? Numerical results should incorporate such estimates.

The algorithm presented in the paper relies on a recent factoring paper by Peter Schnorr’s [11] lattice-based factoring method (not to be confused with Peter Shor’s algorithm) which works well with small keys but falls apart at larger size [12]. The lattice problem must be set up in many more dimensions which raises the following questions – Given this paper depends on Schnorr technique that was not shown to properly scale, is there a claim it gets around this limitation? Would the QAOA/variational based approach in this paper solve the mathematical problems built upon the high dimensional lattices needed for big RSA numbers in a reasonable amount of time? The most straightforward way to validate it is to actually implement it, the ultimate substantiated proof in the cryptographic world. By reducing the number of quantum resources and relying on variational algorithms tackling NP-hard problems, strong guarantees of Shor’s super-polynomial speedup over the best classical factoring methods are lost. There is definitely a trade off between both. Nonetheless, public key infrastructure (PKI) stakeholders and cryptographers should monitor the empirical progress of these approaches and implementation of PQC mitigation plans should remain on a steady track as new quantum algorithms arise in the literature.

In our study we show how this research paper further paves the way for large integer factoring of realistic cryptographic significance and while it is not sufficient, nevertheless improves existing algorithms. There is no guarantee this novel algorithm can shorten the proposed timelines; however, our recommendation is to follow NSA / NIST guidelines and start preparing a PQC strategy immediately by creating a cryptographic key inventory.

Are the RSA and Diffie-Hellman cryptosystems under threat sooner than previously thought?

Is classical asymmetric encryption at imminent risk by Quantum Computers?

Further Reading