Séminaire de Cryptographie

Accueil     Présentation     Archives

Joël Felderhoff

On module uSVP and NTRU

The NTRU problem asks to find f and g two polynomials with small coefficients given h = g/f mod q, where all the polynomials are taken modulo some irreducible polynomial P defining a number field. This problem is a particular instance of a Shortest Vector Problem in a Module lattice of rank 2 in which there exists a particularly dense submodule of rank 1. Although NTRU has first been proposed as a security assumption in 1998, its relationship to other classical module lattice problems is not yet well understood. It was proven in 2021 that ideal-SVP reduces to average-case-NTRU, and that average-case-NTRUmod (consisting in recovering the dense rank-1 submodule of the NTRU module) reduces to decision-NTRU. In this follow-up, we consider Module-uSVP, the Module version of the unique-Shortest Vector Problem. This problem asks to find a short vector in a module lattice, provided that it contains a dense submodule of rank 1. We then propose a reduction from module-uSVP to NTRU. This is the presentation of a join work with Alice Pellet--Mary and Damien Stehlé, avaible at eprint.iacr.org/2022/1203