What is the most efficient attack on NTRU?

Question

So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one? Is it possible to use the LLL to speed up the process?

Answer 1

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems.

Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one?

The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-in-the-middle attack from Nick Howgrave-Graham at Crypto 07, available at: http://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9

In this type of attacks, one performs partial lattice reduction on the NTRU lattices, and then uses a meet-in-the-middle search on the remaining part of the lattice. It combines the strength of both techniques.

For a given NTRU lattice, one need to fine-tune the parameters of the hybrid attack, so that the effort to do lattice reduction is the same as the effort to search. The latest analysis of this attack against NTRU cryptosystems can be found from: http://eprint.iacr.org/2015/708

Is it possible to use the LLL to speed up the process?

Exactly. One can view the lattice reduction part as a pre-processing of a searching attack, which allows one to reduce the searching space.

PS: LLL algorithm is not strong enough for large dimensional NTRU lattice, even in the partially reduced scenario. One needs to use the BKZ/BKZ2.0 algorithms.