Welcome to the resource topic for 2021/821
Title:
On the hardness of the NTRU problem
Authors: Alice Pellet-Mary, 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.
ePrint: https://eprint.iacr.org/2021/821
Talk: https://www.youtube.com/watch?v=oTNGVASYHfk
Slides: https://iacr.org/submit/files/slides/2021/asiacrypt/asiacrypt2021/164/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .