Quantum-resistant cryptography is a new public key cryptography that can safely use cryptography technology in a quantum computing environment, and is securely resistant to all attacks by quantum computers.

A domestic research team has succeeded in developing a world-class quantum algorithm capable of attacking 'quantum-resistant cryptography', a new cryptographic system in the quantum computer era. It is expected to be a turning point not only for quantum computers but also for related industries such as mathematics and cryptography.

The Electronics and Telecommunications Research Institute (ETRI) announced on the 3rd that it has developed a world-class quantum algorithm that can effectively attack the linear noise problem, one of the key fundamental problems of quantum-resistant cryptography, together with domestic and international researchers from KIST, Seoul National University, Hanyang University, KIAS, and Imperial College London. A linear noise problem is a problem of finding a solution to a linear equation with errors, and the difficulty is determined by how few samples consisting of randomly selected inputs and outputs containing errors can be used to solve the problem.

In the early days of quantum computing research, it was predicted that existing cryptographic systems such as public key cryptography (RSA) would have difficulty maintaining security when quantum computers became practical due to the emergence of quantum factoring algorithms. Accordingly, a new cryptographic system called 'quantum-resistant cryptography (PQC)', which is expected to be safe from hacking using quantum computers, has emerged.

Quantum-resistant cryptography is a next-generation cryptography system that utilizes mathematical problems that are difficult even for quantum computers to solve. In order to solve this, qubit resources that increase exponentially with the size of the problem are required. Therefore, it has been considered impossible to attack even for quantum computers.

However, the research team developed a quantum algorithm that can attack quantum-resistant encryption with a relatively small quantum computer by utilizing the 'divide-and-conquer strategy' for the first time in the world. The divide-and-conquer strategy is a method of dividing the entire structure into small substructures and attacking them individually. It proved that exponential quantum gain is possible with only an appropriate level of quantum computing power. This means that the amount of resources required for calculation has decreased to a polynomial function, and it is usually classified as an easy problem if the amount of resources increases polynomially.

With this disclosure, the researchers were able to more specifically identify the conditions under which quantum resistance is invalidated. Accordingly, it is expected that the scope of application for next-generation cryptography research by companies, research institutes, and public institutions utilizing quantum technology will be clarified.

Park Sung-soo, head of ETRI’s Quantum Technology Research Group, said, “The results of this study are significant in that they show that quantum attack on quantum-resistant cryptography, which was previously thought to be impossible, is possible in principle.” He added, “However, in order to effectively attack quantum-resistant cryptography in practice, we need to secure more computational power for quantum computers.”

Professor Myung-Soo Kim of Imperial College, UK, who is the co-corresponding author of this paper, also said, “We have proven that linear problems with noise can be solved faster using quantum computers than with classical computers.” In particular, he said, “This is the first case of using the divide-and-conquer strategy in a quantum algorithm, and we expect that it will have a positive ripple effect as it is directly related to the reliability calculation of new cryptographic systems.”

ETRI stated that this research result does not mean that quantum computers have completely conquered quantum resistance, and added that continuous research is needed from the perspective of attacking and protecting quantum-resistant cryptography.

In the future, the research team plans to conduct additional research to optimize the computational resources of the entire problem-solving process, from the stage of generating and preparing quantum samples to the operation of the main algorithm, from the perspective of fault-tolerant quantum computing. Through this, they plan to verify the possibility of quantum attack on quantum-resistant cryptography from a more realistic perspective.

Meanwhile, this study was developed with support from the Ministry of Science and ICT's Quantum Computing Technology Development Project and the National IT Industry Promotion Agency's Quantum Cryptography Communication Integration and Transmission Technology Advancement Project, and the results were published in Quantum Science & Technology, a specialized academic journal on quantum information science and technology.