Three weeks ago, panic spread in some corners of the security world after researchers discovered a breakthrough that finally brought cracking of the widely used RSA encryption scheme within reach using quantum computing.
Scientists and cryptographers have known for two decades that a factorization method known as Shor’s algorithm makes it theoretically possible for a well-resourced quantum computer to break RSA. This is because the secret prime numbers that underpin the security of an RSA key are easy to compute using Shor’s algorithm. Calculating the same prime numbers using classical computing takes billions of years.
The only thing holding back this doomsday scenario is the sheer amount of computing resources required for Shor’s algorithm to crack RSA keys of sufficient size. The current estimate is that cracking a 1024-bit or 2048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in superposition. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. But whereas a classical binary bit can represent only a single binary value such as 0 or 1, a qubit is represented by a superposition of multiple possible states. .)
The paper, published three weeks ago by a team of researchers in China, reported finding a factorization method that could crack a 2048-bit RSA key using a quantum system with just 372 qubits when operating with thousands of operation steps. The finding, if true, would have meant that the fallout of RSA encryption in quantum computing could come much sooner than most people believed.
The disappearance of RSA is greatly exaggerated
At the 2023 Enigma Conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that RSA’s disappearance was greatly exaggerated. At the moment, he said, quantum computing has few if any practical applications.
“In the short term, quantum computers are good for one thing, and that’s publishing papers in prestigious journals,” Garfinkel, co-author with Chris Hoofnagle of the 2021 book Law and politics for the quantum agehe told the audience. “The second thing that they’re reasonably good at, but we don’t know for how much longer, is that they’re reasonably good at getting financing.”
Even when quantum computing becomes advanced enough to provide useful applications, the applications are likely to simulate physics and chemistry and perform computational optimizations that don’t work well with classical computing. Garfinkel said a dearth of useful applications for the foreseeable future could spark a “quantum winter,” similar to the multiple rounds of artificial intelligence winters before AI finally took off.
The problem with the paper published earlier this month was its reliance on the Schnorr algorithm (not to be confused with Shor’s algorithm), which was developed in 1994. The Schnorr algorithm is a classical computation based on networks, which are mathematical structures that have many applications in constructive cryptography and cryptanalysis. The authors who devised the Schnorr algorithm said that it could improve the use of the quantum optimization heuristic method called QAOA.
Before long, a host of researchers pointed out fatal flaws in Schnorr’s algorithm that have nearly brought it into disrepute. Specifically, critics said that there was no evidence to support the authors’ claims that Schnorr’s algorithm achieved polynomial time, as opposed to the exponential time achieved with classical algorithms.
The research paper from three weeks ago seemed to take Shor’s algorithm at face value. Even when supposedly enhanced by QAOA, something for which there is currently no support, it is questionable whether it provides any performance gains.
“All told, this is one of the most misleading quantum computing papers I’ve seen in 25 years, and I’ve seen…a lot,” Scott Aaronson, a computer scientist at the University of Texas at Austin and director of the Quantum Information Center , wrote. “Having said that, this is not the first time I’ve come across the strange idea that quantum exponential speedup for integer factorization, which we know from Shor’s algorithm, should somehow ‘stick’ to the heuristics of quantum optimization that do not incorporate any of the actual insights of Shor’s algorithm, as if by sympathetic magic.