A hybrid lattice-reduction and meet-in-the-middle attack against NTRU

To date the NTRUEncrypt security parameters have been based on the existence of two types of attack: a meet-in-the-middle attack due to Odlyzko, and a conservative extrapolation of the running times of the best (known) lattice reduction schemes to recover the private key. We show that there is in fact a continuum of more efficient attacks between these two attacks. We show that by combining lattice reduction and a meet-in-the-middle strategy one can reduce the number of loops in attacking the NTRUEncrypt private key from 2(84.2) to 2(60.3), for the k = 80 parameter set. In practice the attack is still expensive (dependent on ones choice of cost-metric), although there are certain space/time trade-offs that can be applied. Asymptotically our attack remains exponential in the security parameter k, but it dictates that NTRUEncrypt parameters must be chosen so that the meet-in-the-middle attack has complexity 2(k) even after an initial lattice basis reduction of complexity 2(k).