Understanding the Recent News of Quantum Attacks on Crypto

By: Roger A. Hallman and Shane Kosieradzki

1 Introduction

A late 2024 spate of articles in English language popular tech media (e.g., [18]) publicized what appeared to be a mortal blow to RSA cryptography, an asymmetric cryptographic protocol which underpins many information security schemes. These articles were reporting on a research paper, “Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage,” [19] which was published in the Chinese Journal of Computers in May, 2024. This paper purports to use quantum computing-based approaches to attack against RSA cryptography, factoring larger numbers than has previously been accomplished via quantum computing.

This article will examine the claims and results of this research paper, as well as the popular media reporting on the article to determine whether the air of cryptography’s impending doom was overblown. We will introduce the reader to RSA cryptography and quantum cryptanalysis in Section 2.1, then briefly describe quantum computing and its use in cryptanalysis in Section 2.2. Section 3 presents a more detailed examination of the paper’s results attacking the RSA algorithm, as well as providing prudent skepticism on the results and popular reporting of the Chinese paper in Section 3.1. Finally, closing remarks are given in Section 4.

2 Background

2.1 The RSA Cryptographic Protocols

The RSA cryptographic protocol [9] is one of the most widely used public key cryptosystems, used to securely transmit information over potentially untrusted networks. The security of the protocol is rooted in number theory and modular arithmetic, relying on the difficulty of factoring large numbers. Moreover, the protocol offers a digital signature capability to ensure the integrity and authenticity of transmitted data.

RSA key generation takes two large prime numbers p and q, and generates a modulus value n = p × q. Euler’s totient function ϕ(n) = (p − 1)(q − 1) is computed, then a public exponent e is calculated such that 1 < e < ϕ(n) and gcd(e, ϕ(n)) = 1, and a private exponent d is calculated such that d×e(modϕ(n)) = 1. The public key is the pair (e,n) and the private key, which remains secret, is d. A message m is encrypted to generate a ciphertext c = m^e(modn) and the original message is recovered by a decryption function m = c^d(modn). Messages can be digitally signed with the private key, s = m^d(modn), and the signature verified with the public key, m = s^e(modn).

2.2 Quantum Computing and Quantum Cryptanalysis

Quantum computing [13] is an emerging theory and practice of computer science which is based on the principles of quantum mechanics, in particular superposition, entanglement, and quantum interference. Quantum computing operations are fundamentally different from operations utilized in classical computing. Qubits (quantum bits) are distinct from classical bits, which encode binary representations—either a 1 or 0. Qubits exist as a coherent superposition of states, simultaneously representing 1 and 0, which exponentially expands the representational capacity within the computational system. This increased capacity gives quantum computers the ability to theoretically compute certain classes of problems, such as factorization and unstructured search, with unparalleled efficiency when compared to classical computers. Quantum cryptanalysis [17] exploits this advantage in computational efficiency to target cryptographic protocols, particularly protocols which are reliant on the hardness of specific mathematical problems like integer factorization and discrete logarithms. Quantum computers are mostly theoretical, and true quantum computers may never be built at scale or widely available. (Indeed, the cryptographer Nigel Smart jokes that we’ve been ten years away from real world quantum computers for several decades [16].) However, the development of quantum algorithms, such as Shor’s algorithm [15] for factorization and Grover’s algorithm [7] for search, threaten widely deployed cryptographic standards, including RSA and elliptic curve cryptography.

2.2.1 Factorization as an Optimization Problem

Composite numbers are products of prime numbers and prime factorization, the decomposition of composite numbers into their constituent primes, is known to be a hard problem as numbers get larger. Burges’ seminal paper [4] recasts prime factorization—biprimes in particular—as an unconstrained optimization problem using quartic polynomials. The paper initially describes a factoring decomposition that maps prime factorization to a constrained optimization landscape and then introduces a novel ”Curvature Inversion Descent” (CID) algorithm, which efficiently escapes local minima. Experimental analysis showed that the CID algorithm escaped local minima nearly 90% of the time, a remarkable improvement over the roughly 30% successful escapes by other gradient descent approaches.

