Quantum Computing and the Threat of Unbreakable Encryption

Monday - October 9 2023, 02:57 UTC - 1 year ago

Computer scientists have discovered a new algorithm which could reduce the number of qubits required to crack encryption. Thanks to quantum computing, cracking encryption with prime factoring is simple. Today's quantum computers are unable to do it, but with advances in quantum computing the algorithm created by Oded Regev could reduce the number of qubits needed to crack encryption. Current estimates place a 1,024-bit key taking a quantum computer running for 12 hours to crack.

Despite all the hype around quantum computing, there are still significant question marks around what quantum computers will actually be useful for. There are hopes they could accelerate everything from optimization processes to machine learning, but how much easier and faster they’ll be remains unclear in many cases. 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 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 n2. Regev’s approach would only require n1.5 gates because it searches for prime factors by carrying out a statistical test on the size of the number.