Paper 2019/100

Correlation Power Analysis on NTRU Prime and Related Countermeasures

Wei-Lun Huang and Jiun-Peng Chen and Bo-Yin Yang

Abstract

We perform correlation power analysis on ideal-lattice-based cryptosystems featuring product scanning, for example the reference implementation of NTRU Prime, a Round 2 candidate in the NIST PQC Competition. We also discuss three corresponding countermeasures in detail. The proposed approach achieves full private-key recovery in a highly efficient way with few traces. For each defensive strategy, its effectiveness is validated, and its side-channel resistance is evaluated by the TVLA general tests. The correlation power analysis exploits the vulnerabilities in product-scanning-based polynomial multiplications. The statistical analysis program in C++ takes time linear in the input size on average and practically less than 8 seconds on an ordinary laptop to reveal all the coefficients of each private-key polynomial. The three countermeasures together demonstrate the tradeoff between security and performance. The predictions about their effectiveness, performance, and side-channel resistance are supported by the correlation power analysis and the TVLA general tests based on thousands of traces.