NTRU Prime

Abstract

📜 Abstract

Several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the rings used in those cryptosystems. The same structures are also used in the leading proposals for post-quantum lattice-based cryptography, including the classic NTRU cryptosystem and typical Ring-LWE-based cryptosystems. This paper proposes NTRU Prime, which tweaks NTRU to use rings without these structures; proposes Streamlined NTRU Prime, which optimizes NTRU Prime from an implementation perspective; finds high-security post-quantum parameters for Streamlined NTRU Prime; and optimizes a constant-time implementation of those parameters. The performance results are surprisingly competitive with the best previous speeds for lattice-based cryptography.

Description

✨ Summary

The paper proposes NTRU Prime, a modification of NTRU intended to reduce exposure to attacks that exploit algebraic structure in commonly used rings. It recommends using a prime-degree polynomial with a large Galois group, specifically (x^p-x-1), together with a prime modulus (q) for which the polynomial remains irreducible modulo (q). This makes the quotient a field and removes several useful factorizations, subfields, homomorphisms, and automorphisms present in classic NTRU and many Ring-LWE constructions.

The paper then presents Streamlined NTRU Prime, a key-encapsulation mechanism optimized for implementation. Its design uses small ternary polynomials, rounded ciphertexts, SHA-512-derived session keys and key confirmation, and a decapsulation procedure that verifies the recovered input. For the concrete parameter set ((p,q,t)=(739,9829,204)), the authors claim a conservative estimated pre-quantum security level of (2^{215}), giving margin above their target of more than (2^{128}) post-quantum security. The bound (q\geq48t+1) guarantees correct decoding for all valid inputs, avoiding the decryption-failure behavior that complicates many lattice-based systems.

The implementation replaces number-theoretic transforms with a combination of Toom-6 multiplication, refined Karatsuba multiplication, schoolbook multiplication at the lowest level, and vectorization on Intel Haswell. The reported multiplication cost is approximately 50,000 cycles per operation, with a public key of about 1,232 bytes and a ciphertext of about 1,141 bytes for the case-study parameters. The broader engineering message is that conservative algebraic choices need not impose a prohibitive performance penalty when the multiplication strategy and encoding are redesigned together.

The later sntrup761 instantiation of Streamlined NTRU Prime was incorporated into hybrid SSH key exchange implementations. The protocol was implemented in TinySSH and OpenSSH, became the default OpenSSH key-exchange method in 2022, and was subsequently documented as the widely deployed hybrid sntrup761x25519-sha512 in RFC 9941, published in April 2026. (datatracker.ietf.org) The paper therefore influenced both subsequent implementation work on constant-time NTRU Prime and practical deployment of post-quantum protection in SSH. Later implementation and hardware research continues to optimize sntrup761, including polynomial multiplication and hardware acceleration. (ntruprime.cr.yp.to)