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.
“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 don’t know for how much longer, is they’re 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 don’t 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 Shnorr’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 authors who devised Schnorr’s 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 Shnorr’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.”
In geological time, yes; in our lifetime, no
On Tuesday, Japanese technology company Fujitsu published a press release that provided further reassurance that the cryptocalypse isn’t nigh. Fujitsu researchers, the press release claimed, found that cracking an RSA key would require a fault-tolerant quantum computer with a scale of roughly 10,000 qubits and 2.23 trillion quantum gates, and even then, the computation would require about 104 days.
Attempts to obtain the research weren’t immediately successful, and Fujitsu researchers weren’t available by this story’s publication. That makes it impossible for fellow researchers to know precisely what the findings are or how significant they are.
“For example, when [the Fujitsu researchers] say 10,000 qubits in the press release, do they mean logical or physical qubits?” Samuel Jaques, a doctoral student at the University of Cambridge, wrote in an email. “In my view, the best estimate for quantum factoring is still [Craig] Gidney and [Martin] Ekerå from 2020, who estimate that factoring RSA-2048 would need 20 million physical qubits and 8 hours. If Fujitsu’s result drops the physical qubit count from 20 million to 10,000, that’s a huge breakthrough; if instead they need 10,000 logical qubits, then that’s much more than Gidney and Ekerå so I would need to check carefully to see why.”
That leads us back to the Enigma Conference and Garfinkel, who, like Jaques, said the Gidney and Ekerå findings are the best-known estimate for the breaking of RSA. Asked to respond to the oft-repeated statement that humanity is at the precipice of a large quantum computer, Garfinkel responded:
“If by large-scale you mean something that’s big enough to crack an RSA key, what do you mean humanity is on the precipice? In geological time we certainly are. In terms of the duration of the republic, sure. But in our lifetimes?”
Even when the day comes that there’s a quantum computer with the power envisioned by Gidney and Ekerå, the notion that RSA will fall in one stroke is misleading. That’s because it would take this 20 million-qubit quantum system eight hours in constant superposition to crack a single encryption key. That would certainly be catastrophic since someone might be able to use the capability to cryptographically sign malicious updates with a Microsoft or Apple key and distribute them to millions of people.
But even then, the scenario that nation-states are storing all encrypted communications in a database and will decrypt them all in bulk once a quantum computer becomes available is unrealistic, given the number of keys and the resources required to crack them all.
Over the past five years, the National Institute of Standards and Technology has run a search for new cryptographic algorithms that aren’t vulnerable to Shor’s algorithm. The process is far from finished. Last year, a candidate that had made it to the fourth round was taken out of the running after it fell to an attack that used only classical computing.
Once a post-quantum replacement is named, Garfinkel warned, “There’s going to be this mad rush to sell new things to the government so the government can immediately adopt these new algorithms. There’s just so much money to be made selling things to the government.”
Despite his insistence that the world is still decades away from being able to crack an RSA key, Garfinkel left himself wiggling room. At the same time, he said too many people focus on the risk posed by Shor’s algorithm without considering the possibility that RSA could just as easily fall from other factorization attacks posed by classical computers.
“If I was at CISA [Cybersecurity and Infrastructure Security Agency], I wouldn’t feel the need to say, ‘Don’t worry, it’s decades away’ only to risk the entire security of the United States,” he said. “But maybe we shouldn’t be moving to just post-quantum algorithms. Maybe we should be using the post-quantum algorithms and RSA in parallel because there might be a problem with the post-quantum algorithms.”