2.2.2 Quantum Hardware: Annealer vs Gates

The two most common paradigms for quantum computing are quantum gates [20] and quantum annealing [12]. Both of these approaches are based on principles from quantum mechanics; however, they differ significantly in models, mechanisms, and applications.

Gate-based quantum computing is analogous to classical computing, but operates on qubits rather than classical bits. Qubits can exist in superposition, representing both 0 and 1 simultaneously and can thus be entangled, enabling correlations between qubits that classical systems simply cannot replicate. These properties allow quantum computers to process information in ways that classical computers are unable to match. The computational process in gate-based quantum systems is structured around quantum circuits, consisting of a sequence of quantum gates. These gates are mathematical operations that manipulate qubits’ states.

These gates implement step-by-step processes to solve specific problems, such as factoring integers using Shor’s algorithm [15] or optimizing search processes using Grover’s algorithm [7]. Qubits are prone to noise and decoherence, and so this approach requires precise control over the quantum system and error correction mechanisms. Examples of quantum gate-based systems include IBM’s Quantum Processors and Google’s Sycamore.

Quantum annealing is used to solve optimization problems. Instead of discrete quantum gates, this approach uses the principles of adiabatic quantum computing. This process is based on evolving a quantum system from an initial simple state to the ground state (i.e. the lowest energy configuration) of a more complex problem Hamiltonian. This process begins by encoding the optimization problem into a cost function, represented as a quantum Hamiltonian (i.e. a mathematical description of the energy of a system). The system is initialized in the ground state of a simple, known Hamiltonian, which is slowly transformed into the problem Hamiltonian. If the evolution is slow enough, the system remains in its ground state throughout, providing the solution to the optimization problem when the process completes.

Quantum annealing is particularly effective for problems that can be represented as finding the global minimum of a function, including combinatorial optimization, integer factorization, and machine learning. However, quantum annealing approaches lack the versatility of gate-based quantum computers and face challenges such as noise sensitivity and embedding overhead. The most noteworthy implementations are D-Wave’s quantum annealers, which solve problems by mapping them onto Ising models [5] or quadratic unconstrained binary optimization (QUBO) [2] formulations.

2.2.3 The D-Wave Architecture

D-wave [1] is a quantum computing company which was the first to offer quantum-effect computing services to the marketplace. D-Wave systems minimize an energy function represented as either a QUBO problem or an equivalent Ising model, where variables correspond to qubits and their interactions represent problem constraints. By leveraging quantum superposition and tunneling, the annealer can escape local minima and find the global minimum more effectively than classical methods for certain problems. Physical qubits are made from superconducting loops operating at near absolute zero, and interact via programmable couplers, enabling precise encoding of optimization tasks.

D-wave’s hardware uses connectivity patterns to arrange qubits and their interactions. Compared to older topologies, their Pegasus design enhances connectivity and reduces overhead when mapping logical problem variables to physical qubits. D-Wave’s systems are purpose-built and excel primarily in optimization tasks like scheduling, resource allocation, integer factorization, and machine learning.

2.2.4 Quantum Attacks Against Cryptographic Protocols

Much of modern cryptography is built upon one-way functions, or mathematical operations that are easy to compute but with an inverse operation that is prohibitively difficult. Examples of one-way functions include factoring large integers and discrete logarithms over finite fields. However, we have seen that some quantum computers excel at these inverse operations. Shor’s algorithm [15] is theoretically capable of efficiently factoring large integers, though the largest integer that it has factored to date is 21 [10]. While Shor’s algorithm is probably the most well-known quantum factoring approach, quantum annealing has been far more successful at integer factorization, and thus for cryptanalysis.

