You are looking at a specific version 20210616:134209 of this paper. See the latest version.

Paper 2021/821

On the hardness of the NTRU problem

Alice Pellet-Mary and Damien Stehlé

Abstract

The 25 year-old NTRU problem is a mainstream security foundation 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
Preprint. MINOR revision.
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.