Understanding the breakthrough
The Chinese Journal of Computers recently published a paper in which researchers from Shanghai University factored a 22-bit integer using D-Wave’s quantum annealing machine. The research showcases how quantum annealing can be leveraged to transform cryptographic attacks into solvable combinatorial optimization problems.
The team factored a 22-bit number, a far cry from the 2048-bit keys currently used for secure encryption. The difference between a 22-bit and a 2048-bit number is exponential, and this study, while a step forward, doesn’t yet threaten RSA encryption as we know it.
RSA encryption, a widely used public-key cryptosystem, relies on the difficulty of factoring large prime numbers. While classical computers struggle with factoring large numbers, quantum computing, theoretically, could solve this problem using much faster algorithms.
Quantum Annealing vs. General-purpose Quantum Computers
The research used quantum annealing, a method focused on solving optimization problems, rather than a general-purpose quantum computer, which can execute broader tasks like Shor’s algorithm. D-Wave’s quantum annealer is not yet capable of handling the large numbers necessary for breaking RSA encryption of today effectively. The method used involved a hybrid quantum-classical approach—where traditional computers still play a major role. It is also not clear whether the attack would scale on a quantum annealer as well as it does on a general-purpose quantum computer using Shor’s algorithm.
Quantum Annealing may ultimately offer a faster path to breaking RSA keys in comparison to traditional computers, and therefore deserves our attention. However, it is not clear whether a large enough quantum annealer capable of running the attack of the Chinese researchers will be available before a large enough general-purpose quantum computer capable of running Shor’s algorithm to break actual RSA keys used today.
Quantum technology threats to cryptography
Despite the excitement surrounding this study, it’s essential to understand the limitations of quantum technology in breaking cryptography. Apart from the already mentioned modest scale of current quantum computers there are a few other considerations:
- Small Scale: The D-Wave machine only managed to factorize a 22-bit number. In contrast, RSA encryption typically uses keys of at least 2048 bits, with some systems using 4096-bit keys, making current quantum attempts insufficient.
- Classical Computers Still Win: Quantum computers are far from beating traditional computing at factoring the largest numbers. The biggest number factored using classical methods, as of 2020, was a 250-digit number (an 829-bit number), while quantum machines are still far behind.
- Symmetric algorithms not at risk: Quantum computers primarily threaten asymmetric algorithms, such as RSA and ECC. The widely used symmetric AES algorithm is not at risk. Over time, there may be a need to switch to longer keys, which is supported by the AES algorithm.
- Technical Challenges: Quantum computers face significant challenges in scaling up. Qubits (the fundamental unit of quantum information) are highly sensitive to disturbances, and maintaining stability requires drastic measures.
- For stable calculations, it is estimated that one logical qubit might need between 100 to 1,000 physical qubits to ensure reliable functioning. Moreover, researchers anticipate that breaking RSA-2048 encryption would require approximately 4,000 logical qubits, highlighting the scale of the challenge.
- Additionally, Microsoft Research has calculated that to break a standard 256-bit key, such as those used in elliptic curve cryptography, around 2,500 logical qubits would be required to compute the necessary discrete logarithms.
- Despite these challenges, even smaller quantum computers can still offer value in certain business applications. For example, a 100-logical-qubit quantum computer could provide practical benefits for optimization problems or machine learning tasks. However, this is far from the quantum power needed to crack RSA encryption.
- Our experts urge caution in over-interpreting quantum computing advancements. Misrepresenting the capabilities of quantum technology at this stage only serves to spread uncertainty. As Duncan Jones from Quantinuum points out, if a nation truly had the ability to crack RSA encryption on a large scale, it is unlikely they would advertise it publicly.
The Move Toward Quantum-Resistant Encryption
It is justified however to prepare for future quantum threats, and the industry is already adopting quantum-resistant encryption, which is generally referred to as Post Quantum Cryptography (PQC). Algorithms like Dilithium and Kyber, are now standardized by NIST and begin to find their way to various applications. They offer security that can withstand quantum attacks of the future.
PQC algorithms provide strong encryption and can already be applied. The most important challenge today is to implement new algorithms without compromising the security. Mistakes introduced during deployment may cause more damage than existing attack methods involving quantum computing. Therefore, it remains important to evaluate PQC implementations to verify that addressing quantum computer threats does not inadvertently introduce new vulnerabilities through poor implementation practices. Users of PQC can get assurance by insisting on verified and certified products.