International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On Module Unique-SVP and NTRU

Authors:
Joël Felderhoff , Inria
Alice Pellet-Mary , CNRS and université de Bordeaux
Damien Stehlé , ENS de Lyon
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2022
Abstract: 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.
BibTeX
@inproceedings{asiacrypt-2022-32459,
  title={On Module Unique-SVP and NTRU},
  publisher={Springer-Verlag},
  author={Joël Felderhoff and Alice Pellet-Mary and Damien Stehlé},
  year=2022
}