# 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
### Redefining the Equivalence Relation and the HW Classes. For the generation of the elements of each class \(<F_{a}>\), it is convenient to redefine it, representing it from the following \((n+1)\) subsets:  
\[C(F)_{k}=\{x|\ HW(F(x))=k,\forall x\in\{0,\ldots,2^{n}-1\}\}. \tag{11}\]  
Thus, \(C(F)_{k}\) is the set of inputs of the S-box \(F\) whose outputs have weight \(k\). **Proposition 3** (Necessary and sufficient condition of HW equivalence). : \(F_{1},F_{2}\) _are HW equivalents if and only if \(C(F_{1})_{k}=C(F_{2})_{k},\forall k\in\{0,\ldots,n\}\)._ \begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline
**x** & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** \\ \hline \(\mathbf{F_{Print}(x)}\) & 0 & 1 & 3 & 6 & 7 & 4 & 5 & 2 \\ \hline \(<F_{Print}>\) & 0 & 1 & 2 & 2 & 3 & 1 & 2 & 1 \\ \hline \end{tabular}
\end{table} 
Table 2: PRINT S-box \(F_{Print}(x)\) and its HW class \(<F_{Print}>\). Proof. : Starting from the hypothesis, \(HW(F_{1}(x))=HW(F_{2}(x)),\forall x\in\{0,\ldots,2^{n}-1\}\). If it is assumed that \(x\) exists such that \(x\in C(F_{1})_{k}\) and \(x\
ot\in C(F_{2})_{k}\), then the hypothesis contradicts. On the other hand, assuming that \(C(F_{1})_{k}=C(F_{2})_{k},\forall k\in\{0,1,2,\ldots,n\}\), if there exists an \(x\in C(F_{1})_{k}\), then \(x\in C(F_{2})_{k}\), and therefore \(HW(F_{1}(x))=HW(F_{2}(x))=k\). By redefining the equivalence relationship, the class associated with the S-box \(F_{a}\) can be expressed as: \(<F_{a}>=\{F_{b}|C(F_{b})_{k}=C(F_{a})_{k},\forall k\in\{0,\ldots,n\}\}\). From the redefinition of the class, it is easy to see that it is determined by the \((n+1)\) sets \(C(F_{a})_{k}\), \(\forall k\in\{0,\ldots,n\}\). **Example 4** (Redefinition of class \(<F_{Print}>\).). : _Let \(<F_{Print}>=(HW(F_{Print}(0)),\ldots,HW(F_{Print}(7)))=(0,1,2,2,3,1,2,1)\). The \(C(F_{a})_{k}\) sets that determine the class \(<F_{Print}>\) associated with the S-box of PRINT are:_  
* \(C(F_{Print})_{0}=\{0\}\)_:_ \(F_{Print}(x)\) _inputs_ \(x\) _such that_ \(HW(F_{Print}(x))=0\)_._
* \(C(F_{Print})_{1}=\{1,5,7\}\)_:_ \(F_{Print}(x)\) _inputs_ \(x\) _such that_ \(HW(F_{Print}(x))=1\)_._
* \(C(F_{Print})_{2}=\{2,3,6\}\)_:_ \(F_{Print}(x)\) _inputs_ \(x\) _such that_ \(HW(F_{Print}(x))=2\)_._
* \(C(F_{Print})_{3}=\{4\}\)_:_ \(F_{Print}(x)\) _inputs_ \(x\) _such that_ \(HW(F_{Print}(x))=3\)_._  
**Example 5** (Redefinition of class \(<F_{AES}>\)). : _The sets \(C(F_{a})_{k}\) that determine the class \(<F_{AES}>=(HW(F_{AES}(0)),\ldots,HW(F_{AES}(255)))\) associated with the S-box \(F_{AES}\) of the AES, are:_  
* \(C(F_{AES})_{0}=\{75\}\)_._
* \(C(F_{AES})_{1}=\{53,57,76,9a,68,cc,e9,ea\}\)_._
* \(C(F_{AES})_{2}=\{5,6,9,24,50,54,5c,5f,71,72,7a,7d,7e,7f,91,9d,b3,b8,c0,c3,c4,cb,cf,e2,e6,ed,\)__\(f3,ff\}\)_._
* \(C(F_{AES})_{3}=\{1,2,a,b,e,20,23,27,2b,2c,2f,45,51,52,58,5b,5e,\)__\(64,68,6b,6f,70,73,77,79,7b,7c,90,92,96,99,9b,\)__\(9_{c},9e,b0,b7,bb,bc,be,bf,c2,c5,c7,e9,cc,d1,da,de,\)__\(e0,e1,e4,e5,ee,f0,f8,fc\}\)_._
* \(C(F_{AES})_{4}=\{0,3,4,7,8,c,d,f,1b,1c,1f,21,22,28,29,2d,2e,31,\)__\(36,3d,41,42,46,4a,4d,55,56,59,5a,5d,60,63,67,\)__\(74,78,80,84,88,8b,8c,93,94,95,97,98,a6,a7,a9,aa,\)__\(b1,b2,b4,b6,b9,bd,cc,ca,d0,d6,dd,e3,e7,e8,eb,cc,\)__\(ef,f4,f7,fb\}\)_._
* \(C(F_{AES})_{5}=\{10,13,14,17,18,19,1e,25,26,2a,32,35,37,3a,3b,\)__\(3e,43,47,48,49,4b,4c,4e,61,62,65,66,69,6a,6e,83,\)__\(87,87,9f,40,a1,a2,a5,ad,ae,b5,ba,c1,cd,d2,d3,d4,\)__\(45,d7,d8,49,f5,f9,fa,fd,fe\}\)_._
* \(C(F_{AES})_{6}=\{12,15,16,1d,30,33,38,39,3c,3f,40,44,4f,6d,82,\)__\(85,89,8a,8e,a3,44,ab,ac,dc,df,f1,f2,f6\}\)_._
* \(C(F_{AES})_{7}=\{11,1a,34,81,86,48,af,db\}\)_._
* \(C(F_{AES})_{8}=\{8d\}\)_._  
The determination of the class by the \((n+1)\) sets allows deducing an algorithm to easily generate the elements of a class: Let \(F_{a}\) be an arbitrary initial S-box.