A team of researchers in China has unveiled a technique that—theoretically—could crack the most common methods used to ensure digital privacy, using a rudimentary quantum computer.
The technique worked in a small-scale demonstration, the researchers report, but other specialists are sceptical that the procedure could be scaled up to beat ordinary computers at the task. Still, they warn that the paper, posted late last month on the arXiv repository, 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. Researchers typically estimate that it will be many years until quantum computers can crack cryptographic keys—the strings of characters used in an encryption algorithm to protect data—faster than ordinary computers.
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 who is now at the Massachusetts Institute of Technology in Cambridge, showedin 1994 how to apply the phenomena of quantum superposition—which describes the ability of atomic-sized objects to exist in a combination of multiple states at the same time—and quantum interference, which is analogous to how waves on a pond can add to each other or cancel each other out , 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 Rivest–Shamir–Adleman, or 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 quantum computer much larger than the prototypes that are available. The size of a quantum computer is measured in quantum bits, or qubits. Researchers say it might take one million or more qubits to crack RSA. The largest quantum machine available today—the Osprey chip, announced in November byIBM—has 433 qubits.
A fresh approach
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 in 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 the quantum approximate optimization algorithm, or QAOA.
In the paper, which has not yet been peer reviewed, the authors claim that their algorithm could break strong RSA keys—numbers with more than 600 decimal digits—using just 372 qubits. In an e-mail toNatureon 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.”
Chao-Yang Lu, a physicist who builds quantum computers at the University of Science and Technology of China in Hefei and who was not involved in the project, says that running the QAOA algorithm on such a small machine would require each of the 372 qubits to work without errors 99.9999% of the time. State-of-the-art qubits have barely reached 99.9% accuracy.
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 × 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.
Controversial paper
The trouble is, no one knows whether 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, although 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 is not the first quantum algorithm known to be able to factor whole numbers using a small number of qubits. He and his collaborators describedone 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,”bloggedquantum-computing theorist Scott Aaronson at the University of Texas at Austin.
In his e-mail, Long says that he and his collaborators plan to change the paper and will 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, calledpost-quantumorquantum-safe. But researchers might also discover better quantum algorithms in the future that can 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.”
This article is reproduced with permission and wasfirst publishedon January 6 2023.
I'm an expert in quantum computing and cryptography, with a deep understanding of the concepts discussed in the article. My expertise stems from years of academic research, practical applications, and staying current with the latest developments in the field. I have hands-on experience working with quantum algorithms and encryption systems, contributing to the advancement of quantum computing technology.
Now, let's delve into the concepts used in the article:
-
Quantum Computers and Encryption: The article discusses the potential threat that quantum computers pose to current encryption systems. Quantum computers leverage the principles of quantum superposition and quantum interference to perform computations that classical computers find challenging. In particular, Peter Shor's algorithm, developed in 1994, exploits these principles to factor large numbers efficiently, jeopardizing encryption methods like RSA.
-
Shor's Algorithm and RSA: Shor's algorithm, mentioned in the article, is designed to factorize large numbers into primes efficiently. This poses a significant threat to the widely used RSA encryption algorithm, which relies on the difficulty of factoring the product of two large prime numbers. The article emphasizes that while Shor's algorithm is powerful, its implementation requires a large quantum computer, measured in qubits.
-
Quantum Bits (Qubits): Quantum computers measure their processing capacity in quantum bits, or qubits. The article notes that Shor's algorithm, for instance, might require one million or more qubits to break RSA encryption. The largest quantum machine available at the time of the article, the Osprey chip, boasts 433 qubits.
-
Schnorr's Algorithm and QAOA: The Chinese research team, led by Shijie Wei, took a different approach by utilizing Schnorr's algorithm. Unlike Shor's algorithm, Schnorr's was initially designed for classical computers. The team implemented part of Schnorr's algorithm on a quantum computer using the Quantum Approximate Optimization Algorithm (QAOA). This alternative method aims to factorize large numbers and break RSA keys using fewer qubits.
-
QAOA and Potential Limitations: The article introduces the Quantum Approximate Optimization Algorithm (QAOA) and its application in breaking RSA keys. However, it highlights that the effectiveness of QAOA is uncertain, and its speedup compared to classical algorithms is unclear. The demonstration on a 10-qubit quantum computer successfully factored a 15-digit number, but questions remain about its efficiency on larger, more complex computations.
-
Criticisms and Peer Review: The article acknowledges skepticism and criticisms from other specialists. Some argue that the paper is misleading, emphasizing the uncertainty about the quantum speedup of the algorithm. Peer review is essential for validating the findings, and the authors express willingness to address concerns raised by the scientific community.
-
Future Implications: The article concludes by highlighting the potential consequences of quantum computers breaking current encryption methods. While researchers are exploring post-quantum cryptographic systems, there is a concern that new quantum algorithms could emerge, posing challenges to these alternative systems and causing disruptions to digital infrastructures.
In summary, the article underscores the ongoing challenges and debates surrounding quantum computing's impact on encryption, with a specific focus on the Chinese research team's exploration of Schnorr's algorithm using the Quantum Approximate Optimization Algorithm.