A subfield lattice attack on overstretched NTRU assumptions

Abstract: 

Many practical lattice-based cryptosystems are based on assumptions on structured lattices such as the NTRU lattice. We describe a subfield lattice attack on overstretched NTRU assumptions. The attack exploits the presence of a subfield to solve overstretched versions of the NTRU assumption: norming the public key down to a subfield may lead to an easier lattice problem and any sufficiently good solution may be lifted to a short vector in the full NTRU-lattice.

The talk is based on a joint work with Martin Albrecht and Léo Ducas.