International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the hardness of the NTRU problem

Authors:
Alice Pellet-Mary , CNRS and University of Bordeaux
Damien Stehlé , ENS de Lyon
Download:
DOI: 10.1007/978-3-030-92062-3_1
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound. We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31400,
  title={On the hardness of the NTRU problem},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92062-3_1},
  author={Alice Pellet-Mary and Damien Stehlé},
  year=2021
}