# 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  
The corollary above provides an inverse measure of the reduction in search space achieved by replacing the S-boxes path with the path over the HW classes. It tells us what fraction of the initial space of S-boxes is reduced by HW's classes space. The lower the value of \(\frac{1}{\prod_{r=0}^{n}C(n,r)}=\frac{1}{\prod_{r=1}^{n-1}C(n,r)}\), the more significant the reduction achieved when going through the classes and not the S-boxes. Now, we discuss the reduction speed as a function of \(n\). Note that as \(n\) increases, the value \(\prod_{r=0}^{n}C(n,r)!\) grows very quickly and \(\frac{1}{\prod_{r=0}^{n}C(n,r)! }\) decreases very rapidly. Note that  
\[\lim_{n\to\infty}\frac{Number\ of\ HWclasses}{Number\ of\ S-boxes\ of\ n\times n}=\lim_{n\to\infty}(\frac{1}{\prod_{r=0}^{n}C(n,r)!})=0. \tag{14}\]  
The above expression shows that as \(n\) increases, the class space's dimension becomes an ever-smaller fraction of the S-box space. This fraction decreases very rapidly as \(n\) grows. 8.3 Examples of the Number of HW Classes, the Number of S-Boxes per Class and the Reduction in Search-Space Achieved with the New Proposed Strategy  
In this subsection, we illustrate the previous proposition's application to estimate the search space reduction using some examples (see Table 3). We next discuss some observations on the data shown in Table 3. With respect to the dimension of the class space, notice how for \(n=3,4,5,6,7,8\) the dimension of the class space is, respectively, equal to \(10^{-1}\), \(10^{-6}\), \(10^{-17}\), \(10^{-43}\), \(10^{-52}\) and \(10^{-316}\), i.e., for each part of the initial space of S-boxes, there is a smaller and smaller fraction of the initial space. Note that, for \(n=3,4,5,6,7\), the number of classes is greater than the class's cardinal, while, for \(n=8\), the number of classes is less than the class's cardinal. On the exponential reduction of space, for \(n=8\), the dimension of the class space is approximately \(10^{316}\) times less than the initial space of S-boxes. Therefore, when applying the proposed strategy of moving from class to class and not from S-box to S-box, the reduction of the search space is of the order \(10^{316}\). Importantly, by rejecting a class for having a low CCV value, one is simultaneously rejecting approximately \(\sim\)\(10^{316}\) S-boxes. On the other hand, accepting a class, due to having a high value of CCV, there are approximately \(10^{316}\) S-boxes among which to look for some that meet the remaining cryptographic properties. Now, relating the comparison of S-box space partitions, consider the case \(n=4\). In [5], for \(n=4\), the bijective S-box space is partitioned into classes considering the resistance to differential and linear cryptanalysis. In this work, the space of S-boxes is divided into HW classes according to their theoretical resistance to power attacks, according to the CV metric. It would be very interesting to compare both partitions, which is left for future work. With respect to all S-boxes in a \(3\times 3\) class, consider the following. For the \(3\times 3\) S-box of the PRINT cryptographic algorithm [28], the 36 equivalent S-boxes were generated. They are shown in the Appendix. It is observed how the necessary condition given in Proposition 4 is fulfilled. The preimages of \(0\) and \(7=2^{3}-1\) are constant within the class: \(F_{a}^{-1}(0)=F_{b}^{-1}(0)=0\) and \(F_{a}^{-1}(7)=F_{b}^{-1}(7)=4\), \(\forall\)\(F_{b}\in<F_{a}>\). The 1120 HW equivalence classes were constructed. 8.4 Estimation of the Number of HW classes and the Number of S-boxes in Each Class as an Occupation Problem  
The following proposition provides another alternative way of calculating the number of classes and the number of S-boxes per class. **Proposition 6** (Calculating the S-box number within each HW class).