Breaking RSA: Separating Hype from Reality

I've been asked by people about the claims from China about breaking RSA https://lnkd.in/gBXQi6AB

High level answer:

• Don't panic
• Don't procrastinate in your migration to quantum-safe cryptography
• Plan a migration to post-quantum public-key cryptography, and ALSO be prepared for an unexpected break that works

In more detail:
Shor's algorithm breaks today's public key cryptography efficiently (so longer keys are not a viable solution). It requires O(n) fault-tolerant qubits to break n-bit RSA. So over 4000 fault-tolerant logical qubits (using the best-known methods today) to break RSA-2048.

But can we break RSA-2048 with fewer qubits?
e.g. Can we use fewer qubits and speed up the (classical) Number Field Sieve (NFS)?
In eprint.iacr.org/2017/352 we show that roughly O(n^{2/3}) logical qubits allow us to improve the NFS. Not polytime, and we didn't work out the constants. This approach doesn't keep me up at night, but it does illustrate there is nothing fundamental about needing O(n) qubits to break n-bit RSA better than is currently possible.

This new paper is trying to speed up part of another classical algorithm, based on reducing integer factorization to lattice basis reduction.
Prof. Schnorr's version of this approach hasn't been demonstrated to be competitive with the NFS. See e.g. https://lnkd.in/gZgTMkp9 which outlines relevant background and analysis.
 
The method in arxiv paper 2212.12372 uses O(n/log n) qubits. This is more than the O(n^{2/3}) qubits we showed for NFS, but they propose using physical qubits instead of fault-tolerant logical qubits (many physical qubits are needed to achieve a logical qubit).

But to compete (in run-time and total resources) with the NFS, this QAOA based approach would have to substantially outperform classical methods for lattice basis reduction. There's no evidence that it comes close to classical methods.
See e.g. Scott's note on this: https://lnkd.in/g69DJyZs

Even if it worked with a few hundred logical qubits, it would be interesting (but, again, there's no evidence to suggest it does).
Hence, this new paper isn't a reason to panic.

I'd reiterate our suggestion in arxiv.org/abs/1910.09592 to apply heuristic quantum algorithms to smoothness testing. We don't suggest it will be easy or likely, but at least there it will be easier to translate heuristic quantum speed-ups to faster integer factorization.

Bright people are working on new methods that could reduce the requirements to break RSA or ECC.  Hence, we shouldn't procrastinate in moving along the complex migration to quantum-safe cryptography, including replacing RSA and ECC with standardized post-quantum algorithms.

Further, new methods might also lead to advances in breaking the post-quantum algorithms, so we must also be ready to respond to this in a pragmatic way. Agility is an important part of the answer, as well as more practical deployments of key agreement methods that don't rely on asymmetric key agreement algorithms.