Chinese researchers’ claimed quantum encryption crack looks unlikely
Briefly this week, it appeared that quantum computers might finally be ready to break 2048-bit RSA encryption, but that moment has passed.
The occasion was the publication of an academic paper by no less than two dozen authors affiliated with seven different research institutions in China.
The paper, titled “Factoring integers with sublinear resources on a superconducting quantum processor,” suggests that the application of Claus Peter Schnorr’s recent factoring algorithm, in conjunction with a quantum approximate optimization algorithm (QAOA), can break asymmetric RSA-2048 encryption using a non-fault tolerant (NISQ, or noisy intermediate scale quantum) quantum computer with only 372 physical quantum bits or qubits.
If true, this would be a significant development because there are already quantum computers that exceed that specification, like IBM’s 433-qubit Osprey.
The speculation has been that orders of magnitude more qubits, in conjunction with robust error correction at scale, may allow future quantum computers to run Peter Schor’s algorithm – not to be confused with the similarly named Schnorr – quickly, on very large numbers, thereby breaking RSA encryption.
In 2019, researchers published a paper [PDF] claiming that 2048-bit RSA integers could be factored in about eight hours … given a quantum computer with 20 million noisy qubits (meaning without the overhead of error correction and the like).
That’s a future the National Security Agency has been planning for since 2015, when it started public work on developing quantum-resistant encryption algorithms.
No one is quite sure when, or whether, that day will arrive. When we considered quantum crypto-cracking in 2019, University of Chicago computer science professor Diana Franklin suggested, “It is possible that Shor’s algorithm could be implemented in the next 15 years,” while allowing predictions of this sort are notoriously difficult to get right.
Nonetheless, the quantum gold rush is on. The US and China, along with Europe, the UK, and other countries in Asia are all working to lead the nascent quantum computing industry and to avoid being caught flat-footed if a breakthrough occurs.
Let’s look at the facts
Public (asymmetric) key cryptography secures the financial system via digital signatures and certificates. Being able to forge those with a sufficiently capable quantum system would be problematic to say the least. Symmetric cryptographic algorithms, like AES-256, are considered to be more resistant to quantum computers, so the application of Grover’s algorithm [PDF] in a quantum system isn’t expected to alter the cryptographic landscape.
The paper from 24 researchers in China might have remained a matter for those well-versed in advanced mathematics, cryptography, and quantum computing – a fairly small set of people – but for the fact that it got noticed by cryptographer Bruce Schneier.
“This is something to take seriously,” he wrote in his blog on January 3rd, 2023. “It might not be correct, but it’s not obviously wrong.”
Schneier did not take a position on the paper, but the following day The Financial Times took notice in an article titled, “Chinese researchers claim to find way to break encryption using quantum computers.”
Evidently they haven’t.
Late that day, on January 4, Scott Aaronson, chair of computer science at The University of Texas at Austin, and director of its Quantum Information Center, offered a rebuttal with a succinct three word review of the paper: “No. Just No.“
Aaronson, among the more credible voices on such matters, hangs the researchers with their own caveat: “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA,” they wrote in their paper.
That’s a vast understatement, Aarsonson argues, because it has yet to be demonstrated that Schnorr’s algorithm, even with QAOA, will work faster on a quantum device than a classical computer. And if a current laptop could break RSA, doing so on a quantum computer would be unnecessary.
“All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many,” he wrote. ®
READ MORE HERE