Recently, an academic paper from a large team of Chinese researchers made the headlines of the specialized press [1]. Reporters claimed that “small” quantum computers may break RSA2048. Breaking RSA2048 may need only 372 qubits. Qubits are similar to bits in the quantum domain. IBM already proposes Osprey: a 433-qubit chip. So, is RSA2048 dead?
The security of RSA relies on the assumption that factorizing the product of two large prime numbers is extremely difficult. It is assumed currently that conventional computers cannot solve this problem. Recent studies showed that, in theory, quantum computers may succeed.
The paper is not for the faint heart. Its summary is as follows:
Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglog N), which is sublinear in the bit length of the integer $N$, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.
As mentioned, RSA’s security assumes it is tough to factorize the product of two very large prime numbers. The researchers use Schnorr’s algorithm [2] to factor these large numbers rather than the Schor one. On the one hand, the Schor algorithm requires millions of qubits, but it is a theoretically proven solution. Unfortunately, it is out of the current feasibility realm. On the other hand, Schnorr’s algorithm seems not yet to be a proven solution at a large scale. The expected speed-up using quantum computing is highly controversial and not demonstrated. The paper stays in the realm of unproven expectations.
The consensus seems to be that the threat is not yet here. Following is a list of posts of people who know far better than me:
- [3] highlights one crucial point (present in all papers): It should be pointed out that the quantum speed-up of the algorithm is unclear due to the ambiguous convergence of QAOA. In other words, the paper does not demonstrate that it is faster than Schor’s. Scott is a quantum computing expert.
- [4] highlights that the paper never claims to be faster. It omits “running time”; what is merely claimed is that the quantum circuit is very small.
- [5] Bruce Schneier reminds that Schnorr’s paper works well for small moduli, but does not scale well for larger prime numbers.
- [6] highlights that the quantum computer should have a 99.999% fidelity. This would require a NISQ computer with gate level fidelities of 99.999%. That level is more than two orders of magnitude better than the best machines we have today.
Conclusion
Keep calm. RSA 2048 is still safe for many years. Nevertheless, it is key to be aware of the latest progress of post-quantum cryptography. Do we have to switch to post-quantum cryptography? Not right now, especially if you do not handle secrets that have to last for many decades.
Reference
[1] B. Yan et al., “Factoring integers with sublinear resources on a superconducting quantum processor.” arXiv, Dec. 23, 2022. Available: http://arxiv.org/abs/2212.12372
[2] C. P. Schnorr, “Fast Factoring Integers by SVP Algorithms, corrected.” 2021. Available: https://eprint.iacr.org/2021/933
[3] S. Aaronson, “Cargo Cult Quantum Factoring,” Shtetl-Optimized, Jan. 04, 2023. https://scottaaronson.blog/?p=6957
[4] “Paper claims to break RSA-2048 with only 372 physical quibits.” https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AkfdRQS4yoY/m/3plDftUEAgAJ .
[5] “Breaking RSA with a Quantum Computer – Schneier on Security.” https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html
[6] dougfinke, “Quantum Experts Debunk China Quantum Factoring Claims,” Quantum Computing Report, Jan. 06, 2023. https://quantumcomputingreport.com/quantum-experts-debunk-china-quantum-factoring-claims