# Algorithm for Generating S-Boxes with Prescribed Differential Properties
## 1 Introduction  
A substitution box (_S-box_) is a principal component of a large class of symmetric ciphers. The main task of the S-box is to provide nonlinearity to the cipher design, creating a property called confusion [1]. From the mathematical point of view, a cryptographic \(n\times m\) S-box is a vectorial Boolean function \(S:\mathbb{Z}_{2}^{n}\rightarrow\mathbb{Z}_{2}^{m}\), which fulfills specific criteria. We refer the reader to [2] for a more thorough study of Boolean functions used in cryptography. We can evaluate a vectorial Boolean function with respect to some S-box criteria and assign a quality to an S-box (with respect to these criteria). An S-box that fulfills prescribed criteria is called a strong S-box, while an S-box that lacks in some criterion is called a weak S-box. The S-box criteria include:  
* Nonlinearity, which measures the resistance against the linear cryptanalysis [3]. Nonlinearity is computed as a minimum distance to all affine functions, which can be efficiently implemented with a Fast Walsh-Hadamard transform. Cryptographic applications require S-boxes with nonlinearity that is as high as possible. * Differential profile, which measures the resistance against the differential cryptanalysis [4]. The differential profile measures the probability of the difference propagation, and should be as flat as possible. In this article, we focus exclusively on the differential profile. We provide more details in the following text. * Balancedness [5], which is required to achieve uniform distribution of output bits. A balanced Boolean function has the same number of zeroes and ones in its vector of values. Note that it is easy to show that Boolean permutation (bijective vectorial Boolean function) is always balanced. * Strict Avalanche (SAC) and Output Bit Independence (BIC) [6; 7], which measure the diffusion properties of the S-box. * Algebraic immunity [8], which measures the resistance against algebraic attacks on symmetric ciphers. * Multiplicative complexity [9], which measures the complexity of the S-box implementation in terms of the number of AND gates required to implement the S-box. High multiplicative complexity means that S-box implementation in hardware is more costly. On the other hand, S-boxes with low multiplicative complexity can be weak with respect to other criteria. * Other criteria, such as differential profile with respect to addition modulo \(2^{m}\)[10]. This can cover special cases required by non-standard cipher designs. An important task in cipher design is to generate strong S-boxes, as using a weak S-box can weaken the cipher. Even if the overall cipher design fixes the weakness introduced by a weak S-box, it would be less efficient than the design which uses strong S-boxes. There are multiple methods for generating strong S-boxes, which we review in Section 2. While efficient algebraic constructions of S-boxes with good cryptographic properties are known, we prefer to generate S-boxes with stochastic methods that can choose S-boxes from a large set of possible candidates and are not restricted to specific algebraic classes. Our main reason is that some cipher designs can be vulnerable against algebraic attacks (see, e.g., [11]), and these types of attacks can be specific to only certain classes of S-boxes. Thus, our goal is to generate S-boxes with better properties than can be obtained from a randomly generated vectorial Boolean function while keeping the S-box space as large (and diverse) as possible. For this purpose, we have introduced a new algorithm for generating S-boxes with prescribed differential properties. Unlike other known stochastic methods, our algorithms build the S-box in incremental steps. After each new value, we check the partial differential table. If the partial S-box does not fulfill the criteria, we use backtracking to explore a different branch of the search space. The algorithm is formally presented in Section 3.