NTRU standard

Propose Edit

Updated:

NTRU is a computational problem introduced in 1996 by Hoffstein, Pipher, and Silverman [1]. Predating Learning with Errors by nearly a decade, NTRU relies on the hardness of finding short vectors in a specific class of structured ideal lattices known as “NTRU lattices”. It serves as computational hardness assumption for key exchange mechanisms, public-key encryption schemes, and unforgeable signatures.

Definition

The NTRU problem comes in two versions: Search and Decision.

Search NTRU$_{q, \chi, \mathcal{R}}$

Let $\mathcal{R}_q$ be the polynomial ring $\ZZ_q[X]/(f(X))$ and let $f,g \in \mathcal{R}$ be short polynomials sampled from some distribution $\chi$, subject to $f$ being invertible in $\mathcal{R}_q$. Define $h=g/f \in \mathcal{R}_q$. Given $h$, an adversary is asked to find $f$ and $g$ (or another pair of short polynomials $f’, g’$ satisfying $h= g’/f’$).

The distribution $\chi$ is usually chosen as the uniform tertiary distribution $U(\set{-1,0,1})$. Classical NTRU picks the function $f$ as $f(X) = X^d - 1$ with prime $d$ and $q$ being a power of two [1]. Similar to R-LWE, several modern papers rather choose $f(X) = X^d + 1$ with $d$ a power of two and prime modulus $q \in 1 + 2d\ZZ$ to enable the NTT fast matrix multiplication. Furthermore, there exists parameter choices of NTRU such as NTRU Prime [2] with $\mathcal{R} = \ZZ[X] / (X^d - X - 1)$ to reduce specific attack surfaces.

Decision NTRU$_{q, \chi, \mathcal{R}}$

Let $\mathcal{R}_q$ be the polynomial ring $\ZZ_q[X]/(f(X))$ and let $f,g \in \mathcal{R}$ be short polynomials sampled from some distribution $\chi$, subject to $f$ being invertible in $\mathcal{R}_q$. An adversary is asked to distinguish between the NTRU distribution $h = g/f \in \mathcal{R}_q$ and a uniform distribution over $\mathcal{R}_q$.

The decisional version of NTRU is also referred to as Decisional Small Polynomial Ratio (DSPR) assumption [3].

Modern Utilisation

NTRU is frequently utilised either in combination with or as a highly efficient replacement for SIS or LWE assumptions. This approach typically offers more efficient parameter sets as a trade-off for relying on the more structured cryptographic assumption NTRU. Notable examples of this include:

  • Falcon: The signature scheme is built upon the GPV framework, which is proven secure based on SIS. Falcon specifically instantiates the framework over NTRU lattices for smaller parameters.
  • NTRU-ISIS$_f$: An assumption utilised to construct efficient anonymous credentials (as detailed in Section 7 of [4]). By relying on this NTRU-instantiated variant rather than ISIS$_f$ itself, the authors are able to achieve better concrete parameters.

Note: Specific “derived” or “hybrid” assumptions such as NTRU-ISIS$_f$ are currently considered out of scope for entries in the Lattice Assumption Zoo to keep the focus on the fundamental ideas behind new assumptions and prevent artificial expansion.

Hardness

Compared to lattices utilised in SIS and LWE assumptions, NTRU lattices contain an unusually short vector as well as all vectors corresponding to rotations of $(f,g)$ and their linear combinations. Thus, NTRU lattices contain an unusually dense sublattice.

For $\chi$ chosen as a discrete Gaussian distribution $D_{\ZZ^d, \sigma}$, $s > \sqrt{q} \cdot \poly{n}$, and $f(X) = X^d + 1$ with $d$ a power of two, the NTRU distribution is statistially close to uniform over all invertible elements in $\mathcal{R}_q$ and this variant of decision NTRU is hard – even for unbounded adversaries [5]. This result was extended to all cyclotomic rings in [6].

Nevertheless, the reduction sketched out in Section 4.4.4 of [7] shows that R-LWE is at least as hard as NTRU, providing an upper bound to the hardness of NTRU.

After all, the hardness of NTRU crucially relies on the choice of $\chi$, $\mathcal{R}$ and $q$ as well as the specified wiggle room for the NTRU solution. There are several partial reductions to and from NTRU for specific choices of parameters as well as 25 years of cryptanalysis. Their results are decently summarised (and partially provided) in the following two papers:

Any reductions in this section should be reflected as an edge in the graph.

Constructions built from NTRU

  • Ring-LWE provides similar capabilities and operates on more general lattices.

References

  • [1]Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. 1998. NTRU: A Ring-Based Public Key Cryptosystem. In Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings (Lecture Notes in Computer Science), 1998. Springer, 267–288. https://doi.org/10.1007/BFB0054868
  • [2]Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. 2017. NTRU Prime: Reducing Attack Surface at Low Cost. In Selected Areas in Cryptography - SAC 2017 - 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers (Lecture Notes in Computer Science), 2017. Springer, 235–260. Retrieved from https://ia.cr/2016/461
  • [3]Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. 2012. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, 2012. ACM, 1219–1234. Retrieved from https://ia.cr/2013/094
  • [4]Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Alessandro Sorniotti. 2023. A Framework for Practical Anonymous Credentials from Lattices. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II (Lecture Notes in Computer Science), 2023. Springer, 384–417. Retrieved from https://ia.cr/2023/560
  • [5]Damien Stehlé and Ron Steinfeld. 2011. Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. In Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 27–47. Retrieved from https://ia.cr/2013/004
  • [6]Yang Wang and Mingqiang Wang. 2018. Provably Secure NTRUEncrypt over Any Cyclotomic Field. In Selected Areas in Cryptography - SAC 2018 - 25th International Conference, Calgary, AB, Canada, August 15-17, 2018, Revised Selected Papers (Lecture Notes in Computer Science), 2018. Springer, 391–417. https://doi.org/10.1007/978-3-030-10970-7_18
  • [7]Chris Peikert. 2016. A Decade of Lattice Cryptography. Found. Trends Theor. Comput. Sci. 10, 4 (2016), 283–424. Retrieved from https://ia.cr/2015/939
  • [8]Alice Pellet-Mary and Damien Stehlé. 2021. On the Hardness of the NTRU Problem. In Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I (Lecture Notes in Computer Science), 2021. Springer, 3–35. Retrieved from https://ia.cr/2021/821
  • [9]Martin Albrecht and Léo Ducas. 2021. Lattice Attacks on NTRU and LWE: A History of Refinements. Retrieved from https://ia.cr/2021/799
  • [10]Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, and William Whyte. 2003. NTRUSIGN: Digital Signatures Using the NTRU Lattice. In Topics in Cryptology - CT-RSA 2003, The Cryptographers’ Track at the RSA Conference 2003, San Francisco, CA, USA, April 13-17, 2003, Proceedings (Lecture Notes in Computer Science), 2003. Springer, 122–140. https://doi.org/10.1007/3-540-36563-X_9
  • [11]Joo Woo, Jonghyun Kim, Ga Hee Hong, Seungwoo Lee, Minkyu Kim, Hochang Lee, and Jong Hwan Park. 2026. NTRU+Sign: compact NTRU-based signatures using bimodal distributions. Des. Codes Cryptogr. 94, 1 (2026), 2. Retrieved from https://ia.cr/2025/106