# Search-Space Reduction for S-Boxes Resilient to Power Attacks
## 4 Conclusions  
The main results of the present work are the proposal of a new equivalence relationship between S-boxes and their application to exponentially reduce the search space for nonlinear S-boxes and resistance to power attacks, when the search is performed from class to class. This result provides new theoretical knowledge about the internal structure of the bijective S-box space and its partition into equivalence classes according to its resistance to power attacks. As far as we know, there are no previous reports of results of this type  
New equivalence classes: This paper proposes a new definition of equivalence classes to relate S-boxes according to their power leak following the Hamming weight model (HW equivalence). A new algorithm is presented, which randomly generates an S-box HW equivalent to the initial one, given an initial S-box of input. Three variants of different complexity are proposed to apply this algorithm. It was demonstrated that the metric \"variance of the confusion coefficient (CCV)\" that theoretically measures the resistance of an S-box against power attacks takes constant values within the HW classes. This result was confirmed experimentally (using the previous algorithm) for four S-boxes classes, corresponding to the S-boxes of the AESCC, SCREAM, AES and STRIBOG algorithms. Exponential reduction of the search space: Based on these new HW equivalence classes, a new strategy was proposed to search for S-boxes resistant to power attacks, \begin{table}
\begin{tabular}{c c c c} \hline \hline
**r** & \(C\Big{(}\left[2^{n}-\sum_{i=0}^{r-1}C(n,i)\right],C(n,r)\Big{)}\) & **Estimated Value** & **Accumulated Product** \\ \hline
0 & C(256, 1) = 256 & \(\sim\)\(10^{2}\) & \(\sim\)\(10^{2}\) \\ \hline
1 & C(256-1, 8) = C(255, 8) & \(\sim\)\(10^{15}\) & \(\sim\)\(10^{17}\) \\ \hline
2 & C(255-8, 28) = C(247, 28) & \(\sim\)\(10^{37}\) & \(\sim\)\(10^{54}\) \\ \hline
3 & C(255-8, 28) = C(219, 56) & \(\sim\)\(10^{54}\) & \(\sim\)\(10^{108}\) \\ \hline
4 & C(219-56, 70) = C(163, 70) & \(\sim\)\(10^{47}\) & \(\sim\)\(10^{155}\) \\ \hline
5 & C(163-70, 56) = C(93, 56) & \(\sim\)\(10^{27}\) & \(\sim\)\(10^{182}\) \\ \hline
6 & C(93-56, 28) = C(37, 28) & \(\sim\)\(10^{9}\) & \(\sim\)\(10^{191}\) \\ \hline
7 & C(37-28, 8) = C(9, 8) = 9 & \(\sim\)\(10^{1}\) & \(\sim\)\(10^{192}\) \\ \hline
8 & C(9-8, 1) = C(1, 1) = 1 & \(\sim\)\(10^{0}\) & \(\sim\)\(10^{192}\) \\ \hline \multicolumn{3}{c}{Exactly} \\ \# of classes & \(\left[256\times C(255,8)\times C(247,28)\times\right.\) & & Approximately \(\sim\)\(10^{192}\) \\ \multicolumn{3}{c}{\(\left.C(219,56)\times C(163,70)\times\right.\)} \\ \multicolumn{3}{c}{\(\left.C(93,56)\times C(37,28)\times\right.\)9} \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Number of classes for \(n=8\), by Proposition 5. \begin{table}
\begin{tabular}{c c} \hline \hline \multicolumn{3}{c}{**Estimated Number of HW**} \\ \multicolumn{3}{c}{**Classes of \(8\times 8\)**} \\ \hline Proposition 5 & \(\sim\)\(10^{190}\) \\ Proposition 6 & \(\sim\)\(10^{192}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: \(n=8\), number of classes estimated by Propositions 5 and 6.  
essentially consisting of moving in the class space and not in the S-box space, changing of classes as long as the CCV value is low. When a high CCV class is found, the S-boxes inside the class are scanned to evaluate the remaining cryptographic properties of the S-boxes, such as nonlinearity. An advantage of this strategy is that it is easily applied because, to change classes, it is enough to swap at least two elements of different hamming weights, while, to change S-boxes within the class, it is enough to swap at least two elements of equal weight. The main advantage of this strategy is that it allows an exponential reduction of the search space. The cardinal of the class space was calculated using two different methods. Its comparison with the cardinal of the space of S-boxes shows that, as n increases, the class space represents a smaller and smaller fraction of the space of S-boxes.