A team of Chinese researchers has unveiled a technique that could theoretically decipher the most common methods used to ensure digital privacy using a rudimentary quantum computer.
The researchers report that the technique worked in small-scale demonstrations, but other experts are skeptical that the procedure can be scaled up to beat regular computers. Yet they warn that a paper posted to the arXiv repository late last month is a reminder of online privacy vulnerabilities.
Quantum computers are known to be a potential threat to current cryptographic systems, but the technology is still in its infancy. Researchers typically estimate that it will be years before quantum computers can crack cryptographic keys (strings of characters used in cryptographic algorithms to protect data) faster than ordinary computers. increase.
In the 1990s, researchers realized that quantum computers could take advantage of peculiarities in physics to perform tasks that seemed beyond the scope of “classical” computers. In 1994, mathematician Peter Scholl, now at the Massachusetts Institute of Technology in Cambridge, showed how to apply the phenomenon of quantum superposition to explain the ability of atomic-sized objects to exist in multiple combinations of states simultaneously. rice field. —and quantum interference is analogous to the way waves in a pond add or cancel each other, analogous to factoring integers into prime numbers.
Shore’s algorithm outperforms conventional computers in cracking cryptosystems based on large prime numbers, called Rivest-Shamir-Adleman (RSA), after the initials of its inventors, and other common cryptographic techniques. Exponentially faster. Protect your online privacy and security today. But implementing Shore’s technology would require a much larger quantum computer than the available prototypes. The size of a quantum computer is measured in quantum bits or qubits. Researchers say it could take him over a million qubits to crack RSA. The largest quantum machine currently available, the Osprey chip, unveiled by his IBM in November, has 433 qubits.
fresh approach
Shijie Wei and collaborators at the Beijing Academy of Quantum Information Science took another approach to defeating RSA, based on Schnorr’s algorithm instead of Shor’s. 1990s. Schnorr’s algorithm was designed to run on classical computers, but Wei’s team moved parts of the process to quantum computers using a procedure called the Quantum Approximate Optimization Algorithm (QAOA). Implemented.
In this paper, which has not yet been peer-reviewed, the authors claim their algorithm can crack strong RSA keys (over 600 decimal digits) using just 372 qubits.by email to Nature On behalf of all the authors, Guilu Long, a physicist at Tsinghua University in China, said that having many qubits is not enough and that current quantum machines are still error-prone and that such large I warned you that you can’t successfully perform large scale calculations. “Simply increasing the number of qubits without reducing the error rate will not help,” he said.
Chao-Yang Lu, a physicist building quantum computers at the University of Science and Technology of China in Hefei, who was not involved in the project, said that running the QAOA algorithm on such a small machine would require 372 qubits. Each said they would need it. 99.9999% of the time it works without errors. State-of-the-art qubits barely reach 99.9% accuracy.
The team demonstrated the technique on a 10-qubit quantum computer to factorize the more manageable 15-digit numbers 261,980,999,226,229. (Divided into two prime numbers, such as 15,538,213 × 16,860,433.) This is the largest number ever factored using quantum computers, according to the researchers, but the cryptography used in modern web browsers Much smaller than a key.
controversial paper
The problem is that no one knows if QAOA will make prime factorization of large numbers faster than running Schnorr’s classical algorithm on a laptop. “It should be pointed out that the quantum speedup of the algorithm is unknown,” the authors write. In other words, Shor’s algorithm is guaranteed to break encryption efficiently when (and if) a sufficiently large quantum computer becomes available, but optimization-based technique can be run on a much smaller machine, but may never complete the task.
Michele Mosca, a mathematician at the University of Waterloo in Canada, also points out that QAOA is not the first quantum algorithm known to be able to factor integers using a small number of qubits. In 2017 he and his collaborators wrote one. So the researchers already knew that nothing fundamental would require a very large quantum computer to factor.
Other researchers complain that the latest paper may be correct, but the warning about speed only appears at the end of the paper. Scott Aaronson, quantum computing theorist at the University of Texas at Austin In his blog, he said:
In an email, Long said he and his collaborators plan to change the paper and move the warning to a higher position. “We welcome peer review and communication with scientists around the world,” the statement added.
Even if Schnorr-based technology doesn’t destroy the internet, quantum computers could eventually do so by running Shor’s algorithms. Security researchers are busy developing a number of alternative cryptosystems that are considered less likely to succumb to quantum attacks, called post-quantum or quantum secure. But researchers may in the future discover better quantum algorithms that beat these systems, with disastrous consequences.
“The trust in digital infrastructure will collapse,” says Mosca. “We suddenly switched from managing quantum-safe transitions with technology lifecycle management to crisis management,” he adds. “No matter how you slice it, it won’t be clean.”
This article is reproduced with permission and was first published on January 6, 2023.
