Countermeasures against Power Analysis Attacks for the NTRU Public Key Cryptosystem

Mun-Kyu LEE  Jeong Eun SONG  Dooho CHOI  Dong-Guk HAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A    No.1    pp.153-163
Publication Date: 2010/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.153
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Cryptanalysis
NTRU,  power analysis attack,  simple power analysis,  correlation power analysis,  countermeasure,  

Full Text: PDF(625.7KB)>>
Buy this Article

The NTRU cryptosystem is a public key system based on lattice problems. While its theoretical security has been well studied, little effort has been made to analyze its security against implementation attacks including power analysis attacks. In this paper, we show that a typical software implementation of NTRU is vulnerable to the simple power analysis and the correlation power analysis including a second-order power attack. We also present novel countermeasures to prevent these attacks, and perform experiments to estimate the performance overheads of our countermeasures. According to our experimental results, the overheads in required memory and execution time are only 8.17% and 9.56%, respectively, over a Tmote Sky equipped with an MSP430 processor.