# 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
For example, nonlinearity can take different values for S-boxes that belong to the same Hamming weight class. Movement between classes and within classes. * Movement within each class: Given an S-box \(F_{a}\), to obtain another S-box \(F_{b}\) of the same class, it is necessary and sufficient to swap between two elements of the output of \(F_{a}\) that have the same Hamming weight. The swap can be generalized between several pairs of elements, as long as the two elements of each pair have the same weight, which can be different between the pairs. * Movement between different classes: Given an S-box \(F_{a}\), to obtain another S-box \(F_{b}\) belonging to a different class, it is necessary and sufficient to perform the swap between two elements of the output that have different Hamming weights. * Number of classes. * The number of classes and the number of S-boxes in each class are estimated in this work (by two different ways) for any \(n\), by means of Propositions 5 and 6. * The number of classes is exponentially less than the number of S-boxes. * For \(n=3\), in Partition of the \(3\times 3\) S-box space into equivalence classes, the list of the 1120 HW classes is given. Quantifying the Search-Space Reduction Achieved Using the Partition into HW Classes Instead of Searching by S-Boxes  
In previous sections, a new partition in equivalence classes is proposed for the S-boxes of \(n\times n\), denoted as a partition in Hamming weight (HW) classes. According to the Hamming weight model, all S-boxes in an HW class have the same hypothetical power leakage. According to the CCV metric, we experimentally verified that all S-boxes of a class have the same theoretical resistance to power attacks. Based on this result, we propose a new strategy consisting of going through the class space and not the S-box space, and we argue that this reduces the search space, when the search is performed from class to class. In this section, for the S-boxes of \(n\times n\), we obtain the expression of the exact number of Hamming weight classes and the number of S-boxes within each class. Using this expression, we quantify the reduction in the search space associated with this new strategy. In particular, it is shown that, as \(n\) increases, the number of classes represents an increasingly smaller proportion of the number of S-boxes. For \(n=3,4,5,6,7,8\), we calculate the total number of classes, the number of S-boxes per class and the reduction achieved in the search space when going through the class space HW and not the space of S-boxes. 8.1 Estimate of the Number of HW Classes and the Number of S-Boxes in Each Class as Permutation with Repetition  
**Proposition 5** (Calculating the number of HW classes). : _When the space of \((2^{n})!\) S-boxes of dimension \(n\times n\) is partitioned into Hamming weight (HW) classes:_  
1. _The total number of HW equivalence classes is:_ \(\text{PR}^{C(n,n),\ldots,C(n,n)}_{2^{n}}=\frac{(2^{n})! }{\prod_{n=0}^{n}(n \
eq r)! }\)_._
2. _The total number of S-boxes in each HW equivalence class is:_ \(\prod_{r=0}^{n}C(n,r)!\)_._  
Proof. : The demonstration is direct because the HW classes definition meets that each class is equivalent to a permutation with repetition of \(2^{n}\) elements grouped into \((n+1)\) groups, where group \(r\) has exactly \(C(n,r)\) equal elements. Keep in mind that, if the \(2^{n}\) outputs of the S-boxes \(\{S(X):X=0,\ldots,2^{n}-1\}\) are grouped by their weights, then the \(2^{n}\) weights of these outputs \(\{\|S(X)\|:S(X)=0,\ldots,2^{n}-1\}\) are divided into \((n+1)\) groups corresponding to the \((n+1)\) different values \(r=0,\ldots,n\), which can take their weights \(\{\|S(X)\|=r:r=0,\ldots,n\}\). The essential observation is that classes are defined by the permutations of the positions occupied by the \((n+1)\) groups. In turn, within a class, the S-boxes are determined by the permutation of the groups' elements.