RSA’s demise due to quantum attacks is highly exaggerated, experts say.

Three weeks ago, it took some corners of the security world by storm after researchers finally found a breakthrough that could use quantum computing to reach cracking of the widely used RSA cryptographic scheme.

Scientists and cryptographers have known for 20 years that the factoring method known as Shor’s algorithm is theoretically possible for a quantum computer with sufficient resources to break RSA. This is because the secret primes behind the security of RSA keys are easy to compute using Shor’s algorithm. It takes billions of years to calculate the same prime numbers using classical computing.

The only thing holding back this doomsday scenario is the sheer amount of computing resources required for Shor’s algorithm to break an RSA key of sufficient size. Current estimates are that cracking a 1,024-bit or 2,048-bit RSA key would require a quantum computer with vast resources. Specifically, these resources are about 20 million qubits, of which about 8 hours are running in superposition. (A qubit is a fundamental unit of quantum computing, similar to a binary bit in classical computing. However, a classical binary bit can only represent a single binary value, such as 0 or 1, whereas a qubit is represented by a superposition of multiple possible states.)

The paper, published three weeks ago by a Chinese research team, reported finding a decomposition method capable of breaking a 2,048-bit RSA key using a quantum system of just 372 qubits when operating using thousands of computational steps. If this finding were true, it would have meant that RSA cryptography’s fall to quantum computing could be coming much sooner than most people think.

RSA’s demise is greatly exaggerated.

At the Enigma 2023 conference on Tuesday in Santa Clara, California, computer scientist and security and privacy expert Simson Garfinkel convinced researchers that the end of RSA was greatly exaggerated. He said there are few practical applications for quantum computing for the time being.

Garfinkel, co-author of the 2021 book with Chris Hoofnagle, said, “In the short term, quantum computers are useful for one thing, which is to publish papers in prestigious journals.” Laws and Policies for the Quantum Age, said to the audience. “The second thing they do reasonably well is that they finance it reasonably well.”

Even if quantum computing is advanced enough to provide useful applications, applications are likely to simulate physics and chemistry and perform computational optimizations that do not play well with conventional computing. Garfinkel said the lack of useful applications in the near future could lead to a “quantum winter” similar to an AI winter of several rounds before AI finally takes off.

The problem with the paper published earlier this month is that it relied on Schnorr’s algorithm (not to be confused with Shor’s) developed in 1994. Constructive encryption and cryptanalysis. The authors of Schnorr’s algorithm said it could improve the use of a heuristic quantum optimization method called QAOA.

In a short period of time, many researchers have pointed out a fatal flaw in Schnorr’s algorithm. In particular, critics said there was no evidence to support the authors’ claim that Schnorr’s algorithm achieved polynomial time, unlike the exponential time achieved by classical algorithms.

A research paper from three weeks ago seemed to take Shor’s algorithm at face value. Even assuming it’s improved using QAOA (which is currently unsupported), the question is whether it provides any performance improvement.

“This is one of the most aggressively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen many,” said Scott Aaronson, a computer scientist at the University of Texas at Austin and director of Quantum. Information Center, I wrote. “That said, this isn’t actually the first time we’ve come across the odd idea that the exponential quantum speed-up on factored integers we know from Shor’s algorithm must somehow be ‘cleared’ by a quantum optimization heuristic that implements nothing. . About the actual insights of the Shor algorithm, as if by empathic magic.”