Computer security experts were struggling this week to assess a startling claim by Chinese researchers that they have found a way to break the most common form of online encryption using the current generation of quantum computers, years before the technology was expected to pose a threat.
The method, outlined in a
published in late December, could be used to break the RSA algorithm that underpins most online encryption using a quantum machine with only 372 qubits — or quantum bits, a basic unit of quantum computing — according to the claims from 24 researchers from a number of academic bodies and state laboratories.
IBM has already said that its 433 qubit Osprey system, the most powerful quantum computer to have been publicly unveiled, will be made available to its customers early this year.
If correct, the research would mark a significant moment in the history of computer security, said Roger Grimes, a computer security expert and author.
“It’s a huge claim,” he said. “It would mean that governments could crack other governments secrets. If it’s true — a big if — it would be a secret like out of the movies, and one of the biggest things ever in computer science.”
Other experts said that while the theory outlined in the research paper appeared sound, trying to apply it in practice could well be beyond the reach of today’s
technology.
“As far as I can tell, the paper isn’t wrong,” said Peter Shor, the Massachusetts Institute of Technology scientist whose 1994 algorithm proving that a quantum machine could defeat online encryption helped to trigger a research boom in quantum computing. Shor’s method requires machines with many hundreds of thousands, or even millions, of qubits, something that many experts believe is a decade or more away.
Shor added, however, that the Chinese researchers had “failed to address how fast the algorithm will run”, and said that it was possible it “will still take millions of years”. He said: “In the absence of any analysis showing that it will be faster, I suspect that the most likely scenario is that it’s not much of an improvement.”
The latest research paper is the second time in less than a year that the field of computer security has been jolted by claims that online encryption was in imminent danger of being broken. German mathematician Claus-Peter Schnorr published an algorithm last year that he said was a far more efficient way to factor large prime numbers — central to breaking the RSA code — potentially putting it within reach of traditional, or “classical” computers. But it turned out that Schnorr’s technique could not be scaled up to work as needed to challenge the RSA algorithm.
The latest research paper claims to make up for the gap in Schnorr’s research by using a quantum computer to speed up the part of the calculation he was unable to solve. It highlights the use of hybrid techniques that combine quantum and classical systems, the current focus of much of the work that is going on to find practical uses for quantum machines.
The Chinese researchers said they had used their algorithm to factor a number with 48 bits on a quantum computer with 10 qubits, but that they had not had the chance to try to scale it up to work on a much bigger system.
Computer security expert Bruce Schneier said that the paper had left open the question of whether the technique would work in practice.
“We have no empirical proof that the [new] quantum algorithm overcomes the Schnorr scaling problem,” he said. “There’s no reason to believe it won’t — but there’s no reason to believe it will.” He added that quantum systems had already reached the scale outlined by the researchers, meaning that their claims could be put to the test very soon.
Even if the research claim proved unfounded, Schneier said it highlights a race to find a way to break encryption using quantum computers far earlier than many had expected. “The betting is, as in all these cases, breaking RSA won’t work,” he said. “But some day that bet will be wrong.”
