Paper 2021/821
On the hardness of the NTRU problem
Alice Pellet-Mary and Damien Stehlé
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.
Metadata
- Available format(s)
-
PDF
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2021
- Contact author(s)
-
alice pellet-mary @ math u-bordeaux fr
damien stehle @ ens-lyon fr - History
- 2021-10-05: revised
- 2021-06-16: received
- See all versions
- Short URL
- https://ia.cr/2021/821
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/821,
author = {Alice Pellet-Mary and Damien Stehlé},
title = {On the hardness of the {NTRU} problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/821},
year = {2021},
url = {https://eprint.iacr.org/2021/821}
}
