Generation of Nonlinear Substitutions by Simulated Annealing Algorithm
Alexandr Kuznetsov,
Mikolaj Karpinski,
Ruslana Ziubina,
Sergey Kandiy,
Emanuele Frontoni,
Oleksandr Peliukh,
Olga Veselska,
Ruslan Kozak
Affiliations
Alexandr Kuznetsov
Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30/32, 62100 Macerata, Italy
Mikolaj Karpinski
Department of Computer Science and Automatics, University of Bielsko-Biala, 2 Willowa St., 43309 Bielsko-Biala, Poland
Ruslana Ziubina
Department of Computer Science and Automatics, University of Bielsko-Biala, 2 Willowa St., 43309 Bielsko-Biala, Poland
Sergey Kandiy
Department of Information and Communication Systems Security, Faculty of Comupter Science, V. N. Karazin Kharkiv National University, 4 Svobody Sq., 61022 Kharkiv, Ukraine
Emanuele Frontoni
Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30/32, 62100 Macerata, Italy
Oleksandr Peliukh
Department of Information and Communication Systems Security, Faculty of Comupter Science, V. N. Karazin Kharkiv National University, 4 Svobody Sq., 61022 Kharkiv, Ukraine
Olga Veselska
Department of Computer Science and Automatics, University of Bielsko-Biala, 2 Willowa St., 43309 Bielsko-Biala, Poland
Ruslan Kozak
Cyber Security Department, Ternopil Ivan Puluj National Technical University, 56 Ruska St., 46001 Ternopil, Ukraine
The problem of nonlinear substitution generation (S-boxes) is investigated in many related works in symmetric key cryptography. In particular, the strength of symmetric ciphers to linear cryptanalysis is directly related to the nonlinearity of substitution. In addition to being highly nonlinear, S-boxes must be random, i.e., must not contain hidden mathematical constructs that facilitate algebraic cryptanalysis. The generation of such substitutions is a complex combinatorial optimization problem. Probabilistic algorithms are used to solve it, for instance the simulated annealing algorithm, which is well-fitted to a discrete search space. We propose a new cost function based on Walsh–Hadamard spectrum computation, and investigate the search efficiency of S-boxes using a simulated annealing algorithm. For this purpose, we conduct numerous experiments with different input parameters: initial temperature, cooling coefficient, number of internal and external loops. As the results of the research show, applying the new cost function allows for the rapid generation of nonlinear substitutions. To find 8-bit bijective S-boxes with nonlinearity 104, we need about 83,000 iterations. At the same time, the probability of finding the target result is 100%.
