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%.

Generation of Nonlinear Substitutions by Simulated Annealing Algorithm

Frontoni E.;
2023-01-01

Abstract

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%.
2023
MDPI
Internazionale
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11393/325864
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 4
social impact