A team of scientists from MISIS University, RKTs and Sberbank conducted an in-depth analysis of the calculations used by researchers from China when simulating hacking a cryptosystem using a 400+ qubit quantum computer, and questioned their sensational conclusion about a revolution in cryptography. Russian scientists believe that their colleagues’ algorithm is not working due to “pitfalls” in the classical part and the complexity of implementing the quantum part. A representative of MISIS University reported this to CNews.
RSA is one of the first public key cryptosystems and is widely used for secure data transmission. Most public key cryptosystems currently in use are believed to be secure against attacks via conventional high-power computers, but not via quantum ones.
In December 2022, scientists from China published a paper in which they reported that they were able to factorize a 48-bit number by simulating hacking the RSA algorithm using a 10-qubit quantum computer. Based on the classical Schnorr factorization method, the authors use quantum acceleration to solve the shortest vector problem (SVP) in a lattice of small dimension - which allowed them to make the sensational statement that for factorization, that is, factorization of a large number, it requires fewer qubits than its length, as well as quantum circuits of less depth than previously thought. The researchers concluded that it was possible to crack a 2048-bit number using a computer with 372 physical qubits, although previously it was believed that 20 million were needed for this purpose. After IBM demonstrated the readiness of the 433-qubit Osprey quantum processor, many doubted the reliability of the modern asymmetric cryptography and post-quantum cryptosystems based on SVP computing.
Researchers from NUST MISIS, RKTs and Sber consider the conclusion about the possibility of hacking the 2048-bit RSA algorithm to be hasty.
“The Schnorr method does not have an accurate estimate of complexity. The main difficulty lies not in solving one shortest vector problem, but in correctly selecting and solving many such problems. It follows from this that this method is probably not suitable for RSA numbers of the sizes used in modern cryptography,” said Alexey Fedorov, director of the Institute of Physics and Quantum Engineering of NUST MISIS, head of the scientific group “Quantum Information Technologies” of the RCC.
Scientists emphasize that the method used by researchers from China provides only an approximate solution to the problem, which can be easily obtained for small numbers and small lattices, but is practically impossible for the real parameters of cryptosystems. Details of the study were published in one of the leading scientific journals, IEEE Access (Q1).
“Science moves forward not only through obtaining its own positive results, but also through scrupulous, critical analysis of the results of other research teams. We showed the pitfalls that arise in the algorithm proposed by Chinese colleagues for breaking modern encryption algorithms. However, even though a particular implementation may be ineffective, a quantum computer could still pose a serious information security risk in the future. Therefore, it makes sense now to consider ways to minimize these risks,” noted Albert Efimov, Ph.D. Sc., Head of the Department of Engineering Cybernetics, NUST MISIS, Vice-President-Director of the Research and Innovation Department of Sberbank.
Researchers claim that the method of scientists from China does not lead to instant cracking of existing cryptographic algorithms, but the emergence of new classical and quantum cryptanalysis algorithms is an inevitable step towards the introduction of post-quantum cryptography.
RSA is one of the first public key cryptosystems and is widely used for secure data transmission. Most public key cryptosystems currently in use are believed to be secure against attacks via conventional high-power computers, but not via quantum ones.
In December 2022, scientists from China published a paper in which they reported that they were able to factorize a 48-bit number by simulating hacking the RSA algorithm using a 10-qubit quantum computer. Based on the classical Schnorr factorization method, the authors use quantum acceleration to solve the shortest vector problem (SVP) in a lattice of small dimension - which allowed them to make the sensational statement that for factorization, that is, factorization of a large number, it requires fewer qubits than its length, as well as quantum circuits of less depth than previously thought. The researchers concluded that it was possible to crack a 2048-bit number using a computer with 372 physical qubits, although previously it was believed that 20 million were needed for this purpose. After IBM demonstrated the readiness of the 433-qubit Osprey quantum processor, many doubted the reliability of the modern asymmetric cryptography and post-quantum cryptosystems based on SVP computing.
Researchers from NUST MISIS, RKTs and Sber consider the conclusion about the possibility of hacking the 2048-bit RSA algorithm to be hasty.
“The Schnorr method does not have an accurate estimate of complexity. The main difficulty lies not in solving one shortest vector problem, but in correctly selecting and solving many such problems. It follows from this that this method is probably not suitable for RSA numbers of the sizes used in modern cryptography,” said Alexey Fedorov, director of the Institute of Physics and Quantum Engineering of NUST MISIS, head of the scientific group “Quantum Information Technologies” of the RCC.
Scientists emphasize that the method used by researchers from China provides only an approximate solution to the problem, which can be easily obtained for small numbers and small lattices, but is practically impossible for the real parameters of cryptosystems. Details of the study were published in one of the leading scientific journals, IEEE Access (Q1).
“Science moves forward not only through obtaining its own positive results, but also through scrupulous, critical analysis of the results of other research teams. We showed the pitfalls that arise in the algorithm proposed by Chinese colleagues for breaking modern encryption algorithms. However, even though a particular implementation may be ineffective, a quantum computer could still pose a serious information security risk in the future. Therefore, it makes sense now to consider ways to minimize these risks,” noted Albert Efimov, Ph.D. Sc., Head of the Department of Engineering Cybernetics, NUST MISIS, Vice-President-Director of the Research and Innovation Department of Sberbank.
Researchers claim that the method of scientists from China does not lead to instant cracking of existing cryptographic algorithms, but the emergence of new classical and quantum cryptanalysis algorithms is an inevitable step towards the introduction of post-quantum cryptography.
