Three weeks ago, many security scientists panicked when Chinese researchers announced the breaking the widely used RSA encryption system using quantum computers.
Scientists and cryptographers have known for two decades that a factorization method known as Shor's algorithm it makes it theoretically possible for a quantum computer with sufficient resources to break RSA.
This is because the secret primes that support the security of an RSA key are easy to compute using Shor's algorithm. Calculating prime numbers using classical computers can take billions of years.
The only thing standing in the way of this catastrophic scenario is the massive amount of computing resources required for Shor's algorithm to crack RSA keys. The current estimate is that breaking a 1.024-bit or 2.048-bit RSA key requires a quantum computer with enormous resources. Specifically, these resources should be about 20 million qubits running for about eight hours. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. But while a classical binary bit can only represent a single binary value such as 0 or 1, a qubit is represented by a set of multiple possible values. )
The paper, published three weeks ago by a team of researchers in China, reported finding a factorization method that could crack a 2.048-bit RSA key using a quantum system with just 372 qubits. The finding, if true, would mean that breaking RSA encryption in quantum computing could come much sooner than most people think.
At the Enigma 2023 conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that the RSA crack was overblown. At present, he said, quantum computing has few, if any, practical applications.
“In the near future, quantum computers will be good for one thing, and that will be publishing articles in peer-reviewed journals”, Garfinkel, co-author with Chris Hoofnagle of the 2021 book Law and Policy for the Quantum Age, told the audience.
"The second thing they're pretty good at, but we don't know how much longer, is they're pretty good at getting financing."
Even when quantum computing becomes advanced enough to provide useful applications, the lack of useful applications in the near future may result in a “quantum winter,” similar to the multiple winters we had in artificial intelligence before we finally took the first steps.
The problem with the work published earlier this month is its reliance on Schnorr's algorithm (not to be confused with Shor's algorithm), which was developed in 1994. Schnorr's algorithm is a classical computation based on lattices, which are mathematical structures that have many applications in constructive cryptography and cryptanalysis. The scientists who devised Schnorr's algorithm reported that it could enhance the use of a heuristic quantum optimization method called QAOA.
In a short time, too many researchers have discovered flaws in Schnorr's algorithm and have debunked it. Specifically, they stated that there is no evidence to support claims that Schnorr's algorithm achieves polynomial time, as opposed to the exponential time achieved by classical algorithms.
The research paper three weeks ago appeared to take Shor's algorithm at face value. Even when it's supposed to be improved by the addition of QAOA - something it doesn't currently exist for - it's doubtful that it provides any performance boost.
"Consequently, this is one of the most misleading quantum computing papers I've seen in the last 25 years, and I've seen... a lot," Reported Scott Aaronson, a computer scientist at the University of Texas at Austin and director of the Quantum Information Center.