Are quantum computers about to break online privacy? – Nature.com
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.
Advertisement
You can also search for this author in PubMed Google Scholar
You have full access to this article via your institution.
A quantum computer at IBM’s Thomas J. Watson Research Center.Credit: Connie Zhou for IBM
A team of researchers in China has unveiled a technique that — theoretically — could crack the most commonly used types of digital privacy using a rudimentary quantum computer.
The technique worked in a small-scale demonstration, the researchers report, but other experts are sceptical that the procedure could scale up to beat ordinary computers at the task. Still, they warn that the paper, posted late last month on the arXiv repository1, is a reminder of the vulnerability of online privacy.
Quantum computers are known to be a potential threat to current encryption systems, but the technology is still in its infancy and researchers typically estimate that it will be many years until they can be faster than ordinary computers at cracking cryptographic keys.
Researchers realized in the 1990s that quantum computers could exploit peculiarities of physics to perform tasks that seem to be beyond the reach of ‘classical’ computers. Peter Shor, a mathematician now at the Massachusetts Institute of Technology in Cambridge, showed in 19942 how to apply the phenomena of quantum superposition and interference to factoring integer numbers into primes — the integers that cannot be further divided without a remainder.
Shor’s algorithm would make a quantum computer exponentially faster than a classical one at cracking an encryption system based on large prime numbers — called RSA after the initials of its inventors — as well as some other popular cryptography techniques, which currently protect online privacy and security. But implementing Shor’s technique would require a much larger quantum computer than the prototypes available. The size of a quantum computer is measured in quantum bits, or qubits; researchers say it might take a million or more qubits to crack RSA. The largest quantum machine available today — the Osprey chip announced in November by IBM — has 433 qubits.
Shijie Wei at the Beijing Academy of Quantum Information Sciences and collaborators took a different route to beat RSA, based not on Shor’s but on Schnorr’s algorithm — a process for factoring integer numbers devised by mathematician Claus Schnorr at Goethe University at Frankfurt, Germany, also in the 1990s. Schnorr’s algorithm was designed to run on a classical computer, but Wei’s team implemented part of the process on a quantum computer, using a procedure called quantum approximate optimization algorithm, or QAOA.
In the paper, which has not yet been peer-reviewed, they claim that it could break strong RSA keys — numbers with more than 600 decimal digits — using just 372 qubits. In an email to Nature on behalf of all the authors, Guilu Long, a physicist at Tsinghua University in China, cautioned that having many qubits is not enough, and that current quantum machines are still too-error prone to do such a large computation successfully. “Simply increasing the qubit number without reducing the error rate does not help.”
The team demonstrated the technique on a 10-qubit quantum computer to factor the more-manageable, 15-digit number 261,980,999,226,229. (It splits into two primes, as 15,538,213 x 16,860,433.) The researchers say this is the largest number yet to have been factored with the aid of a quantum computer — although it is much smaller than the encryption keys used by modern web browsers.
The trouble is, no one knows if the QAOA makes factoring large numbers faster than just running Schnorr’s classical algorithm on a laptop. “It should be pointed out that the quantum speedup of the algorithm is unclear,” write the authors. In other words, while Shor’s algorithm is guaranteed to break encryption efficiently when (and if) a large-enough quantum computer becomes available, the optimization-based technique could run on a much smaller machine, but it might never finish the task.
Michele Mosca, a mathematician at the University of Waterloo in Canada, also points out that the QAOA route is not the first quantum algorithm known to be able to factor whole numbers using a small number of qubits. He and his collaborators described3 one in 2017. So, researchers already knew that there is nothing fundamental that requires quantum computers to be very large to factor numbers.
Other researchers have complained that although the latest paper could be correct, the caveat regarding speed comes only at the very end of it. “All told, this is one of the most misleading quantum computing papers I’ve seen in 25 years,” blogged quantum computing theorist Scott Aaronson at the University of Texas at Austin.
In the email, Long says that he and his collaborators plan to change the paper and to move the caveat higher up. “We welcome the peer review and the communication with scientists around the world,” the statement added.
Even if the Schnorr-based technique won’t break the Internet, quantum computers could eventually do so by running Shor’s algorithm. Security researchers have been busy developing a number of alternative cryptographic systems that are seen as less likely to succumb to a quantum attack, called post-quantum or quantum-safe. But researchers might also discover better quantum algorithms in the future that beat these systems, with calamitous consequences.
“Confidence in digital infrastructures would collapse,” says Mosca. “We’d suddenly switch from managing the quantum-safe migration through technology lifecycle management to crisis management,” he adds. “It won’t be pretty any way you slice it.”
doi: https://doi.org/10.1038/d41586-023-00017-0
Yan, B. et al. Preprint at https://arxiv.org/abs/2212.12372 (2022).
Shor, P. W. Phys. Rev. A 52, R2493(R) (1995).
Article Google Scholar
Bernstein, D. J., Biasse, J.-F, & Mosca, M. in Post-Quantum Cryptography Lecture Notes in Computer Science (eds Lange, T. & Takagi, T.) Vol. 10346 (Springer, 2017).
Google Scholar
Download references
The race to save the Internet from quantum hackers
The quantum internet has arrived (and it hasn’t)
These ‘quantum-proof’ algorithms could safeguard against future cyberattacks
Driven quantum bits push computational limit
News & Views
Formation of robust bound states of interacting microwave photons
Article
Did physicists create a wormhole in a quantum computer?
News
Reply to: Climate versus tectonics as controls on river profiles
Matters Arising
AI bot ChatGPT writes smart essays — should professors worry?
News Explainer
Are ChatGPT and AlphaCode going to replace programmers?
News
Technische Universität Dresden (TU Dresden)
01069 Dresden, Germany
Francis Crick Institute
London, United Kingdom
Luxembourg Institute of Health (LIH)
Luxembourg, Luxembourg
The University of British Columbia (UBC)
Vancouver, Canada
You have full access to this article via your institution.
The race to save the Internet from quantum hackers
The quantum internet has arrived (and it hasn’t)
These ‘quantum-proof’ algorithms could safeguard against future cyberattacks
An essential round-up of science news, opinion and analysis, delivered to your inbox every weekday.
Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.
© 2023 Springer Nature Limited