# Search-Space Reduction for S-Boxes Resilient to Power Attacks
## 2 Basic Concepts  
We begin by stating some basic definitions. Bijective S-boxes are vector functions used in most block ciphers, represented as a mapping \(F:\{0,1\}^{n}\rightarrow\{0,1\}^{n},n\in\mathbb{N}\). For each binary vector \(x\in\{0,1\}^{n}\), \(HW(x)\) represents the Hamming weight of \(x\)[10]. Its objective is to cause the greatest possible confusion by masking the relationship between the plain text and the ciphertext [2; 19].  
The _correlation power attack (CPA)_[20] uses the linear correlation coefficient as a distinction to quantify the statistical dependence between the real power leak \(Y_{k,p}\) generated from the \(K\) key and the hypothetical leak \(X_{j,p}\) calculated with the model from the assumed key \(J\). In the Hamming weight model [2], the hypothetical leakage \(X_{j,p}\) of the power consumption evaluating an S-box is represented by the value \(X_{j,p}=HW(F(j\oplus p))\), where \(F\) is the S-box, \(p\) represents the clear text and \(j\) is the assumed subkey to encrypt the plain text.  
S-boxes have a set of properties that allow for the evaluation of their cryptographic quality, such as the high degree of nonlinearity (NL) that protects against linear attacks. The _coefficient of confusion_ (CC) and the _confusion coefficient variance_ (CCV) are two of the used metrics to measure resistance to differential power attacks (DPA). The coefficient of confusion (CC) theoretical metric was introduced by [PERSON] et al. in 2012 [21], who defined the confusion coefficient \(\kappa\) over two keys \((k_{i},k_{j})\) as:  
\[\kappa=\kappa(k_{i},k_{j})=Pr[(L\mid k_{i})\
eq(L\mid k_{j})]=\frac{N_{(L\mid k _{i})\
eq(L\mid k_{j})}}{N_{t}}, \tag{1}\]  
where \(N_{t}\) is the total number of values for the relevant cipher-text bits and \(N_{(L\mid k_{i})\
eq(L\mid k_{j})}\) is the number of occurrences for which different key hypotheses \(k_{i}\) and \(k_{j}\) result in different \(L\) values. In the DPA model, \(L\) has only two possible outcomes 0 and 1, but, in other power attack models, \(L\) can take more than two values. Then, in [22], the authors defined a general confusion coefficient as:  
\[\kappa(k_{i},k_{j})=E[(L\mid k_{i}-L\mid k_{j})^{2}]. \tag{2}\]  
Particularly, under the DPA model, \(E[(L\mid k_{i}-L\mid k_{j})^{2}]\) becomes \(Pr[(L\mid k_{i})\
eq(L\mid k_{j})]\).  
In [15], [PERSON] et al. considered \(\kappa(k_{i},k_{j})\) equal to the expected value \(E_{P}\) (among all the possible \(p\) plain texts) of the distance between the power leaks \(L(F(k_{i}\oplus p))\) and \(L(F(k_{j}\oplus p))\), using the pair of keys \(k_{i}\) and \(k_{j}\), i.e.,  
\[\kappa(k_{i},k_{j})=E_{P}\Big{[}L(F(k_{i}\oplus p)-L(F(k_{j}\oplus p))^{2} \Big{]}, \tag{3}\]  
and proposed to take a new theoretical metric as the variance (\(\sigma^{2}\)) of the CC vector over all possible pairs of keys:  
\[CCV(F)=\sigma^{2}\big{[}\overline{k}\big{]}=\sigma^{2}\big{[}\kappa(k_{i},k_{ j})\mid\forall i<j\big{]}. \tag{4}\]  
When using the Hamming weight leakage model as the \(L\) function, the CCV is:  
\[CCV(F)=\sigma^{2}\Big{[}E_{P}\Big{[}(HW(F(k_{i}\oplus p))-HW(F(k_{j}\oplus p ))^{2}\Big{]}\big{|}\ \forall\ i<j\Big{]} \tag{5}\]We expect that arbitrary keys, different from a real key, will look the same for the DPA attack at a higher value of variance. It increases the DPA resistance of the S-box [22; 23].  
Next, we recall the Stirling formula for factorial calculation. The value of \(n!\) grows extremely quickly, but, for large values of \(n\), it can be estimated using the well-known Stirling formula (see Table 1), the full proof of which appears in [24],  
\[n!\approx\sqrt{2\pi n}\ n^{n}\ e^{-n}, \tag{6}\]  
which, using base 10 logarithm, can be expressed equivalently as:  
\[n!=10^{\frac{1}{2}\log(2\pi)+\frac{1}{2}\log(n)+n\log(n)-n\log(e)}. \tag{7}\]  
A refinement of the Stirling formula, in terms of lower and upper bounds is given by  
\[(\sqrt{2\pi}\cdot n^{n+\frac{1}{2}}\cdot e^{-n})(e^{(12n+1)^{-1}})<n!<(\sqrt{2 \pi}\cdot n^{n+\frac{1}{2}}\cdot e^{-n})(e^{(12n)^{-1}}). \tag{8}\]