# Search-Space Reduction for S-Boxes Resilient to Power Attacks
## 3 Our Contributions: Reduction of the S-Boxes Search-Space into a Hamming Weight Class SEARCH-Space
### New Search Strategy for S-Boxes Resistant to Power Attacks Based on HW Classes
#### 3.8.2 Reduced Search-Space
: _When we partition the space of \((2^{n})!\) S-boxes of dimension \(n\times n\), into Hamming weight (HW) classes, then the following hold:_  
_(a) The number of \"Hamming Weight\" equivalence classes is equal to:_  
\[N_{\text{HW}}=2^{n}\prod_{r=1}^{n}C\left(\left[2^{n}-\sum_{i=0}^{r-1}C(n,i) \right],C(n,r)\right) \tag{15}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Number** & **Number** & \(\prod_{r=0}^{n}C(n,r)!\) & \(\prod_{r=0}^{n}C(n,r)!\) & \(\frac{1}{\prod_{r=0}^{n}C(n,r)}\) \\
**n** & **(\(2^{n}\))! of** & \(PR_{2^{n}}^{C(n,n),\ldots,C(n,n)}\) & **of S-Boxes** & \(\frac{1}{\prod_{r=0}^{n}C(n,r)}\) \\  & **S-Boxes** & **of HW Classes** & **in Each Class** & \\ \hline
3 & 8! = 40320\(\sim\)\(10^{4}\) & 1120\(\sim\)\(10^{3}\) & 36\(\sim\)\(10^{1}\) & \(\sim\)\(10^{-1}\) \\
4 & 16!\(\sim\)\(10^{13}\) & \(\sim\)\(10^{7}\) & \(\sim\)\(10^{6}\) & \(\sim\)\(10^{-6}\) \\
5 & 32!\(\sim\)\(10^{35}\) & \(\sim\)\(10^{18}\) & \(\sim\)\(10^{17}\) & \(\sim\)\(10^{-17}\) \\
6 & 64!\(\sim\)\(10^{89}\) & \(\sim\)\(10^{46}\) & \(\sim\)\(10^{43}\) & \(\sim\)\(10^{-43}\) \\
7 & 128!\(\sim\)\(10^{215}\) & \(\sim\)\(10^{163}\) & \(\sim\)\(10^{52}\) & \(\sim\)\(10^{-52}\) \\
8 & 256\(\sim\)\(10^{506}\) & \(\sim\)\(10^{190}\) & \(\sim\)\(10^{316}\) & \(\sim\)\(10^{-316}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Example for \(n=3,4,5,6,7,8\) estimate of the number of S-boxes, number of HW classes, the number of S-boxes per class and the reduction in search space. _The number of S-boxes within each HW equivalence class is exactly equal to:_  
\[N_{S}=\frac{(2^{n})!}{2^{n}\prod_{r=1}^{n}C\Big{(}2^{n}-\sum_{i=0}^{r-1}C(n,i),C( n,r)\Big{)}} \tag{16}\]  
Proof. : The demonstration of Statement (a) is based on modeling the construction of the classes using an occupation problem, with successive dependent launches. It is taken into account that the \(2^{n}\) weights \(\{\|S(X)\|:S(X)=0,\ldots,2^{n}-1\}\) of the outputs of the S-boxes can be divided into \((n+1)\) groups corresponding to the \((n+1)\) different values \(\{r:r=0,\ldots,n\}\) that can take their weights \(\{\|S(X)\|=r:r=0,\ldots,n\}\), where the group \(r\) contains exactly \(C(n,r)\) equal elements. The essential observation is that each class corresponds to a different location of the \((n+1)\) weight groups in the \(2^{n}\) places. Without loss of generality, it can be assumed that the groups are located in increasing order of the value of \(r\). The first group corresponds to the weight \(r=0\), containing \(C(n,0)=1\), only one element and can be located in any of the \(C(2^{n},1)=2^{n}\) possible places. For the remaining groups \(r=1,\ldots,(n-1)\), the reduction in the number of available places caused by the location of the previous groups must be taken into account, as discussed below. In general, to locate the \(C(n,r)\) elements of the \(r\)th group, for \(r=1,\ldots,(n-1)\), there are exactly \(\left[2^{n}-\sum_{i=0}^{r-1}C(n,i)\right]\) available places, since the \(\left[\sum_{i=0}^{r-1}C(n,i)\right]\) places occupied by the previous groups are subtracted from the \(2^{n}\) starting places. The selection of those \(C(n,r)\) positions among the available \(\left[2^{n}-\sum_{i=0}^{r-1}C(n,i)\right]\) can be done in \(C\Big{(}\left[2^{n}-\sum_{i=0}^{r-1}C(n,i)\right],C(n,r)\Big{)}\) forms. Therefore, the total number of ways to locate the \((n+1)\) weight groups in the \(2^{n}\) places is equal to \(2^{n}\prod_{r=1}^{n}C(2^{n}-\sum_{i=0}^{r-1}C(n,i),C(n,r))\), which is exactly the number of HW classes. Now, we turn to Statement (b). By dividing the total number \((2^{n})!\) of S-boxes of \(n\times n\) between the number of classes, \((2^{n})\prod_{r=1}^{n}C(\left[2^{n}-\sum_{i=0}^{r-1}C(n,i)\right],C(n,r))\) calculated for Statement (a), it is obtained that the number of S-boxes inside each class is  
\[N_{S}=\frac{(2^{n})!}{2^{n}\prod_{r=1}^{n}C(2^{n}-\sum_{i=0}^{r-1}C(n,i),C(n, r))}. \tag{17}\]