# Single Trace Analysis against HyMES by Exploitation of Joint Distributions of Leakages
## 2 Related Works
### Code-Based Cryptography
#### 2.2.1 McEliece Cryptosystem
In Reference [6], the multiplication and division are computed by addition, subtraction, and modulus operations using the pre-computed log-table and exponentiation-table. Note that using the tables is more efficient than directly computing the exponentiations and logarithm values. The implementations of multiplication and division over \(GF(2^{m})\) are as shown in Algorithms 8 and 9, respectively. ```
0:\(a,b\in GF(2^{m})\), \(\exp[i]=\alpha^{i}\), \(\log[\alpha^{i}]=i\), \(i=0,...,2^{m}-1\ mod(d)=((d)\wedge(2^{m}-1))+((d)>>m)\)
0:\(a\times b\in GF(2^{m})\)
1:if \(a\) or \(b=0\)
2:\(a\times b\gets 0\)
3:else
4:\(a\times b\leftarrow\exp[mod(\log[a])+\log[b]]\)
5:end
6:return \(a\times b\)
```
**Algorithm 8** HyMES implementation : Multiplication over \(GF(2^{m})\)[6]

Now that the basic field operations have been explained, we present the method to recover \(g(z)\). To find \(g(z)\), we must find the coefficients \(g_{t-1},g_{t-2},...,g_{0}\) of all the orders of \(g(z)\). In this section, we only explain how to find \(g_{t-1}\), since the other coefficients are found with the same methods used for \(g_{t-1}\). The full recovery of \(g(z)\) using the joint distributions of leakages is described in Algorithm 10. Function \(l(k,a)\) is a function that returns \(\log[k\oplus a]\) by taking the elements \(k\) and \(a\) of \(GF(2^{m})\), while function \(\phi(v)\) takes \(v\) as input and returns the Hamming weight of \(v\). The value of \(a_{i}\) and \(b_{i}\) are the estimated Hamming weights of the input \(a\) and output \(b\) of the function \(l(k,a)\), respectively. When \(j=t-2,t-3\) in the step 3 loop of Algorithm 7, the operation process can be described as follows for \(i=0:2^{m}-1\). \[h_{0}[t-2] =g_{t-1}\oplus(\alpha_{0}\times h_{0}[t-1])\] \[h_{0}[t-3] =g_{t-2}\oplus(\alpha_{0}\times h_{0}[t-2])\] \[h_{1}[t-2] =g_{t-1}\oplus(\alpha_{1}\times h_{1}[t-1])\] \[h_{1}[t-3] =g_{t-2}\oplus(\alpha_{1}\times h_{1}[t-2])\] (6)... \[h_{2^{m}-1}[t-2] =g_{t-1}\oplus(\alpha_{2^{m}-1}\times h_{2^{m}-1}[t-1])\] \[h_{2^{m}-1}[t-3] =g_{t-2}\oplus(\alpha_{2^{m}-1}\times h_{2^{m}-1}[t-2]).\]



values of the actually used data are uniformly distributed, so it is necessary to use a sufficient amount of data. Finally, when the similarity between the theoretical joint distribution and the estimated joint distribution is compared, \(g_{t-1}^{\prime}\) with the highest similarity is selected as the real key \(g_{t-1}\). In this paper, we use the Harmonic Mean Distance, Inner Product Distance, and \(\chi\)-square Pearson Distance as the comparison method of distribution similarity. The definitions of the three similarity comparison methods are the same as Definition 5-7. **Definition 5. **_Harmonic Mean Distance (HMD) is as follows._

\[HMD(S(g,k),S_{d})= \begin{cases}1-2\sum_{i=0}^{i=n}\sum_{j=0}^{j=m}\frac{p_{i,j} f_{i,j}}{p_{i,j}+f_{i,j}},&p_{i,j}+f_{i,j}\
eq 0\\ 0,&p_{i,j}+f_{i,j}=0.\end{cases}  \tag{9}\]

**Definition 6. **_Inner Product Distance is as follows._

\[IPD(S(g,k),S_{d})=1-\sum_{i=0}^{i=n}\sum_{j=0}^{j=m}p_{i,j}f_{i,j}. \tag{10}\]

**Definition 7. **_\(\chi\)-square Pearson Distance is as follows._

\[\chi^{2}PD(S(g,k),S_{d})= \begin{cases}\sum_{i=0}^{i=n}\sum_{j=0}^{j=m}\frac{(p _{i,j}-f_{i,j})^{2}}{f_{i,j}},&f_{i,j}\
eq 0\\ 0,&f_{i,j}=p_{i,j}\\ \infty,&f_{i,j}=0\
eq p_{i,j}.\end{cases}  \tag{11}\]

### Recovering \(L_{sec}\)

In this section, we explain how to find the remaining secret key \(L_{sec}\) using \(g(z)\) obtained in Section 3.2. The process of finding \(L_{sec}\) is described in Algorithm 11. We explain the process of finding \(L_{sec}\) by recovering the first support value \(\alpha_{0}\) as a concrete example. The other support values can be analyzed using the same logic used to find \(\alpha_{0}\). When \(i=0\) in Algorithm 7, the operation process can be expressed by Equation (12).