REALITY CHECK — RSAs demise from quantum attacks is very much exaggerated, expert says Expert says the focus on quantum attacks may distract us from more immediate threats.
Dan Goodin – Jan 26, 2023 1:15 am UTC Enlarge reader comments 36 with 0 posters participating Share this story Share on Facebook Share on Twitter Share on Reddit
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 Shors algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. Thats because the secret prime numbers that underpin the security of an RSA key are easy to calculate using Shors 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 Shors 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. RSAs 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. Advertisement
In the near term, quantum computers are good for one thing, and that is getting papers published in prestigious 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 are reasonably good at, but we dont know for how much longer, is theyre reasonably good at getting funding.
Even when quantum computing becomes advanced enough to provide useful applications, the applications are likely for simulating physics and chemistry, and performing computer optimizations that dont work well with classical computing. Garfinkel said that the dearth of useful applications in the foreseeable future might bring on 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 Schnorr’s algorithm (not to be confused with Shors algorithm), which was developed in 1994. Schnorrs algorithm is a classical computation based on lattices, which are mathematical structures that have many applications in constructive cryptography and cryptanalysis. The authors who devised Schnorrs algorithm said it could enhance the use of the heuristic quantum optimization method called QAOA.
Within short order, a host of researchers pointed out fatal flaws in Schnorrs algorithm that have all but debunked it. Specifically, critics said there was no evidence supporting the authors claims of Schnorrs algorithm achieving polynomial time, as opposed to the exponential time achieved with classical algorithms.
The research paper from three weeks ago seemed to take Shors algorithm at face value. Even when its supposedly enhanced using QAOAsomething theres currently no support forits questionable whether it provides any performance boost.
All told, this is one of the most actively misleading quantum computing papers Ive seen in 25 years, and Ive 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 isnt the first time Ive encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shors algorithm, should somehow rub off onto quantum optimization heuristics that embody none of the actual insights of Shors algorithm, as if by sympathetic magic. Page: 1 2 Next → reader comments 36 with 0 posters participating Share this story Share on Facebook Share on Twitter Share on Reddit Dan Goodin Dan is the Security Editor at Ars Technica, which he joined in 2012 after working for The Register, the Associated Press, Bloomberg News, and other publications. Find him on Mastodon at: https://infosec.exchange/@dangoodin Email dan.goodin@arstechnica.com Advertisement Channel Ars Technica ← Previous story Related Stories Today on Ars