Briefly this week, it appeared that quantum computers might finally be ready to break 2048-bit RSA encryption, but that moment has passed.
The occasion was the publication of an academic paper by no less than two dozen authors affiliated with seven different research institutions in China.
The paper, titled “Factoring integers with sublinear resources on a superconducting quantum processor,” suggests that the application of Claus Peter Schnorr’s recent factoring algorithm, in conjunction with a quantum approximate optimization algorithm (QAOA), can break asymmetric RSA-2048 encryption using a non-fault tolerant (NISQ, or noisy intermediate scale quantum) quantum computer with only 372 physical quantum bits or qubits.
If true, this would be a significant development because there are already quantum computers that exceed that specification, like IBM’s 433-qubit Osprey.
The speculation has been that orders of magnitude more qubits, in conjunction with robust error correction at scale, may allow future quantum computers to run Peter Schor’s algorithm – not to be confused with the similarly named Schnorr – quickly, on very large numbers, thereby breaking RSA encryption.
In 2019, researchers published a paper [PDF] claiming that 2048-bit RSA integers could be factored in about eight hours … given a quantum computer with 20 million noisy qubits (meaning without the overhead of error correction and the like).
That’s a future the National Security Agency has been planning for since 2015, when it started public work on developing quantum-resistant encryption algorithms.
No one is quite sure when, or whether, that day