Three weeks ago, panic came across certain corners of the security world after researchers emerged who finally cracked the widely used RSA encryption scheme within reach by using quantum computing.
Scientists and cryptographers have known for the past twenty years that a factorization method called Shor’s algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. That’s because it’s easy to calculate the secret primes that form the basis of RSA key security using Shor’s algorithm. It takes billions of years to use the same key skills using classical computing.
The only thing holding this back is the enormous amount of computing resources required to break Shor’s algorithm to RSA keys of sufficient size. The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with massive resources. Specifically, those resources represent about 20 million cubits and about eight hours of them running in overlay. (A qubit is a basic unit of quantum computing similar to the binary bit in classical computing. But while a classical binary bit can only represent a single binary value as 0 or 1, a qubit represents a possible multiple superposition of states.)
The paper, published three weeks ago by a team of researchers in China, reported that a factorization method was found that could break a 2,048-bit RSA key using a quantum system with just 372 qubits when it operated using using thousands of steps of operation. If the result were true, it would mean the fall of RSA encryption to quantum computing much sooner than most people believed.
The demise of the RSA is greatly exaggerated
At the Enigma 2023 Conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel confirmed to researchers that the demise of RSA was greatly exaggerated. For the time being, he said, quantum computing has few, if any, practical applications.
“In the short term, quantum computers are good for one thing, and that is to publish papers in prestigious journals,” Garfinkel, co-author with Chris Hoofnagle of the book 2021 Law and Policy for the Quantum Age, said the audience. “The second thing they’re doing reasonably well, but we don’t know how much longer, is that they’re reasonably well funded.”
Even when quantum computing is advanced enough to provide useful applications, there will likely be applications for physics and chemistry simulation, and computer optimization that do not work well with classical computing. Garfinkel said that a “quantum hibernation” could occur due to the lack of useful applications in the future, similar to the multiple rounds of artificial intelligence hibernation 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 lattices, which are structures mathematics with many applications. constructive cryptography and cryptanalysis. The authors who devised Schnorr’s algorithm said that it could improve the use of the heuristic quantum optimization method known as QAOA.
In short order, several researchers pointed out fatal flaws in Schnorr’s algorithm that led to its debunking. Specifically, critics said there was no evidence to support the authors’ claims that Schnorr’s algorithm would achieve exponential time, compared to the exponential time achieved by classical algorithms.
The research paper from three weeks ago appeared to take Shor’s algorithm further. Even when it is apparently improved using QAOA – which is currently unsupported – it is questionable whether it provides any performance boost.
“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 a Quantum Information Center, write. Having said that, this is not the first time I have come across the strange idea that the quantum exponential speedup for factoring integers, which we know about from Shor’s algorithm, should ‘sub off’ quantum optimization heuristics that are not in included in it. of the actual insights into Shor’s algorithm, as if by sympathetic magic.”