Russian scientists have refuted the sensational conclusion made by researchers about the possibility of breaking quantum algorithms

January 11Science, Science achievements, Science community

A team of scientists from the MISIS University, RQC, and Sber conducted a thorough analysis of the calculations used by researchers from Zhengzhou, Beijing, and Hangzhou institutions to simulate the breaking of a cryptosystem using a 350+ qubit quantum computer and questioned their sensational conclusion about a revolution in cryptography. Russian scientists believe that the colleagues’ algorithm is not functional due to some “pitfalls” in the classical part and the complexity of the quantum part’s implementation.

RSA is one of the first public-key cryptosystems and is widely used for secure data transmission. It is believed that most currently used public-key cryptosystems are protected from attacks by conventional powerful computers, but not by quantum computers. However, as believed breaking the modern version of the RSA algorithm would require tens of millions of qubits, which is far beyond the capabilities of the current generation of quantum computers.

In December 2022, scientists from China published an article stating that they had managed to factorize a 48-bit number, simulating the hacking of the RSA algorithm, using a 10-qubit quantum computer. Based on the classical Schnorr’s factoring method, the authors used quantum acceleration to solve the Shortest Vector Problem (SVP) of small dimensionality, which allowed them to make a sensational statement that it requires fewer qubits than its length and quantum schemes of lesser depth than previously thought to factorize a large number. Researchers concluded that it is possible to break a 2048-bit number using a computer with 372 physical qubits, although it was previously thought that 20 million qubits were needed for this purpose. After IBM announced a 433-qubit quantum processor Osprey, many doubted the reliability of modern asymmetric cryptography and post-quantum cryptosystems based on the SVP calculations.

Researchers from NUST MISIS, Russian Quantum Center, and Sberbank believe that the conclusion about the possibility of breaking the 2048-bit RSA algorithm is hasty.

“The Schnorr method’s complexity is hard to estimate precisely. The main difficulty lies not in solving a single shortest vector problem, but in correctly selecting and solving multiple problems. Other difficulties arise at the quantum level, where the use of the quantum approximate optimization algorithm requires additional analysis. Therefore, this method is probably not suitable for RSA numbers of such sizes used in modern cryptography,” said Aleksey Fedorov, Director of the Institute of Physics and Quantum Engineering at NUST MISIS, head of the scientific group “Quantum Information Technologies” at RQC.

Scientists emphasize that the method used by Chinese researchers provides only an approximate solution to the problem, which can be easily obtained for small numbers and small lattices but is practically impossible for real cryptosystem parameters. The details of the research were published in one of the leading scientific journals IEEE Access (Q1).

“Science advances not only through obtaining its positive results but also through scrupulous, critical analysis of the results of other research teams. We have shown the pitfalls that arise in the proposed algorithm for breaking modern encryption algorithms. However, despite the possibility of the specific implementation being inefficient, a quantum computer can still become a serious risk to information security in the future. Therefore, it makes sense to consider ways to minimize these risks now,” noted Albert Efimov, Ph.D., head of the Department of Engineering Cybernetics at NUST MISIS, Vice President and Director of the Research and Innovation Department at Sberbank.

The researchers claim that the method used by scientists from China does not lead to an instant breakthrough in existing cryptographic algorithms. However, the emergence of new classical and quantum cryptanalysis algorithms is an inevitable step towards implementing post-quantum cryptography.