Heuristic Search for Nonlinear Substitutions for Cryptographic Applications

Heuristic algorithms are used to solve complex computational problems quickly in various computer applications. Such algorithms use heuristic functions that rank the search alternatives instead of a full enumeration of possible variants. The algorithm selects, at each iteration, an alternative with the best value for the heuristics. In this paper, we investigate the complex computational problem of finding highly nonlinear substitutions (S-boxes) in the space of 8-bit permutations. The generation of S-boxes is an important field of research, since nonlinear substitutions are widely used in various cryptographic applications. For instance, S-boxes in symmetric ciphers are responsible for cryptographic strength to linear, differential, algebraic, and other types of cryptanalysis. We propose new heuristics in the form of a cost function, calculated with the Walsh-Hadamard transform. We use the Hill Climbing Algorithm to find highly nonlinear substitutions. Our experiments demonstrate that the new heuristics give good results – it takes about 80,000 iterations of the algorithm to generate 8-bit S-boxes with a nonlinearity of 104. For the optimized parameters, the number of iterations of the algorithm is comparable to the best known results, which confirms the significance and value of the research.