# Single Trace Analysis against HyMES by Exploitation of Joint Distributions of Leakages
## 2 Related Works
### Code-Based Cryptography
#### 2.2.1 McEliece Cryptosystem  
The McEliece cryptosystem was the first code-based public-key cryptosystem proposed by McEliece in 1978 [4]. Although the algorithm states that any error-correcting codes can be used, only McEliece with Goppa codes has resisted cryptanalysis to date [14; 15]. In this paper, we define classical McEliece as McEliece with Goppa code. The encryption and decryption processes of McEliece are respectively described in Algorithms 1 and 2. In step 2, the generator matrix \(G\) corresponding to the code \(C\) is a matrix consisting of the basis sequences necessary for generating \(C\). Therefore, \(k\) represents the dimension of code \(C\). \(G\) is computed by using Goppa polynomial of degree \(t\), which is the primary part of the public key. Scrambling matrix \(S\) and a permutation matrix \(P\) need to hide the algebraic structure of \(G\). These are generated randomly and multiplied with \(G\)[4]. \(HW(e)\) is the number of \(1\) when \(e\) is expressed in binary. ```
0:\(M\), \(K_{pub}=(\hat{G}=SGP,t)\)
0: Ciphertext \(c\)
1: Represent the message \(M\) as \(k\)-bit vector \(m\)
2: Generate a random \(n\)-bit vector \(e\). \(HW(e)\leq t\)
3: return \(c=m\times\hat{G}+e\)
```  
**Algorithm 1** Classical McEliece : Encryption  
```
0:\(c\), \(K_{sec}=(G,S^{-1},P^{-1})\)
0: Message \(M\)
1: Compute the \(\hat{c}=c\times P^{-1}\)
2: Compute the syndrome \(S_{\hat{c}}\)
3: Obtain a \(k\)-bit \(\hat{m}=m\times S\) from \(S_{\hat{c}}\) using decoding algorithm \(D_{Goppa}(\hat{c})\)
4: Compute the \(m=\hat{m}\times S^{-1}\)
5: Represent the \(m\) as a message \(M\)
6: return \(M\)
```  
**Algorithm 2** Classical McEliece : Decryption  
```
0:\(c\), \(K_{sec}=(G,S^{-1},P^{-1})\)
0: Message \(M\)
1: Compute the \(\hat{c}=c\times P^{-1}\)
2: Compute the syndrome \(S_{\hat{c}}\)
3: Obtain a \(k\)-bit \(\hat{m}=m\times S\) from \(S_{\hat{c}}\) using decoding algorithm \(D_{Goppa}(\hat{c})\)
4: Compute the \(m=\hat{m}\times S^{-1}\)
5: Represent the \(m\) as a message \(



#### 2.2.2 HyMES (Hybrid McEliece Scheme)

The HyMES was proposed by [PERSON] and [PERSON], who were members of the SECRET team at the INRIA Lab in 2008 [6]. The HyMES is a variant of the McEliece cryptosystem that provides a smaller key size and faster encryption rate than McEliece for the same security level. The key generation algorithm of HyMES is described below. In step 1 of Algorithm 3, Goppa polynomial is chosen as an irreducible polynomial. In this case, since the minimum distance of the code satisfies \(d_{c}\leq 2t+1\), a valid user can correct a maximum of \(t\) errors. In step 2, the number of supports \(n\) is used as the number of all elements of \(GF(2^{m})\), and the supports are selected randomly from 0 to \(2^{m-1}\) in order. The public-key size of HyMES is \(k\times(n-k)\), which is reduced to \(k\times k\) relative to the Classical McEliece whose public-key size is \(k\times n\). The encryption and decryption algorithms are denoted in Algorithms 4 and 5, respectively. ```
0:\(t,n,m\)
0:\(K_{sec}\), \(K_{pub}\)
1: Generate a random monic polynomial \(g(z)\) as the Goppa polynomial \(g(z)=z^{t}+c_{t-1}z^{t-1}+...+c_{1}z+c_{0}\), \(\deg(g(z))=t\), \(c_{i}\in GF(2^{m})\)
2: Randomly choose the support \(L=\{\alpha_{0},...,\alpha_{n-1}\}\), \(\alpha_{i}\in GF(2^{m})\), \(g(\alpha_{i})\
eq 0\)
3: Compute the parity check matrix \(\hat{H}\)
4: Convert the parity check matrix to the systematic form \(\hat{H}_{sys}=\hat{S}\hat{H}\hat{P}=(Q^{T}\mid I_{n-k})\)
5: If the parity check matrix \(\hat{H}\) is not converted to the systematic form \((Q^{T}\mid I_{n-k})\), go back to step 1
6: Replace support \(L\) with \(L_{sec}=L\hat{P}\) using \(\hat{P}\)
7: Compute \(G_{sys}=(I_{k}\mid Q)=SGP\)
8: return \(K_{sec}=(g(z),L_{sec}),K_{pub}=G_{sys}=(I_{k}\mid Q)\)
```
**Algorithm 3** HyMES : Key Generation
```
0:\(M\), \(K_{pub}=G_{sys}=(I_{k}\mid Q)\)
0: Ciphertext \(c\)
1: Represent the message \(M\) as \(k\)-bit vector \(m\)
2: Generate a random \(n\)-bit vector \(e\).