Quantum computers could crack a common data encryption technique once they have a million qubits, or quantum bits. While this is still well beyond the capabilities of existing quantum computers, this new estimate is 20 times lower than previously thought, suggesting the day encryption is cracked is closer than we think.
The widely used RSA algorithm relies on the fact that multiplying two prime numbers to generate a large encryption key is easy, but finding those original prime factors when all you have is the resulting key is extraordinarily difficult. It has long been known, however, that quantum computers will be capable of easily doing things that classical computers find very hard – like cracking RSA keys. A technique to do just that, known as Shor’s algorithm, was first developed in 1994.
at Google Quantum AI co-authored a in 2019 that estimated Shor’s algorithm could be used to crack RSA keys of a certain commonly used size – 2048 bits – in just 8 hours using a quantum computer with 20 million qubits. That would effectively allow the controller of such a machine to break into anyone’s email or bank account that had been secured using that technology, and could potentially give them access to state secrets. Now, Gidney has tweaked his method to slash the required size of the computer to less than a million qubits.
Advertisement
at the University of Oxford says Gidney is a leading name in the field and his new paper, which is yet to be peer-reviewed, will cause a stir. But he also expects it represents the last of the low-hanging fruit in terms of efficiency improvements to Shor’s algorithm.
“It’s come down and down and down over decades, but it’s still out there at quite a formidable scale,” says Leek. “There’s a possibility that people might improve the efficiency of this algorithm more – I’m sure that’s possible – but I suspect it’s probably going to become a bit more incremental now.”
“It’s a good reminder that we need to keep moving toward [post-quantum cryptography]. This new research doesn’t change our announced migration timelines, but we’re keeping an eye on things and will adjust if needed,” says at the National Institute of Standards and Technology (NIST). NIST has selected the next generation of encryption algorithms, which even quantum computers should not be able to crack. “Government and industry are already working on the transition,” he says.
, also at the University of Oxford, says that rather than relying on fundamentally new theory, Gidney’s gains come from hoovering-up various pieces of progress made in the field over the past six years in how to compile quantum algorithms into physical quantum circuits. Part of the reduction in qubit demands has been achieved by making a trade-off on computation time – rising from 8 hours in the 2019 paper to “less than a week”.
“There’s a whole parameter space there that you could explore, and he probably found one of the most compelling combinations of space and time, where both of those things look pretty reasonable,” says Kissinger. “Think about it like on your own computer: if you’ve got more memory, then you can sort of spread things out and you can do more things in parallel. Whereas if you have less space to work with, then it takes longer.”
One point in favour of RSA is that quantum computers are still far off Gidney’s requirements, with the current record sitting at just over 1000 qubits. But Leek says improvements in quantum computer error rates could see that million qubit requirement fall further.
“I wouldn’t expect it to be done the way that this paper describes, actually,” says Leek. “I would expect that more efficient error correction would be used and that we would be doing it on a device that doesn’t actually have a million physical qubits, but has a more innovative way to do the error correction, more efficiently implemented. It needs to come down by only a factor of four or five to get to this, so that’s extremely doable.”
Gidney didn’t respond to a request for comment before publication.
arXiv
