First-order collision attack on protected NTRU cryptosystem

NTRU cryptosystem has been widely used in microsystems with low performance in computation. In 2010 Lee et al. gave several power analysis attacks on NTRU and three countermeasures, where they argued that only second-order power analysis can break their first countermeasure, and the combination of the first and third countermeasure is secure. In this paper we give efficient first-order collision attacks against all their countermeasures. Besides a gain of 108.4% and 78% in efficiency, our attacks cannot be avoided by any padding scheme. Furthermore, we discuss some countermeasures preventing our attacks.