# Algorithm for Generating S-Boxes with Prescribed Differential Properties
## 4 Complexity Analysis
### Analysis of the Algorithm 3  
From the complexity point of view, Algorithm 3 has the advantage of early rejection compared to the general rejection sampling employed by a randomized depth-first search for S-boxes. A classical approach is to generate the whole S-box, compute DDT, and then reject or accept based on the threshold \(\delta\). Our new algorithm enables partial DDT sampling. If the partial sample contains DDT values above the threshold \(\delta\), further iterations of the algorithm cannot improve this value, meaning that it can be immediately rejected. Moreover, using a randomized depth-first search, we can exclude the whole set of samples that are above the threshold \(\delta\) from the search.  
Similarly to Section 4.1, we can estimate the probability of distribution of PDDT cells after \(s\) steps of the algorithm as follows:  
\[Pr(PDDT_{i,j}^{(s)}\geq t)=Q(X_{i,j}^{(s)}\geq t)=e^{-\lambda_{s}}\sum_{j\geq t }\frac{(\lambda_{s})^{j}}{j!},\]  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**S-Box Size** & \(\delta=4\) & \(\delta=6\) & \(\delta=8\) & \(\delta=10\) & \(\delta=12\) \\ \hline \(n=4\) & 3.8\% & 66.7\% & 96.0\% & 99.7\% & 99.9\% \\ \(n=6\) & 0.0\% & 0.2\% & 52.4\% & 94.8\% & 99.6\% \\ \(n=8\) & 0.0\% & 0.0\% & 0.0\% & 42.2\% & 94.0\% \\ \hline \hline \end{tabular}
\end{table}
Table 2: Estimated probabilities of random \(\delta\)-differentially uniform S-boxes using “bins and balls” method.  
where \(\lambda_{s}\) is an expected average value of \"balls per bin\" after \(s\) steps of the algorithm. The number of bins, value \(\kappa=MN\), does not change throughout the algorithm, however, the expected average occupancy of the bins \(\lambda_{s}\) grows with \(s\).  
If we carry out rejection sampling after exactly \(s\) steps of the algorithm, we can estimate the probability of not rejecting the PDDT with threshold \(t=\delta/2+1\) again as  
\[p_{t,s}=\left(1-e^{-\lambda_{s}}\frac{(\lambda_{s})^{t}}{t!}\right)^{\kappa}.\]  
The value of \(\lambda_{s}\) increases with \(s\) as follows. After \(s\) steps, we throw \(s(s-1)/2\) \"balls\" (pairs added to PDDT) into \(MN\) bins; thus, the average number of \"balls per bin\" is  
\[\lambda_{s}=\frac{s(s-1)}{2 MN}.\]  
For S-boxes \(S:\mathbb{Z}_{2}^{n}\leftarrow\mathbb{Z}_{2}^{n}\), we have \(N=M=2^{n}\) and  
\[\lambda_{s}\approx\frac{s^{2}}{2^{2n+1}}.\]  
When \(s\) is small in comparison to \(MN\), we have a low probability of rejecting a PDDT; thus, the search space quickly branches out. With growing \(s\), we increase the number of potential branches (up to \(M^{s}\)), as well as the probability of rejecting the PDDTs. Thus, the estimated width of the search tree on level \(s\) is  
\[W_{s}=W_{s-1}\cdot M\cdot p_{t,s}=M^{s}\prod_{i=1}^{s}p_{t,i}.\]  
The number of potential endpoints of the search tree we are looking for is \(D=M^{N}p_{t}\). Each of these points is connected to the root of the search tree, with the paths going through the level with the maximum width of the tree, denoted by \(W=\max W_{s}\). Thus, we need to go through the search tree on average \(W/D\)-times, which is  
\[\max_{s\leq N}\left\{M^{s-N}\frac{\prod_{i=1}^{s}p_{t,i}}{p_{t}}\right\}.\]  
As \(M^{s-N}\prod_{i=1}^{s}p_{t,i}<1\) for each \(s\), it is apparent that Algorithm 3 can always find the desired S-box (if it exists) faster than random search, which has an expected complexity of \(p_{t}^{-1}\).