Jiang, et al. [8] developed a quantum annealing framework for integer factorization using Ising models, direct optimization and modified multiplication table approaches. Both methods reduce integer factorization to optimization problems solvable via quantum annealing hardware like D-Wave’s 2000Q, and they were able to factorize numbers up to 376,289 during experimentation. More recently, Ding, et al. [6] encoded prime factorization into a modular multiplier circuit using the Pegasus QA architecture. They detailed several annealing strategies, including initialization techniques, chain strengths, and anneal offsets, culminating in the successful factorization of 8,219,999, the largest number factorized solely through quantum annealing at the time.

3 The Recent Chinese Attack on Cryptographic Protocols with D-Wave

We are now ready to analyze the paper, “Quantum annealing public key cryptographic attack algorithm based on d-wave advantage,” [19] in which the authors discuss two RSA public-key cryptographic attack algorithms leveraging D-Wave’s quantum annealing technology. The quantum annealing approach, using quantum tunneling, avoids local minima in optimization problems, which makes it suitable for integer factorization in RSA attacks.

The authors propose two methods for attacking the RSA protocol. In the first method, they frame their attack as combinatorial optimization problems using Ising and QUBO models and use dimensionality reduction formulas to reduce the qubit count and improve the model’s stability. Using this approach, the authors were able to factor a 22-bit integer and advance beyond prior benchmarks. Building on this, the authors went on to integrate quantum annealing with classical mathematical methods, specifically Babai’s algorithm [3], to attack the Closest Vector Problem (CVP) [11]. The CVP is a computationally difficult lattice problem where the goal is to find the nearest vector in a point lattice to another vector (which may not be in that lattice). The authors used quantum tunneling with Babai’s algorithm to improve vector precision and a quantum annealing adaptation of Schnorr’s algorithm [14] for faster CVP solutions to factor a 50-bit RSA integer.

3.1 To Quote Monty Python, “I’m not dead yet.”

Though alarmist headlines certainly grabbed readers’ attention, there are a number of reasons that this paper may not herald the imminent demise of widely used cryptographic protocols like RSA and why it should be taken with a grain of salt. These reasons are partially practical, but there are also several details about the paper and its publication process which invite skepticism.

Assuming that the authors’ results are legitimate and repeatable, 22-bit and 50-bit integers are far shorter than the integer size of real-world RSA implementations. The current RSA standard is 2048-bit, but 4096-bit integers are recommended for longer term security. It is unclear how well the authors’ methodologies will scale to factoring integers of these lengths. Further experimentation will determine whether the paper’s results are repeatable, and answer questions on the approach’s scalability.

There are also several non-technical reasons to view this paper with skepticism. At 10 pages in length, it is a relatively short paper which was published in a Chinese language journal rather than an English language venue (such as an IEEE or ACM journal). The paper provides an abstract in English, but the body is entirely in Chinese and no English translation is readily available; services such as Google Translate or ChatGPT can be used to translate the paper. The article only went through a single round of peer review, which is unusual as the refereeing process is meant to ensure that manuscripts don’t contain any glaring holes in reasoning or procedure and are sufficiently polished for publication. Reading through translations of this paper, it is evident that the authors glossed over details which top-tier publication venues would require before accepting the manuscript for publication. On top of these concerns, the authors have reportedly been loathe to answer queries from media or other academics, allegedly due to the sensitivity of the topic. Furthermore, the article lists a Digital Object Identifier (DOI) number which does not exist (Figure 1). This opacity casts some doubt on the paper’s methods and results, pending broader experimentation within the broader cryptanalysis and quantum computing communities to verify the authors’ original work.

4 Conclusion

The claims made in “Quantum annealing public key cryptographic attack algorithm based on d-wave advantage” warrant scrutiny. The authors claim several intriguing advancements using quantum annealing to factor small integers and integrate classical mathematical techniques; however, the practical implications for real-world cryptographic protocols remain speculative at best. To make the jump from factoring 50-bit integers to compromising standard RSA keys, which are orders of magnitude larger, is a monumental one, and fraught with computational and scalability challenges that this paper does not convincingly address. The methods described require rigorous validation and testing by the broader research communities to assess their true potential and limitations, particularly when applied to cryptographic key sizes used in modern security systems.

