14.12.2022 change 14.12.2022

Cryptologists tackle possible attacks on ciphers

Credit: WAT Credit: WAT

Can quantum annealing be used to attack lightweight ciphers used in the Internet of Things? Currently existing quantum computers are not sufficiently large to break all the currently used classical public key algorithms, explain cryptologists from the Military University of Technology.

The university informs on its website that each of us uses the Internet of Things everyday. This system allows devices to independently connect to computer networks and process data using special sensors. Data sent using these devices must be secure. Cryptographic algorithms called lightweight ciphers have been developed for this purpose.

Around the world, researchers explore the possibility of using quantum computers for attacks on ciphers. Scientists from the Institute of Mathematics and Cryptology of the Faculty of Cybernetics of the Military University of Technology focused on lightweight block algorithms.

In their paper, Elżbieta Burek and Dr. Michał Wroński analysed the structure of the SPECK lightweight cipher. They checked the possibilities of describing it using a system of multivariable polynomial equations in such a way that the problem solved by quantum annealing was as small as possible.

BEFORE SPECIAL-PURPOSE QUANTUM COMPUTER IS DEVELOPED

“A well-known quantum algorithm that can be used for the cryptanalysis of symmetric ciphers is the Grover algorithm. Grover's algorithm attack consists in a full search. A quantum implementation of a given cipher is used. The existence of this attack reduces the security of symmetric ciphers,” explain the scientists from the Military University of Technology.

They explain that this attack is designed for general-purpose quantum computers. Currently, such computers do not have sufficient resources to carry out this attack. Therefore, a special-purpose quantum computer using quantum annealing is gaining more and more interest. Its resources are much greater.

The researchers proposed to change the scope of the round, compared to the round described in the official documentation. Thanks to this approach, the problems obtained for the SPECK cipher are even half as small as those for the AES cipher with the same key length. This means that quantum annealing algebraic attacks against the SPECK cipher should be much more efficient than with the AES cipher.

The authors emphasise that the computational complexity of solving problems using quantum annealing has not yet been fully explored. Nevertheless, there are some estimates based on heuristic methods, according to which the solution to the problem requires the use of quantum annealing. Assuming a high complexity, an algebraic attack using quantum annealing can be a successful attack against 31 out of 34 rounds of SPECK128/256 cipher. This result is better than the best known classical attack against this variant of the SPECK  cipher.

PRACTICAL IDEA FOR A DISCRETE LOGARITHM

Once a sufficiently large quantum computer is built, all currently used classical public key algorithms will be broken. Scientists have known this for nearly 30 years, when Shor's algorithm was published.

In the case of Shor's algorithm, the best result so far has been factoring the number 21. As for the quantum solving of discrete logarithm problem in a finite field, no success has been achieved so far - neither with Shor's algorithm nor with any other method.

The first practical implementation of solving discrete logarithm problem in a finite field using quantum methods is presented in Dr. Michał Wroński's paper. The scientist of the Military University of Technology explains, the discrete logarithm problem in a finite field consists in finding the smallest positive integer y for which, and for g and h from this field, g to the power of y equals h. To explain it better, the researcher uses an example.

“Suppose we operate in an 11-element field. It is important that the number of elements is prime, and 11 is prime. Operating in an 11-element field means that we perform operations on the remainder of division by 11. Now, we want to find the smallest positive integer y for which in our field 4 to the power of y equals 9.

“So the idea is to find a y for which 4 raised to the y power when divided by 11 gives the remainder 9. The solution in this case is y equals 8. 'Anyone can check that 4 to the 8th power is 65,536, and that when divided by 11, gives the remainder equal to 9,” says Dr. Wroński, but adds that for sufficiently large fields, the problem becomes very difficult.

Quantum annealing computers currently have significantly more resources than general-purpose quantum computers. Therefore, it was obvious to try to use quantum annealing to solve a discrete logarithm problem in a finite field.

“We had to overcome some difficulties first. We knew how to solve systems of polynomial equations in finite fields using quantum annealing. In the case of the discrete logarithm in a finite field, the difficulty was to transform the exponential function into a polynomial function and then to a quadratic optimisation problem that has relatively few variables. Remember that the y is in the exponent. By using quantum annealing, we managed to solve the discrete logarithm problem in a 6-bit finite field,” the scientist explains.

Dr. Wroński emphasises that although the size of the solved problem does not seem to be too large, the obtained result is important from a theoretical point of view and may lead to more effective methods of quantum solving of  the discrete logarithm problem before it is possible with Shor's algorithm.

The ideas were presented at the International Conference on Computational Science. The main organizer of the conference was the University of Amsterdam. The Military University of Technology presented the papers in its Best Publications series.

PAP - Science in Poland, Karolina Duszczyk

kol/ kap/

tr. RL

Przed dodaniem komentarza prosimy o zapoznanie z Regulaminem forum serwisu Nauka w Polsce.

Copyright © Foundation PAP 2024