# Single Trace Side Channel Analysis on NTRU Implementation
## 3 Proposed Single Trace Side Channel Analysis on NTRU Implementation
### NTRU Open Source  
The integral parts of NTRU implementation are the way to store polynomials and a polynomial multiplication. **Representing Polynomials**  
To store a polynomial \(f\) of the private key, NTRU Open Source stores the degree of indeterminant \(x\) whose coefficient is \(-1\) or \(1\). Because the addition is computed according to the degree of \(-1\) and \(1\), it is possible to operate without the degree of \(0\). Thus, the private key array first stores all the degree whose coefficient is \(1\) and then it stores all the degree where its coefficient is \(-1\) in an array. For example, if \(f=x^{3}-x+1\), then the array of \(f\) would be \(\{0,3,1\}\). The polynomial in general, is stored such that the coefficient of the \(x\)th degree is the \(x\)th element in an array. For example, the polynomial \(e=3x^{4}-x^{2}+9x-5\) represent as \(\{-5,9,-1,0,3\}\). **Polynomial Multiplication**  
For efficiency, the private key is set as \(f=pF+1\) and \(F\) is divided into three trinary polynomials \(F=F_{1}\cdot F_{2}+F_{3}\), \(F_{1},F_{2},\text{ and }F_{3}\in\mathcal{L}_{F}\). The advantage of splitting \(F\), is that it lowers the hamming weight of polynomials so that the multiplication could be speed up [13; 30]. Consequently, the decryption of NTRU Open Source performs as in Equation (7) considering the order of multiplication. \[a=f\cdot e=(1+pF)\cdot e=(1+p(F_{1}\cdot F_{2}+F_{3}))\cdot e=e+p(((e\cdot F_{ 1})\cdot F_{2})+(e\cdot F_{3})) \tag{7}\]  
Computation of Equation (7) is represented in Algorithm 1 and algorithm for polynomial multiplication is in Algorithm 2. ```
0: The trinary polynomials \(F_{1},F_{2},F_{3}\) and \(e\in R\) with degree \(N\)\(\triangleright\)\(F_{1},F_{2},F_{3}\) is a private key polynomial satisfied \(f=1+p(F_{1}\cdot F_{2}+F_{3})\)
0: message \(m=f\cdot e\pmod{q}=(1+(F_{1}\cdot F_{2}+F_{3}))\cdot e\pmod{q}\)
1:\(t\leftarrow\) Algorithm \(2(F_{1},e)\)\(\triangleright\) Algorithm 2 is polynomial multiplication
2:\(t\leftarrow\) Algorithm \(2(F_{2},t)\)
3:\(u\leftarrow\) Algorithm \(2(F_{3},e)\)
4:for\(0\leq i<N\)do
5:\(v_{i}\leftarrow(t_{i}+u_{i})\pmod{q}\)\(\triangleright\) add \(t\) and \(u\)
6:endfor
7:for\(0\leq i<N\)do
8:\(m_{i}\leftarrow(e_{i}+p*v_{i})\pmod{q}\)\(\triangleright\)\(*\) is a word multiplication
9:endfor
10:return\(m\)
```  
**Algorithm 1** Decryption in NTRU Open Source  
The input \(b\) of Algorithm 2 is formed in a way such that the degree having coefficient \(1\) is stored in ascending order and then degree having \(-1\) is stored. The polynomial multiplication starts with the smallest degree where its coefficient equals to \(-1\) and add cipher-text to the initialized array. Since the result must be reduced modulo \((x^{N}-1)\), this implementation performs the addition from the beginning to \((N-1)\) and restarts for the \(0\)th element in an array when the degree exceeds \(N\). After the modular operation, the sign is reversed and the same steps are repeated on for the degree havingcoefficient 1. Lastly, the \((\text{mod }q)\) operation is performed by AND(\(\wedge\)) \((q-1)\) since the \(q\) is set as power of 2.