# Algorithm for Generating S-Boxes with Prescribed Differential Properties
## 3 New Algorithm for Generating S-Boxes with Prescribed Differential Properties
### Main Algorithm  
The disadvantages of Algorithm 2 lead us to a final version of the search algorithm that is based on a depth-first search with backtracking. This algorithm is formalized as Algorithm 3.  
```
0:\(n>0\), S-box input size.
0:\(m>0\), S-box output size.
0:\(satisfies\_conditions()\), a function that returns true if partial DDT satisfies criteria.
0:\(limit\), the maximum number of tries. \(X\leftarrow[],Y\leftarrow[]\) \(counter\gets 0\) while\(len(X)<2^{n}\)do if\(counter>limit\)then return\(\varnothing\) endif \(a\leftarrow\)\(\in_{R}\)\(\mathbf{F}_{2}^{2^{n}}\setminus X\) \(b\leftarrow\)\(\in_{R}\)\(\mathbf{F}_{2}^{2^{n}}\setminus Y\) \(PDDT\leftarrow\)\(partial\_ddt(X+[a],Y+[b])\) if\(satisfies\_conditions(PDDT)\)then \(X.append(a)\) \(Y.append(b)\) endif \(counter\gets counter+1\) endwhile return\(Sbox(X,Y)\)
```  
**Algorithm 3** Randomized algorithm to construct S-boxes with prescribed differential table  
In Algorithm 3, we initialize arrays \(Y_{x}\) with potential elements from \(\mathbb{Z}_{2}^{m}\) in random order. Then, we try to fill in the partial S-box in a fixed order of \(x\), with \(S(x)\) stored in the growing list \(Y\). For each new \(x\), we take the next element \(y\) from \(Y_{x}\) (representing \(y=S(x)\)) and check whether the conditions on partial DDT of the potential S-box hold. If PDDT is correct, we continue with new \(x\); otherwise, we remove \(y\) from \(Y_{x}\), and try the next one.  
If all \(y\) on a level have been removed, it is neccesary to backtrack. We remove the last stored assignment of \(y=S(x)\) by decreasing active \(x\) and removing \(y\) from \(Y\) and the corresponding \(Y_{x}\) set. After backtracking, we continue to investigate the remaining options in \(Y_{x}\), or backtrack again if all options are exhausted.  
In practice, it is possible to speed up the search by exploiting the affine equivalence of S-boxes; see, e.g., [9]). This means that when \(x=0\) or \(x=2^{i}\) for some \(i<n\), we only use \(Y_{x}=\{x\}\). In this case, the algorithm generates a normalized representative of an affine class of S-boxes with the required DDT. This method cannot be applied when looking for additional properties of the DDT, such as special distribution of values in rows and columns of the DDT.  
```
0:\(n>0\), S-box input size.
0:\(m>0\), S-box output size.
0:\(satisfies\_conditions()\), a function that returns true if partial DDT satisfies criteria. \(Y\leftarrow[]\) for all\(x\in\{0,1,\ldots,2^{n}-1\}\)do \(Y_{x}\gets shuffle(\mathbb{Z}_{2}^{m})\) [Store elements in random order.] endfor \(x\gets 0\) while\(x<2^{n}\)do [If bijective S-boxes are required, use \(y\in Y_{x}-Y\) instead.] for all\(y\in Y_{x}\)do \(PDDT\leftarrow\)\(partial\_ddt([0,1,\ldots,x],Y+[y])\) if\(satisfies\_conditions(PDDT)\)then \(x\gets x+1\) {Increes depth.} \(Y.append(y)\) else \(Y_{x}.remove(y)\) [Dead end, try other branches.] endfor if\(x=0\)and\(Y_{0}=[]\)then return\(\emptyset\) endif if\(Y_{x}=[]\)then [Backtracking needed?] \(Y_{x}\gets shuffle(\mathbb{Z}_{2}^{m})\) {Reset options on this level.} \(x\gets x-1\) {Decrease search level.} \(y\gets Y.pop()\) {Remove last element of \(Y_{x}.remove(y)\) [Explored, no suitable successors.] endif endwhile return\(Sbox([0,1,\ldots,2^{n}-1],Y)\) {Whole S-box is determined.}
```  
**Algorithm 3** Depth-first search algorithm to find S-boxes with prescribed differential table  
Algorithm 3 is a typical example of an exhaustive search algorithm. Thus, it always stops and produces the required results if any S-box that satisfies the conditions exists. However, in the worst-case scenario the algorithm needs to examine the whole search space, with potential complexity as high as \(2^{m2^{n}}\) DDT evaluations. However, because unproductive branches are cut off, the proposed algorithm terminates sooner than a simple exhaustive search that only checks the DDT of the whole S-box. A more detailed complexity analysis is provided in Section 4.