A subfield lattice attack on overstretched NTRU assumptions


Shi Bai


INRIA, France


Wed, 21/09/2016 - 2:00pm


RC-4082, The Red Centre, UNSW


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.

School Seminar Series: