### On Module Unique-SVP and NTRU

##### 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.

Available format(s)
Category
Foundations
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
History
2022-09-15: revised
See all versions
Short URL
https://ia.cr/2022/1203

CC BY

BibTeX

@misc{cryptoeprint:2022/1203,
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{https://eprint.iacr.org/2022/1203}},
url = {https://eprint.iacr.org/2022/1203}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.