Research of Computational Complexity of Cost Functions in S-boxes Generation Problems

The generation of non-linear substitutions (S-boxes) is an important task in the design of cryptographic algorithms with a secret key. The properties of S-boxes determine the cryptographic strength of symmetric ciphers against various attacks, for example, linear and differential cryptanalysis. In addition, substitutions must be random in order to be resistant to algebraic cryptanalysis methods. Many authors explore the problem of generating random S-boxes. The most effective technique is heuristic search, which is based on the use of various cost functions (special heuristics). Heuristic search consists of iteratively modifying a randomly generated substitution. At each iteration, the value of the cost function is calculated, the search continues until a substitution is found that minimizes the cost function. In this article we explore several options for cost functions and evaluate the complexity of their calculation. We estimate the number of iterations required by the heuristic search to generate S-boxes with given cryptographic indicators as well as the computational complexity of generation taking into account the complexity of calculating the cost function.