A new quantum algorithm to break into sensitive data, but it does not work (for how long?)

A new quantum algorithm that needs just 372 physical qubits (available now) was proposed to break sensitive data (RSA 2048), but it does not work now (for how long?)

Quantum computing has shown its teeth to the cyber community and alarms with the possibility of hacking sensitive data. The threat is fueled by developments from two fronts: hardware and algorithms evolution. This time steps were made on the algorithms front.

Recently researchers from China published a paper claiming that they need just 372 physical qubits to factor RSA-2048. 372 physical qubits are available today. And breaking RSA-2048 is a milestone opening the door to cryptographically protected data. The factoring algorithm that they proposed is based on a scheme that works well for smaller numbers (~50 bit) and cannot be easily scaled to higher-order numbers. So, for now, we are in a safe place.

It is hard to predict new knowledge creation. However, motivation, financing and attention are factors to consider. They do not leave a lot of choices for corporates and governments to develop their quantum-readiness strategy. This achievement illustrates the urgency of the question.

The evolution of algorithms to break sensitive data and render currently used cryptography algorithms non-secure is thrilling. The first algorithm proposed was Shor's algorithm in the 90th. It provides a way to factor large numbers but requires very mature hardware (millions of logical qubits and very long circuit depth). Later many attempts were made that dropped the demand to complete a factoring task first to 1 billion physical qubits (2011, Fowler et al.), then 200 million (2014, O'Gorman et al.), and then 20 million (2019, Gidney, Ekera). At this stage, demand was much higher than what was available to the industry. In 2022, Zapata offered a VQF algorithm that required just 6000 qubits (it is a heuristic algorithm and may not always work). And today, we encountered an attempt to cut one more order of magnitude, but it is not scalable.

Many companies started the transition to Post-Quantum Cryptography, which has many obstacles. Those new algorithms are computationally more demanding. And the scale of change does not allow us to execute it overnight.

Reference to the original paper - https://arxiv.org/abs/2212.12372v1