## CryptoDB

### Paper: On the hardness of the NTRU problem

Authors: Alice Pellet-Mary , CNRS and University of Bordeaux Damien Stehlé , ENS de Lyon DOI: 10.1007/978-3-030-92062-3_1 Search ePrint Search Google Slides ASIACRYPT 2021 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.
##### 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
}