Quantum Decryption Breakthrough? Not So Fast

A research paper that claimed a quantum breakthrough that could "challenge RSA-2048" encryption received significant attention in the past week, followed by significant criticism as experts weighed in.

The paper, titled "Factoring integers with sublinear resources on a superconducting quantum processor," proposes a general-purpose quantum algorithm combining two methods of optimization to speed up the process of discovering the prime factors of a given number — an operation that is central to traditional public-key encryption. 

The combination of a classical approach along with a quantum approach could allow RSA 2,048-bit public-key encryption to be decrypted much faster and would only require a 372-physical-qubit computer, according to the paper.

While the paper frames the research as a significant breakthrough — computer scientists love algorithms that reduce problems to sublinear time — quantum-computing experts began casting doubts on the two-dozen authors' claims in the past week. Scott Aaronson, the director of the University of Texas at Austin's Quantum Information Center, summarizes his opinion with three words: "No. Just No."

"The paper claims … well, it’s hard to pin down what it claims, but it’s certainly given many people the impression that there’s been a decisive advance on how to factor huge integers, and thereby break the RSA cryptosystem, using a near-term quantum computer," he says.

Quantum computers take advantage of the unique physics of quantum systems to probabilistically solve problems that would take exponential time and effort on the classical digital computers that the industry uses today. For information security professionals, quantum computers threaten to unravel the complex mathematics on which relies some widely used encryption, such as public key crypto-systems and elliptic curve cryptography.

To address the future threat of quantum computers, the National Institute of Standards and Technology (NIST) has developed post-quantum encryption algorithms that are just as difficult for quantum systems to decrypt.

A Quantum Leap?

With private industry investing significantly in various promising technologies, quantum computers have become much more capable. In November, for example, IBM announced the largest quantum computer to date at 433 qubits, a trebling of capability in a year.

The threat, however, remains some ways off, experts say.

"The theoretical ability of a quantum computer to perform ultrafast factorization of giant integers and thus match keys for a number of asymmetric crypto-algorithms — including RSA encryption — has long been known," cybersecurity firm Kaspersky said in a blog post this week. "So far, all experts have agreed that a quantum computer large enough to crack RSA would probably be built no sooner than in around a few dozen decades."

Given those expectations, the claims of the researchers from various academic institutions in China, if proved out, would have been a breakthrough. The researchers showed that their approach worked on a smaller problem on a 10-qubit computer, but Aaronson and others point out that the optimization techniques — known as Schnorr's algorithm and the Quantum Approximate Optimization Algorithm (QAOA) — on which the researchers relied remain unproven.

The researchers should demonstrate their technique by finding some of the larger primes in the RSA Factoring Challenge, a contest created in the early 1990s as a way to test new decryption algorithm, well-known cryptographer Bruce Schneier, now chief of security architecture at decentralized data security firm Inrupt, wrote in a blog poston the paper .

"Several times a year, the cryptography community received 'breakthroughs' from people outside the community," Schneier wrote. "In general, the smart bet is on the new techniques not working. But someday, that bet will be wrong. Is it today? Probably not."

Paper Treated "Surprisingly Seriously"

The paper claims that its approach is the least resource-intensive for the specific tasks involving factorization and that a physical 372-qubit computer could "challenge" RSA-2048. The researchers applied the technique to factoring 11-bit, 26-bit, and 48-bit integers.

Yet they concluded the paper on a tentative note.

"It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA," the authors stated in their conclusion.

Other quantum experts accused the researchers of burying the lead, producing "one of the most actively misleading quantum computing papers (in 25 years)," according to UT Austin's Aaronson.

"It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr's algorithm on your laptop," Aaronson says. "And if the latter were able to break RSA, it would’ve already done so."

Yet information security professionals should still expect a future where quantum computers pose a significant threat for pre-quantum encryption. While the Chinese research may not threaten information security at present, it will likely only be a matter of time before reasonable resources could yield encryption keys, as sustained and intensive research into breaking RSA or ECC continues, Michele Mosca, co-founder and CEO of evolutionQ, stated in an analysis of the paper.

"[W]e shouldn't procrastinate in moving along the complex migration to quantum-safe cryptography, including replacing RSA and ECC with standardized post-quantum algorithms," he said. "Further, new methods might also lead to advances in breaking the post-quantum algorithms, so we must also be ready to respond to this in a pragmatic way."