# 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
### S-Boxes HW Equivalent  
**Definition 1**. : _Two bijective S-boxes \(F_{1},F_{2}\) of order \(n\times n\) are called HW equivalent if they have the same leakage of power according to the Hamming weight model, i.e., \(F_{1},F_{2}\) are HW equivalent if and only if \(HW(F_{1}(x))=HW(F_{2}(x))\), for all \(x\in\{0,\ldots,2^{n}-1\}\)._  
**Proposition 1**. : _The HW equivalence relationship defined in the space of all S-boxes \(F\) of order \(n\times n\), is an equivalence relationship._  
Proof. : It is immediate from the definition that the S-boxes meet the properties of reflexivity, symmetry and transitivity. It proves the HW equivalent relation between the S-boxes. The HW equivalence class \(<F_{a}>\) associated with any S-box, \(F_{a}\) can be expressed as:  
\[<F_{a}>=\{F_{b}|HW(F_{b}(x))=HW(F_{a}(x)),\ \forall x\in\{0,\ldots,2^{n}-1\}\}. \tag{9}\]  
This equivalence relation is used to partition the space of bijective S-boxes into Hamming weight classes. The cardinality of the class space is much smaller than the cardinality of the S-box space. According to the confusion coefficient variance, the theoretical resistance to power attacks is constant within each class and can be different between classes. It is proposed to replace the search in the space of S-boxes by the search in the class space Hamming weight (when trying to search for S-boxes resistant to Power attacks). \begin{table}
\begin{tabular}{l l l l} \hline \hline \multicolumn{1}{c}{**Factorial**} & \multicolumn{1}{c}{**Stirling’s Formula**} & \multicolumn{1}{c}{**Upper Bound**} & \multicolumn{1}{c}{**Lower Bound**} \\ \hline
70! & \(10^{100}\) & \(10^{100.0779669}\) & \(10^{100.0779665}\) \\
56! & \(10^{75}\) & \(10^{75}\) & \(846396\) & \(10^{75.846395}\) \\
28! & \(10^{29}\) & \(10^{29}\) & \(48214\) & \(10^{29.48213}\) \\
8! & \(10^{4}\) & \(10^{4.60537}\) & \(10^{4.60532}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Examples of estimating \(n!\) by the Stirling formula, for \(n=8,28,56,70\). Now, we discuss the representation of the HW classes using the vector of weights of the S-boxes outputs that compose it. Considering that the vector of weights of outputs of the S-boxes that belong to a class is the same for all S-class boxes. This vector of weights is used to represent any class: \(<F_{a}>=(HW(F_{a}(0)),\ldots,HW(F_{a}(2^{n}-1)))\). **Example 1** (PRINT cipher). : _The following example represents the PRINT S-box \(F_{Print}(x)\) and its HW class \(<F_{Print}>=(0,1,2,2,3,1,2,1)\) using its vector of output weights. This S-box has a variance of the CCV confusion coefficient of 0.275510 (see Table 2)._  
**Example 2** (PRESENT). : _The representation of the PRESENT S-box \(<F_{PRESENT}>\), through its weight vector, is given in the Appendix A (see Tables A1 and A2)._  
**Example 3** (Aes). : _The representation of the AES S-box class \(<F_{AES}>\), through its weight vector, is given in the Appendix B (see Tables A3 and A4)._  
Considering that all S-boxes in a class have the same hypothetical power leakage according to the Hamming weight model, it is theoretically expected that all S-boxes in a class have the same resistance to power attacks. We also look forward in the direction of having some invariant theoretical metric. **Proposition 2** (CCV is constant within each class). : _Let \(F_{a}\) and \(F_{b}\) be two S-boxes defined in the same domain and image {0,1}\({}^{n}\). If \(F_{a}\) and \(F_{b}\) are HW equivalents, then \(CCV(F_{a})=CCV(F_{b})\)._  
Proof. : In the CCV expression under the Hamming weight leakage model,  
\[CCV(F)=\sigma^{2}\Big{[}E_{P}\Big{[}(HW(F(k_{i}\oplus p))-HW(F(k_{j}\oplus p)) ^{2}\Big{]}\mid\forall\ i<j\Big{]}. \tag{10}\]  
It can be seen that two HW equivalent S-boxes have the same CCV value because, for all \(x\), \(HW(F_{a}(x))=HW(F_{b}(x))\), the Hamming weights of the outputs of each S-box are equal to each other for all possible inputs, and therefore the expected value and the variance that define the CCV are equal.