reader comments
34 with 0 posters participating
Three weeks ago, panic swept across some corners of the security world after researchers discovered a breakthrough that, at long last, put the cracking of the widely used RSA encryption scheme within reach by 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 quantum computer with sufficient resources to break RSA. That’s because the secret prime numbers that underpin the security of an RSA key are easy to calculate using Shor’s algorithm. Computing the same primes using classical computing takes billions of years.
The only thing holding back this doomsday scenario is the massive amount of computing resources required for Shor’s algorithm to break 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 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 classic binary bit can represent only a single binary value such as a 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 break a 2,048-bit RSA key using a quantum system with just 372 qubits when it operated using thousands of operation steps. The finding, if true, would have meant that the fall of RSA encryption to quantum computing could come much sooner than most people believed.
RSA’s demise is greatly exaggerated
At the Enigma 2023 Conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that the demise of RSA was greatly exaggerated. For the time being, he said, quantum computing has few, if any, practical applications.
QAOA.
Within short order, a host of researchers pointed out fatal flaws in Schnorr’s algorithm that have all but debunked it. Specifically, critics said there was no evidence supporting the authors’ claims of Schnorr’s algorithm achieving 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 it’s supposedly enhanced using QAOA—something there’s currently no support for—it’s questionable whether provides any performance boost.
“All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many,” Scott Aaronson, a computer scientist at the University of Texas at Austin and director of its Quantum Information Center, wrote. “Having said that, this actually isn’t the first time I’ve encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor’s algorithm, should somehow ‘rub off’ onto quantum optimization heuristics that embody none of the actual insights of Shor’s algorithm, as if by sympathetic magic.”