Beyond the technical considerations, the context of the paper’s publication also raises questions about its reliability. An apparent lack of extensive, rigorous peer review, the decision to publish in a regional rather than international venue, and the absence of detailed methodological transparency suggest the need for tempered enthusiasm. While the paper has certainly generated excitement and speculation, it should be seen as a prompt for further research rather than as evidence of an imminent cryptographic apocalypse.

References

[1] D-Wave Systems. https://www.dwavesys.com/.

[2] Alom, M. Z., Van Essen, B., Moody, A. T., Widemann, D. P., and Taha, T. M. Quadratic unconstrained binary optimization (qubo) on neuromorphic computing system. In 2017 International Joint Conference on Neural Networks (IJCNN) (2017), IEEE, pp. 3922–3929.

[3] Babai, L. On lov´asz’lattice reduction and the nearest lattice point problem. Combinatorica 6 (1986), 1–13.

[4] Burges, C. J. Factoring as optimization. Microsoft Research MSR-TR-200 (2002).

[5] Cipra, B. A. An introduction to the ising model. The American Mathematical Monthly 94, 10 (1987), 937–959.

[6] Ding, J., Spallitta, G., and Sebastiani, R. Experimenting with d-wave quantum annealers on prime factorization problems. Frontiers in Computer Science 6 (2024), 1335369.

[7] Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996), pp. 212–219.

[8] Jiang, S., Britt, K. A., McCaskey, A. J., Humble, T. S., and Kais, S. Quantum annealing for prime factorization. Scientific reports 8, 1 (2018), 17667.

[9] Katz, J., and Lindell, Y. Introduction to modern cryptography: principles and protocols. Chapman and hall/CRC, 2007.

[10] Martin-Lopez, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.-Q., and O’brien, J. L. Experimental realization of shor’s quantum factoring algorithm using qubit recycling. Nature photonics 6, 11 (2012), 773–776.

[11] Micciancio, D., Goldwasser, S., Micciancio, D., and Goldwasser, S. Closest vector problem. Complexity of Lattice Problems: A Cryptographic Perspective (2002), 45–68.

[12] Morita, S., and Nishimori, H. Mathematical foundation of quantum annealing. Journal of Mathematical Physics 49, 12 (2008).

[13] Rieffel, E., and Polak, W. An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR) 32, 3 (2000), 300–335.

[14] Schnorr, C.-P. A more efficient algorithm for lattice basis reduction. Journal of algorithms 9, 1 (1988), 47–62.

[15] Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (1994), Ieee, pp. 124–134.

[16] Smart, N. Implications of the proposed quantum attack on lwe, 2024. https://nigelsmart.github.io/LWE.html.

[17] Suo, J., Wang, L., Yang, S., Zheng, W., and Zhang, J. Quantum algorithms for typical hard problems: a perspective of cryptanalysis. Quantum Information Processing 19 (2020), 1–26.

[18] Swain, G. Chinese researchers break rsa encryption with a quantum computer. CSO Online (October 14, 2024). https://www.csoonline.com/article/3562701/chinese-researchers-break-rsa-encryption-with-a-quantum-computer.html.

[19] Wang, C., Wang, Q.-D., Hing, C.-L., Hu, Q.-Y., and Zhi, P. Quantum annealing public key cryptographic attack algorithm based on d-wave advantage. Chinese Journal of Computers 47, 5 (2024). DOI: 10.11897/SP.J.1016.2024.01030 http://cjc.ict.ac.cn/online/onlinepaper/wc-202458160402.pdf.

[20] Williams, C. P., and Williams, C. P. Quantum gates. Explorations in Quantum Computing (2011), 51–122.