Unravelling the Chinese factoring algorithm: is our current encryption still safe?
A recent article, posted on the physics ArXiv by Chinese researchers, has caused quite a buzz in the quantum world. These researchers claim to have discovered a new factoring algorithm, which is sublinear in the number of qubits it requires. What does this mean? Well, in one instance they demonstrated factoring of a 48-bit integer (261980999226229) with only 10 qubits. They also claim that 372 physical qubits are sufficient to break RSA-2048! Here the term “physical” qubit is very significant. It means that the algorithm can use non-perfect qubits, as implemented in current quantum computers.
A Quantum Leap in Quantum Computing and QRA’s
Let’s put this into context. In November last year, IBM announced its Osprey processor. With 433 qubits it represents a tripling of the qubits on its previous gen Eagle processor. The roadmap includes the next gen Condor processor, slated for release in 2023, that will feature 1,121 qubits. This could mean breaking existing asymmetric cryptography is imminent. No wonder the article caused such a commotion.
But wait, there’s more. (Apologies in advance if this gets a little technical). The new quantum algorithm relies on a mapping of factoring onto a lattice-based problem. Basically, in order to solve factoring, they solve (approximately) the Closest Vector Problem on a lattice. Why is this important? Because this is precisely the type of problem that has been selected by NIST to develop new Quantum-Resistant Algorithms (QRA’s), designed to replace current RSA and ECC.
So, this new algorithm may also have an impact on the QRA’s – though it only gets a brief mention towards the end of the article: “[this algorithm] can be used as a subroutine in a large group of widely used lattice reduction algorithms. Further on, it can help to analyze the quantum-resistant cryptographic problems based on lattice.” This may have a significant impact on post-quantum cryptography, which was designed to replace existing asymmetric cryptography. We could be getting closer to the cryptopocalypse!
The claims have been met with a fair degree of scepticism, with some saying they are speculative at best and others saying they are just plain wrong.
As acknowledged by the authors, the number of qubits required is only part of the equation. Circuit depth is also a critical factor in quantum computing. Circuit depth is the number of operations that can be performed by your quantum circuit before you lose the quantum properties, known as the coherence of the qubits. Factoring RSA-2048 would require a circuit depth of a thousand, way above what can be achieved today.
Another factor is time. Or, more accurately, the number of operations required to solve the problem you are addressing. This algorithm is based on an optimization problem, where the computation doesn’t follow a step-by-step approach. Instead, you generate an input and let it evolve until you obtain a result, which should be close to the optimum. As a result, the number of operations required is not known in advance.
Some algorithms may converge quickly, others may be much slower. The latter seems to be the case for this new algorithm. So, although you may not need too many qubits, and although you may obtain qubits of sufficient quality to implement the required circuit depths in a few years, it may well be that the convergence of the algorithm will be so slow that solving factoring of large integers is not achievable.
One of the authors of the paper, Prof. Long Gui-Lu, explained to us that they plan to test the new algorithm with larger and larger integers, to get at least an idea of the convergence speed as the size of the input increases. This will provide more useful information and bring greater confidence (or not) in the result.
In summary, it’s clearly too early to know just how significant these results are. Breaking RSA-2048 may still take some time, but this publication is likely to generate a flurry of additional works in the year ahead.
