Searching for an Efficient System of Equations Defining the AES Sbox for the QUBO Problem

• Autorzy: Burek Elżbieta , Mańk Krzysztof , Wroński Michał

Identyfikatory

DOI

10.26636/jtit.2023.4.1340

• Języki publikacji: EN

Abstrakty

EN

The time complexity of solving the QUBO problem depends mainly on the number of logical variables in the problem. This paper focuses mainly on finding a system of equations that uniquely defines the Sbox of the AES cipher and simultaneously allows us to obtain the smallest known optimization problem in the QUBO form for the algebraic attack on the AES cipher. A novel method of searching for an efficient system of equations using linear-feedback shift registers has been presented in order to perform that task efficiently. Transformation of the AES cipher to the QUBO problem, using the identified efficient system, is presented in this paper as well. This method allows us to reduce the target QUBO problem for AES- 128 by almost 500 logical variables, compared to our previous results, and allows us to perform the algebraic attack using quantum annealing four times faster.

Słowa kluczowe

EN

AES Sbox; cryptanalysis; minimal equation system for Sbox; quantum annealing; QUBO

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2023
• Tom: nr 4
• Strony: 30--37
• Opis fizyczny: Bibliogr. 7 poz., rys., tab., wykr.

Twórcy

autor

Burek Elżbieta

• Institute of Mathematics and Cryptology Faculty of Cybernetics Military University of Technology, Warsaw, Poland

• https://orcid.org//0000-0003-2937-0833

autor

Mańk Krzysztof

• Institute of Mathematics and Cryptology Faculty of Cybernetics Military University of Technology, Warsaw, Poland

• https://orcid.org//0000-0002-5048-9049

autor

Wroński Michał

• Cybersecurity Expert Department of Cryptology NASK National Research Institute, Warsaw, Poland

• https://orcid.org/0000-0002-8679-9399

Bibliografia

• [1] P. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”, IEEE Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, USA, 1994 (https://doi.org/10.1109/SFCS.1994.365700).
• [2] C.H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and Weaknesses of Quantum Computing”, SIAM Journal on Computing, vol. 26, no. 5, pp. 1510– 1523, 1997 (https://doi.org/ 10.1137/S0097539796300933).
• [3] L.K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search”, Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 212–219 , 1996 (https://doi.org/ 10.1 145/237814.237866).
• [4] E. Burek, M. Wronski, K. Mank, and M. Misztal, “Algebraic Attacks on Block Ciphers Using Quantum Annealing”, IEEE Transactions on Emerging Topics in Computing, vol. 10, no. 2, pp. 678– 689, 2022 (https://doi.org/10.1109/TETC.2022.3143152).
• [5] I.G. Rosenberg, “Reduction of Bivalent Maximization to the Quadratic Case”, Cahiers du Centre d’Etudes de Recherche Operationnelle, vol. 17, pp. 71–74, 1975.
• [6] N.T. Courtois and J. Pieprzyk, “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations”, Lecture Notes in Computer Science, vol. 2501, 2002 (https://doi.org/ 10. 1007/3- 540- 36178- 2_ 17).
• [7] A.I. Pakhomchik, V.V. Voloshinov, V.M. Vinokur, and G.B. Lesovik, “Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis”, Algorithms, vol. 15, no. 2, art. no. 33, 2022 (https://doi.org/0.3390/a15020033).