Date de l'exposé : 23 juin 2023 (salle Jersey à l'ISTIC)
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
