Paper 2022/1203

On Module Unique-SVP and NTRU

Joël Felderhoff, Inria Lyon, École Normale Supérieure de Lyon
Alice Pellet-Mary, Institut de Mathématiques de Bordeaux, Centre National de la Recherche Scientifique, Inria Bordeaux - Sud-Ouest Research Centre
Damien Stehlé, École Normale Supérieure de Lyon, Institut Universitaire de France

The NTRU problem can be viewed as an instance of finding a short non-zero vector in a lattice, under the promise that it contains an exceptionally short vector. Further, the lattice under scope has the structure of a rank-2 module over the ring of integers of a number field. Let us refer to this problem as the module unique Shortest Vector Problem,or mod-uSVP for short. We exhibit two reductions that together provide evidence the NTRU problem is not just a particular case of mod-uSVP, but representative of it from a computational perspective. First, we reduce worst-case mod-uSVP to worst-case NTRU. For this, we rely on an oracle for id-SVP, the problem of finding short non-zero vectors in ideal lattices. Using the worst-case id-SVP to worst-case NTRU reduction from Pellet-Mary and Stehlé [ASIACRYPT'21],this shows that worst-case NTRU is equivalent to worst-case mod-uSVP. Second, we give a random self-reduction for mod-uSVP. We put forward a distribution D over mod-uSVP instances such that solving mod-uSVP with a non-negligible probability for samples from D allows to solve mod-uSVP in the worst-case. With the first result, this gives a reduction from worst-case mod-uSVP to an average-case version of NTRU where the NTRU instance distribution is inherited from D. This worst-case to average-case reduction requires an oracle for id-SVP.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Contact author(s)
joel felderhoff @ ens-lyon fr
alice pellet-mary @ math u-bordeaux fr
damien stehle @ ens-lyon fr
2022-09-15: revised
2022-09-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joël Felderhoff and Alice Pellet-Mary and Damien Stehlé},
      title = {On Module Unique-SVP and NTRU},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1203},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.