# Algorithm for Generating S-Boxes with Prescribed Differential Properties
## 4 Complexity Analysis
### Random Generation of S-Boxes  
If there is no restriction on DDT, we can estimate the probability distribution of the final DDTs by computing \(B_{i,j}^{N}\). Alternatively, this should correspond to a simpler experiment in which we simply throw \(N(N-1)/2\) balls into \(N\times M\) bins. The generated function \(F\) is expected to be \(\delta\)-differentially uniform with a probability of event  
\[B_{i,j}^{N}\leq\delta/2,\quad\text{for each $1\leq i\leq N,1\leq j\leq M$}.\]  
Distribution of balls in bins follows a multinomial distribution, with \(\kappa=NM\) exclusive events (bins), equal event probabilities \(\pi_{i}=\frac{1}{NM}\), and the number of trials equal to \(\
u=\frac{N(N-1)}{2}\). Thus, the expected average number of balls per bin is \(E(X_{i})=\
u\pi_{i}=\frac{N-1}{2M}\). The most important case for S-box generation is when \(N=M=2^{n}\), which provides us with an expected average number of balls per bin near \(1/2\). Considering \(\
u\) such samples, we now ask what the is probability that all samples are at most at the threshold \(\delta/2\) in order to obtain a \(\delta\)-differentially uniform S-box.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Step** & \(\mathbf{x}\) & **Available Items in \(\mathbf{Y_{x}}\)** & **Partial S-Box** & **max. Value in PDDT** & **Is Valid?** \\ \hline
0 & - & \{0,1,2,3,4,5,6,7\} & [ ] & 0 & - \\
1 & 0 & \{0\} & [ 0 ] & 0 & true \\
2 & 1 & \{1\} & [ 0, 1 ] & 2 & true \\
3 & 2 & \{2\} & [ 0, 1, 2 ] & 2 & true \\
4 & 3 & \{5,7,3,6\} & [ 0, 1, 2, 5 ] & 2 & true \\
5 & 4 & \{4\} & [ 0, 1, 2, 5, 4 ] & 2 & true \\
6 & 5 & \{6,7,3\} & [ 0, 1, 2, 5, 4, 6 ] & 2 & true \\
7 & 6 & \{3,7\} & [ 0, 1, 2, 5, 4, 6, 3 ] & 4 & false \\
8 & 6 & \{3,7\} & [ 0, 1, 2, 5, 4, 6, 7 ] & 2 & true \\
9 & 7 & \{3\} & [ 0, 1, 2, 5, 4, 6, 7, 3 ] & 2 & true \\ \hline \hline \end{tabular}
\end{table}
Table 1: Example of S-box construction with (modified) Algorithm 3.  
To simplify this calculation, we can replace individual binomial distributions with their Poisson approximation  
\[f(k;\lambda)=\Pr(X=k)=\frac{\lambda^{k}e^{-\lambda}}{k!},\]  
which has \(\lambda=1/2\). The probability that the sample size reaches the threshold \(t=\delta/2+1\) is  
\[Pr(DDT_{i,j}\geq t)=Q(X_{i,j}\geq t)=e^{-1/2}\sum_{j\geq t}\frac{(1/2)^{j}}{j!}.\]  
The terms in the expansion converge rapidly to 0; thus, we can take the first term as the expected probability of a single bin containing at least \(t\) balls. The probability that none of the bins contains \(t\) or more balls is then estimated by  
\[p_{t}=\left(1-e^{-1/2}\frac{(1/2)^{t}}{t!}\right)^{\kappa}.\]  
The estimated probabilities for \(N=M=2^{n}\) and \(t=\delta/2+1\) are summarized numerically in Table 2.  
Using the approximation  
\[p_{t}\approx 1-\kappa e^{-1/2}\frac{(1/2)^{t}}{t!}\]  
and [PERSON]'s approximation [48], we obtain  
\[\ln(1-p_{t})\approx 2n-1/2-t(\ln 2+\ln t-1). \tag{1}\]  
This means that when we decrease \(\delta\) for a fixed \(n\), our probability of generating a \(\delta\)-uniform S-box decreases exponentially. Thus, we need to examine exponentially more randomly generated S-boxes to obtain one of suitable quality.