Cryptanalysis of NTRU where the private polynomial has one or more consecutive zero coefficients
Hatem M. Bahig, Ashraf Bhery, Dieaa I. Nassr · Journal of Discrete Mathematical Sciences and Cryptography · 2019
Let h and (f, g) be the public and private keys of NTRU respectively. We present a new lattice to attack NTRU when the private polynomial g has one or more consecutive coefficients which are equal zeros, i.e., zero patterns. The target vector of the new lattice contains the private polynomial f, and the ratio between the size of the target vector and the expected size of a shortest non-zero vector in the new lattice is smaller than the ratio declared in the previous results. The zero patterns are not necessarily of the same or long lengths. Experimental results show that our attack succeeded to cryptanalyze NTRU faster than the previous attacks.