Nonlinear substitutions or S-boxes are important cryptographic primitives of modern symmetric ciphers. They are designed to complicate the plaintext-ciphertext dependency. According to modern ideas, the S-box should be bijective, have high nonlinearity and algebraic immunity, low delta uniformity, and linear redundancy. These criteria directly affect the cryptographic strength of ciphers, providing resistance to statistical, linear, algebraic, differential, and other cryptanalysis techniques. Many researchers have used various heuristic search algorithms to generate random S-boxes with high nonlinearity; however, the complexity of this task is still high. For example, the best-known algorithm to generate a random 8-bit bijective S-box with nonlinearity 104 requires high computational effort—more than 65,000 intermediate estimates or search iterations. In this article, we explore a hill-climbing algorithm and optimize the heuristic search parameters. We show that the complexity of generating S-boxes can be significantly reduced. To search for a random bijective S-box with nonlinearity 104, only about 50,000 intermediate search iterations are required. In addition, we generate cryptographically strong S-Boxes for which additional criteria are provided. We present estimates of the complexity of the search and estimates of the probabilities of generating substitutions with various cryptographic indicators. The extracted results demonstrate a significant improvement in our approach compared to the state of the art in terms of providing linear non-redundancy, nonlinearity, algebraic immunity, and delta uniformity.

Cryptographic algorithms are used to ensure confidentiality, integrity and authenticity of data in information systems. One of the important areas of modern cryptography is that of symmetric key ciphers. They convert the input plaintext into ciphertext, representing it as a random sequence of characters. S-boxes are designed to complicate the input–output relationship of the cipher. In other words, S-boxes introduce nonlinearity into the encryption process, complicating the use of different methods of cryptanalysis (linear, differential, statistical, correlation, etc.). In addition, S-boxes must be random. This property means that nonlinear substitution cannot be represented as simple algebraic constructions. Random S-boxes are designed to protect against algebraic methods of cryptanalysis. Thus, generation of random S-boxes is an important area of research directly related to the design of modern cryptographically strong symmetric ciphers. This problem has been solved in many related works, including some using the simulated annealing (SA) algorithm. Some works managed to generate 8-bit bijective S-boxes with a nonlinearity index of 104. However, this required enormous computational resources. This paper presents the results of our optimization of SA via various parameters. We were able to significantly reduce the computational complexity of substitution generation with SA. In addition, we also significantly increased the probability of generating the target S-boxes with a nonlinearity score of 104.

In the realm of smart communication systems, where the ubiquity of 5G/6G networks and IoT applications demands robust data confidentiality, the cryptographic integrity of block and stream cipher mechanisms plays a pivotal role. This paper focuses on the enhancement of cryptographic strength in these systems through an innovative approach to generating substitution boxes (S-boxes), which are integral in achieving confusion and diffusion properties in substitution–permutation networks. These properties are critical in thwarting statistical, differential, linear, and other forms of cryptanalysis, and are equally vital in pseudorandom number generation and cryptographic hashing algorithms. The paper addresses the challenge of rapidly producing random S-boxes with desired cryptographic attributes, a task notably arduous given the complexity of existing generation algorithms. We delve into the hill climbing algorithm, exploring various cost functions and their impact on computational complexity for generating S-boxes with a target nonlinearity of 104. Our contribution lies in proposing a new cost function that markedly reduces the generation complexity, bringing down the iteration count to under 50,000 for achieving the desired S-box. This advancement is particularly significant in the context of smart communication environments, where the balance between security and performance is paramount.

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

Nonlinear substitutions (S-boxes) are an important component of modern symmetric cryptography algorithms. They complicate symmetric transformations and introduce nonlinearity in the input-output relationship, which provides resistance to some cryptanalysis techniques. S-boxes generation can be done in a number of ways. However, the most promising are heuristic techniques. On the one hand, the generated S-boxes look like random settings, which complicates algebraic cryptanalysis. On the other hand, heuristic search makes it possible to achieve high nonlinearity and δ-uniformity, which complicates linear and differential cryptanalysis. In this article, we will explore the simplest local search algorithm for generating S-boxes. To assess the efficiency of the algorithm, the concept of a track of a cost function is introduced in the article. We optimize the algorithm parameters and show that with the chosen parameters it is possible to reliably form S-boxes with nonlinearity 104.