This new quantum computing algorithm could crack the world’s encryption faster than before

One of the most disruptive uses for a future quantum computer is the ability to crack over 70% of all today’s encryption which, depending on the number of qubits the system has and its accuracy rate, could take a few minutes or up to 8 hours for 2,048 Bit encryption. But now, even though being able to do this was originally dependent on the quantum computer having enough grunt – or Qubits – a new Artificial Intelligence (AI) algorithm could significantly lower the barrier.

Despite all the hype around quantum computing there are still significant question marks around what they’ll actually be used for. There are hopes they could accelerate everything from optimisation problems, such as supply chain and traffic optimisation, as well as drug discovery. But, how much easier and faster they’ll be in the end remains unclear even though recently a few of them have taken mere minutes to complete calculations that would have taken the world’s largest supercomputer billions of years to do.

One thing is pretty certain though - a sufficiently powerful quantum computer could render our leading cryptographic schemes worthless. While the mathematical puzzles underpinning them are virtually unsolvable by classical computers, they would be entirely tractable for a large enough quantum computer. That’s a problem because these schemes secure most of our information online.

The saving grace has been that today’s quantum processors are a long way from the kind of scale required, but that gap is closing fast. But now, according to a report in Science, New York University computer scientist Oded Regev has discovered a new algorithm that could reduce the number of qubits required substantially.

The approach essentially reworks one of the most successful quantum algorithms to date. In 1994, Peter Shor at MIT devised a way to work out which prime numbers need to be multiplied together to give a particular number - a problem known as prime factoring.

For large numbers, this is an incredibly difficult problem that quickly becomes intractable on conventional computers, which is why it was used as the basis for the popular RSA encryption scheme. But by taking advantage of quantum phenomena like superposition and entanglement, Shor’s algorithm can solve these problems even for incredibly large numbers.

That fact has led to no small amount of panic among security experts, not least because hackers and spies can hoover up encrypted data today and then simply wait for the development of sufficiently powerful quantum computers to crack it. And although post-quantum encryption standards have been developed, implementing them across the web could take many years.

It is likely to be quite a long wait though. Most implementations of RSA rely on at least 2048-bit keys, which is equivalent to a number 617 digits long. Fujitsu researchers recently calculated that it would take a completely fault-tolerant quantum computer with 10,000 qubits 104 days to crack a number that large.

However, Regev’s new algorithm, described in a pre-print published on arXiv, could potentially reduce those requirements substantially. Regev has essentially reworked Shor’s algorithm such that it’s possible to find a number’s prime factors using far fewer logical steps. Carrying out operations in a quantum computer involves creating small circuits from a few qubits, known as gates, that perform simple logical operations.

In Shor’s original algorithm, the number of gates required to factor a number is the square of the number of bits used to represent it, which is denoted as n². Regev’s approach would only require n^1.5 gates because it searches for prime factors by carrying out smaller multiplications of many numbers rather than very large multiplications of a single number. It also reduces the number of gates required by using a classical algorithm to further process the outputs.

In the paper, Regev estimates that for a 2048-bit number this could reduce the number of gates required by two to three orders of magnitude. If true, that could enable much smaller quantum computers to crack RSA encryption.

However, there are practical limitations. For a start, Regev notes that Shor’s algorithm benefits from a host of optimizations developed over the years that reduce the number of qubits required to run it. It’s unclear yet whether these optimizations would work on the new approach.

Martin Ekerå, a quantum computing researcher with the Swedish government, also told Science that Regev’s algorithm appears to need quantum memory to store intermediate values. Providing that memory will require extra qubits and eat into any computational advantage it has.

Nonetheless, the new research is a timely reminder that, when it comes to quantum computing’s threat to encryption, the goal posts are constantly moving, and shifting to post-quantum schemes can’t happen fast enough.