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.”
Update: In an email sent after this post went live, one of the Fujitsu researchers, Tetsuya Izu, senior director of data & security research, wrote:
During the trials, we used a Shor’s algorithm and created a program to generate quantum circuits. As a next step, we used this program to generate quantum circuits for composite numbers of 9 bits and smaller, and checked actual operations (integer factorization). We then evaluated the necessary computational resources of the above mentioned quantum circuits and made estimations for the case of integer factorization of 2,048 bits composite numbers. For this reason, our estimation also uses logical qubits. We are still finalizing the research paper and unfortunately cannot provide it today. We will share the paper with you as soon as it is available.
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 wiggle 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.”
