A group of researchers has claimed that quantum computers can now crack the encryption we use to protect emails, bank accounts and other sensitive data. Although this has long been a theoretical possibility, existing quantum computers weren’t yet thought to be powerful enough to threaten encryption.
However, security experts have expressed doubt about the new claim, saying that although the code-breaking technique appears valid, there is no reason to expect it could crack encrypted data in a practical timescale or that current quantum hardware is even reliable enough to run it.
Modern encryption algorithms are based on mathematical problems deemed too hard to be cracked in a reasonable time, even by the fastest ordinary computers available today. For example, the widely used RSA algorithm relies on the fact that multiplying two prime numbers to generate a large encryption key is easy, while finding those original prime factors when you only have the encryption key is very difficult.
Advertisement
But quantum computers can exploit the unusual properties of quantum physics to speed up some calculations, and will probably render current encryption techniques obsolete once the hardware is sufficiently powerful and accurate. A technique to find prime factors on a quantum computer, known as Shor’s algorithm, was first developed in 1994, but it is thought that cracking today’s encryption using this algorithm would require a computer with millions of qubits, or quantum bits – far larger than any in existence today.
Now, Bao Yan at the State Key Laboratory of Mathematical Engineering and Advanced Computing in Zhengzhou, China, and his colleagues have used a small quantum computer to calculate the prime factors of the number 261,980,999,226,229, which they say is a record for quantum computing. The team claims to have improved on the efficiency of Shor’s algorithm by building on work , who boldly said that it “destroys” RSA.
Schnorr’s work proved controversial because other researchers found that it rapidly loses efficiency for larger numbers, meaning it is no threat to practical RSA encryption, which today uses at least 2048-bit numbers, so called because they are 2048 digits long when written in binary.
But Yan and his colleagues have used a new method to factor 261,980,999,226,229 – a 48-bit number – with just 10 qubits, and estimate that they only need 372 qubits to break a 2048-bit number. Although the researchers didn’t have access to a large enough machine to test this, such devices do exist: for example, IBM has a quantum computer called Osprey that contains 433 qubits.
The researchers didn’t respond to a request for interview and their paper doesn’t mention how long their quantum computer took to crack the 48-bit number, or whether it was carried out faster than would be possible on an ordinary computer, where the record for factoring is an . They do, however, claim in their paper that their finding means that RSA encryption is at risk from even today’s small, error-prone and cumbersome quantum computers.
“If this is true, then indeed we’re in big trouble,” says , a cybersecurity consultant based in London and Brussels. He says the number of qubits needed to decrypt a 2048-bit number is probably much higher than 372, as “logical” qubits composed of several physical qubits are required to control errors. “So it’s not a viable attack for the next few years at least. However, if the results stand, it should be testable soon.”
at the US National Institute of Standards and Technology, which recently recommended encryption algorithms that should be safe from quantum computers, says the paper has no obvious mistakes, but should be carefully analysed.
“Cryptographers will be a bit sceptical until some review suggests this newer paper is promising, since it starts with the Schnorr paper,” he says. “One or two smart people I trust have read it and said they have doubts. It’s premature to say this threatens RSA-2048.”
at quantum computing start-up Orca ComputingĚýsays that more work will need to be done before it is known whether the new approach does genuinely find prime factors faster than previous methods, and whether it will scale to the large numbers involved in secure encryption. He says that although today’s quantum computers may have the number of qubits required in theory, they are too inaccurate to carry out the large calculations that would be needed and errors would accrue over time.
“You would just have gibberish by the end,” he says. “It is beyond the reach of current technology, but it’s not obvious that it’s wrong or something that needs to be just dismissed. I think it will probably galvanise the community.”
Reference:
