At the end of December 2022, a Chinese research team published a paper in which the scientists claimed that they had developed an algorithm that – theoretically – could already overcome the currently most common methods of protecting digital privacy with a rudimentary quantum computer. The technique works in a small demonstration, write the researchers in the still unchecked pre-publication.
Quantum computers are known as a potential threat to current encryption systems, but the technology is still in its infancy. Researchers estimate that it will be many more years before quantum computers can actually crack cryptographic keys – the strings used in an encryption algorithm to protect data – faster than ordinary computers. These include, for example, the RSA encryption developed in the 1970s, named after the names of its three inventors Rivest, Shamir and Adleman, as well as some other popular cryptography techniques currently used to protect privacy and security on the Internet.
Quantum computer and quantum bits
In the 1990s, researchers realized that quantum computers can take advantage of the special features of quantum physics to perform tasks that seem unreachable for "classic" computers. While the computers known to us expect bits and the conditions of one or zero, quantum computers use so-called quantum bits. Because the conditions of quantum bits overlap (superposition), they can be in the state of one or zero and also in the theoretically infinite number of conditions. Because several quantum bits can also be entangled, a quantum computer can perform countless calculation steps in parallel. A pioneer in this area was Peter Shor, a mathematician who today works at the Massachusetts Institute of Technology (with) in Cambridge: he showed how to use the phenomena of quantity overposition (the ability of objects in the size of atoms, in several conditions at the same time to exist) as well as the quantum interference (which is analogous to how waves can add up or wipe out waves) in order to factorize full numbers in prime numbers, i.e. to disassemble them into numbers that cannot be shared further.
Peter Shor's algorithm would enable a quantum computer to expect exponentially faster than a classic computer if it were about cracking a encryption system based on prime numbers such as RSA. In order to implement Peter Shor's approach, however, it would need a quantum computer that is much larger than the currently available prototypes. According to researchers, a million or more quBits were needed to overcome RSA encryption. The largest quantum chip called Osprey, which was presented by IBM in November 2022, has 433 qubits.
A new approach
Shijie Wei from the Beijing Academy of Quantum Information Sciences and his employees went a different way to beat RSA cryptography. They did not rely on Peter Shor's algorithm, but on an algorithm by the mathematics Claus Peter Schnorr, who developed him at the Goethe University in Frankfurt am Main in the 1990s. Claus Schnorrs Algorithm was developed for use on a classic computer; The Shijie Wei team, however, implemented part of it on a quantum computer and used a procedure called Qaoa (Quantum Approximate Optimization Algorithm).
In the publication, the authors state that their algorithm itself could crack strong RSA key with numbers of more than 600 decimal digits-with only 372 quBits. In an email to »Nature« in the name of all authors, Guilu Long, physicist at Tsinghua University in China, pointed out that it is not enough to have many quBITs, and that the current quantum computers are still too prone to errors in order to to successfully carry out such a large calculation. "Simply increase the number of qubits without reducing the error rate does not help."
According to Chao-Yang Lu, a physicist who builds quantum computers at the University of Science and Technology of China in Hefei and was not involved in the project, to run the QAOA algorithm on such a small quantum computer, each of the 372 qubits must work error-free in 99.9999 percent of the time; however, state-of-the-art qubits currently barely achieve 99.9 percent accuracy.
The team around Wei demonstrated the technology on a 10-qubit quantum computer, with which the 15-digit number 261 980 999 226 229 divided into two prime number factors, namely 15 538 213 and 16 860 433. The researchers say that this is the largest There is a number that has so far been factorized with the help of a quantum computer. However, it is much smaller than the cryptographic keys used by modern web browsers.
Controversial publication
The actual dilemma is: Nobody knows whether the Qaoa algorithm actually enables large numbers to be disassembled with the help of a quantum computer than the execution of Schnorr's classic algorithm on a laptop. "It must be pointed out that it is unclear whether the use of qubits accelerates the algorithm," the authors write. In other words: Even if Peter Shors Algorithm can guarantee the RSA encryption one day if a sufficiently large quantum computer is available, the technology based on optimization could also run on a much smaller machine-but the task may never end.
Michele Mosca, a mathematician at the University of Waterloo in Canada, also points out that QAOA is not the first known quantum algorithm that can decompose integers with a small number of qubits. He and his staff had already shown this in 2017. So the experts already know that quantum computers don't have to be very large in order to factor numbers.
Other researchers critically expressed themselves that the results of the Chinese researchers could be correct, but the reservation regarding the speed was only at the very end. "All in all, this is one of the most misleading works on quantum computers that I have seen in the past 25 years," writes quantum computer theorist Scott Aaronson from the University of Texas in Austin in a blog post.
In his e-mail to "Nature", Guilu Long explains that he and his collaborators plan to move the restrictive sentence further up. "We are looking forward to the peer review and appreciate the communication with scientists from all over the world," the statement continues.
Even if the technology based on Claus Schnorr will not crack the web encryption, quantum computers could do this at some point-if they perform Peter Shors algorithm. Security researchers have already developed a number of alternative cryptographic systems that are considered less susceptible to attacks by quantum computers and are referred to as "post quantum" or "quantum safe". But researchers could develop even better quantum algorithms in the future that could also beat these systems again - with possibly catastrophic follow.
"Trust in digital infrastructures would collapse," says Michele Mosca. "We would suddenly pass from a gradual manage that adapted to the respective technology," he adds. "That wouldn't be nice in any case."
