Cryptology ePrint Archive: Report 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.

Category / Keywords:

Original Publication (with minor differences): IACR-ASIACRYPT-2021

Date: received 16 Jun 2021, last revised 5 Oct 2021

Contact author: alice pellet-mary at math u-bordeaux fr, damien stehle at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Version: 20211005:171019 (All versions of this report)

Short URL: ia.cr/2021/821


[ Cryptology ePrint archive ]