# Single Trace Side Channel Analysis on NTRU Implementation
## 4 Countermeasure
### Countermeasure against NTRUEncrypt Implementation  
The proposed countermeasure in this paper uses three tables initialized with a random number. The countermeasure prevents not only proposed attack in this paper but also the other previous attacks with a decreased number of computations compared to the submitted implementation. The NTRUEncrypt first calculates the private key \(f(=pF+1)\) then multiplies \(f\cdot e\). However, the proposed countermeasure uses a trinary polynomial \(F\), and computes \(p\times F\cdot e\) and adds \(e\) to decrypt the cipher-text. This is expressed in Equation (8).  
\[m=f\cdot e=(pF+1)\cdot e=pe\cdot F+e \tag{8}\]  
To compute \(f\times e\), the proposed countermeasure first computes \(p\times e\) and temporarily save the value. After that, it updates the output of computation in the three tables according to \(-1,0,1\) from the trinary polynomial \(F\). Then the table of the coefficient \(-1\) is subtracted from the table of the coefficient \(1\). During the accumulation, a start index is sought by \((i+j)\pmod{N}\) to process \(\pmod{x^{N}-1}\) at the same time for increased efficiency.  
For the side channel resistance, by encoding the trinary polynomial of the private key \(F^{\prime}=enc(F)\) at the storage step, it relieves the difference in power consumption coming from loading \(-1\) and \(0,1\). The encoding function \(enc\) is chosen by considering the physical property. The proposed countermeasure uses an encoding function as \(enc(-1)=1,enc(0)=2,\text{ and }enc(1)=4\), to have the same hamming weight. Then the trinary polynomial would be represented with \(1,2,\text{ and }4\) at the proposed algorithm. Algorithm 5 describes the above procedure.  
```
0: Trinary polynomial \(F^{\prime}\) an encoding of \(F\in\mathcal{L}_{f}\), cipher-text \(e\in\mathcal{R}\)
0: message \(m=f\cdot e\pmod{q}\)
1:for\(0\leq i<N\)do
2:\(PE_{i}\gets p\times e_{i}\)
3:\(T_{i}[1]\gets r\)\(\triangleright\)\(r\) is a random
4:\(T_{i}[2]\gets r\)
5:\(T_{i}[4]\gets r\)
6:endfor
7:for\(0\leq i<N\)do
8:for\(0\leq j<N\)do
9:\(T_{i+j\pmod{N}}[F_{i}^{\prime}]\gets T_{i+j\pmod{N}}[F_{i}^{\prime}]+PE_ {j}\)
10:endfor
11:endfor
12:for\(0\leq i<N\)do
13:\(m_{i}\leftarrow(T_{i}[4]-T_{i}[1]+e_{i})\pmod{q}\)
14:endfor
15:return\(m\)
```  
**Algorithm 5** Countermeasure Applied Decryption of NTRUEncrypt  
At the final step 13, a subtraction of \(1\) and \(-1\), an addition of \(e\) and \(\pmod{q}\) could be processed at once. Since \(q\) is a power of \(2\) in the proposed parameters, \(\pmod{q}\) can be operated as AND (\(\wedge\)). In Algorithm 5, different tables are accessed according to the coefficient of \(F\). However, since the same operation is performed regardless of the coefficients, it can be considered that there is no difference in the power consumption which depends on \(-1,0,\text{ and }1\). Furthermore, as the three tables are initialized with the same random number (steps 3 to 5), the algorithm also prevents SPA and CPA proposed in [7]. SPA can be prevented by initializing the array to hold the result with non-zero values and removing the operations that add zero and non-zero values. Also, choosing the non-zero value for initial as random, the algorithm is protected from CPA because the intermediate value cannot be guessed. Whenthree tables initialized with the same random non-zero value, the random values can be removed without additional computation, as in step 13.