NTRU Lattice — Encryption, Basis and Security Explained

NTRU (N-th degree Truncated polynomial Ring Units) was introduced by Hoffstein, Pipher, and Silverman, first announced at the Crypto 1996 rump session and formally published at ANTS 1998. It is the oldest lattice-based public key system and the only one that has survived nearly 30 years of public cryptanalysis. NTRU's ring structure inspired the later Ring-LWE framework. Today it is the basis of FIPS 206 (Falcon / FN-DSA), one of NIST's post-quantum standards. The original paper is available at ntru.org.

NTRU differs from LWE in one important way: instead of adding noise to linear equations, it constructs a trapdoor directly from short polynomials in a ring. The resulting scheme is extremely compact — NTRU encryption and Falcon signatures have some of the smallest key and ciphertext sizes in post-quantum cryptography.

Intuition

In NTRU the private key is a pair of polynomials with small coefficients, and the public key is their quotient in a polynomial ring. Dividing is easy. Going back, recovering two small polynomials from their quotient, amounts to finding a short vector in a special lattice, and no efficient method for that is known.

The idea dates from 1996, which makes NTRU one of the oldest lattice cryptosystems still standing, and its keys and ciphertexts are compact.

The Ring Setting

NTRU works in the polynomial ring:

Definition 30 — NTRU Ring

Let $R = \mathbb{Z}[x]/(x^n - 1)$ (original NTRU) or $R = \mathbb{Z}[x]/(x^n + 1)$ (Falcon, with $n$ a power of 2). NTRU Prime instead uses $R = \mathbb{Z}[x]/(x^p - x - 1)$ with $p$ prime, a field chosen to avoid the extra algebraic structure of cyclotomic rings. Elements are polynomials of degree less than $n$ with integer coefficients. Multiplication in $R$ is polynomial multiplication with coefficient reduction. In the ring $R_q = R/qR$ , coefficients are further reduced modulo $q$ .

A polynomial in $R$ is called small if all its coefficients are in $\{-1, 0, 1\}$ (ternary) or have small absolute value. Small polynomials are the “short vectors” of NTRU.

NTRU Key Generation — Choosing f, g and Computing h

NTRU’s trapdoor is a pair of small polynomials whose ratio (in the ring) is the public key. Knowing either polynomial individually is not useful — you need both (or their ratio) to decrypt. The key generation process must ensure both invertibility (for correctness) and shortness (for security).

Construction 9 — NTRU Key Generation

Parameters: Ring $R = \mathbb{Z}[x]/(x^n - 1)$ (or $x^n + 1$ for Falcon), small modulus $p$ (typically 3), large modulus $q$ (typically a power of 2 or a prime, with $q \gg p$ ).

Step 1 — Choose secret polynomials: Sample small polynomials $f, g \in R$ with coefficients in $\{-1, 0, 1\}$ and approximately $n/3$ nonzero coefficients each. The sparsity and smallness of $f$ and $g$ is what makes the private key a “short vector” — the trapdoor.

Step 2 — Check invertibility: Require that $f$ is invertible in both $R_q = R/(q)$ and $R_p = R/(p)$ . Invertibility in $R_q$ is needed for key generation; invertibility in $R_p$ is needed for decryption. If either fails (which occurs with small probability), resample $f$ .

Step 3 — Compute inverses:
$F_q = f^{-1} \pmod{q}$ (polynomial inverse modulo $q$ )
$F_p = f^{-1} \pmod{p}$ (polynomial inverse modulo $p$ )

Both can be computed efficiently using the extended Euclidean algorithm for polynomials.

Step 4 — Compute public key:
$h = p \cdot F_q \cdot g \pmod{q}$

The public key $h$ is a uniformly random-looking element of $R_q$ . The private key is the pair $(f, F_p)$ .

Security intuition: Given $h = pF_qg$ , recovering $f$ or $g$ requires finding the short vector $(f, g)$ in the NTRU lattice (defined below). This is believed to be as hard as SVP in the NTRU lattice, for which no polynomial-time algorithm is known.

NTRU Encryption and Decryption

NTRU encryption hides a message polynomial inside a linear combination involving the public key. Decryption exploits the private key to cancel the blinding factor, leaving the message recoverable. The correctness condition is that all polynomials involved stay small enough to avoid modular wraparound.

Construction 10 — NTRU Encryption/Decryption

Encrypt message $m \in R_p$ (coefficients in $\{-(p-1)/2, \ldots, (p-1)/2\}$ ):

1. Sample a small random blinding polynomial $r \in R$ with coefficients in $\{-1, 0, 1\}$ .
2. Ciphertext: $e = r \cdot h + m \pmod{q}$ .

The blinding factor $r \cdot h$ masks the message completely — since $h$ looks random, so does $e$ to anyone who doesn’t know $f$ .

Decrypt ciphertext $e$ :

1. Compute $a = f \cdot e \pmod{q}$ . Expanding:

$a = f \cdot (rh + m) = f \cdot r \cdot (pF_q g) + f \cdot m = p \cdot rg + fm \pmod{q}$

2. Lift to integers: Since $f, g, r, m$ all have small coefficients, the polynomial $prg + fm$ has coefficients bounded by approximately $p \cdot \|rg\| + \|fm\| \ll q/2$ . This means the modular reduction mod $q$ has not wrapped around — we can lift $a$ to an integer polynomial with the same value.

3. Reduce mod $p$ : $a \pmod{p} = (prg + fm) \pmod{p} = fm \pmod{p}$ (since $p \cdot rg \equiv 0 \pmod{p}$ ).

4. Recover message: Multiply by $F_p = f^{-1} \pmod{p}$ :
$F_p \cdot (fm \pmod{p}) = m$ .

Correctness condition: The lift in step 2 succeeds as long as $\|prg + fm\|_\infty < q/2$ . Since all polynomials are short, this holds with overwhelming probability for appropriate parameter choices.

Decryption failure: If the error term $prg + fm$ wraps around mod $q$ in any coefficient, decryption fails. Parameters are chosen so that this probability is negligible (below $2^{-128}$ ).

The NTRU Lattice

NTRU’s security is formalized through the NTRU lattice. The private key $(f, g)$ forms an unusually short vector in a lattice defined by the public key $h$ . Breaking NTRU means finding this short vector.

Rendering diagram…

How the NTRU lattice hides the private key. The public key defines a 2n-dimensional lattice that anyone can construct. The secret pair is a very short vector inside it; an attacker must recover such a vector from the public basis.

Definition 31 — The NTRU Lattice

For NTRU with public key $h \in R_q$ and ring dimension $n$ , the NTRU lattice is the $2n$ -dimensional lattice:

$\Lambda_h = \{ (u, v) \in R^2 : v \equiv hu \pmod{q} \}$

In matrix form, the basis is:

$B_h = \begin{pmatrix} I & H \\ 0 & qI \end{pmatrix}$

where $H$ is the $n \times n$ circulant matrix with first row equal to the coefficients of $h$ (the rows of $B_h$ generate the vectors $(u, hu \bmod q)$ ).

Taking $h = g/f \pmod{q}$ as in Falcon (for the encryption key $h = pF_q g$ , use $h/p$ ), we have $g \equiv hf$ , so the private key gives the short vector $(f, g) \in \Lambda_h$ with $\|(f, g)\| \approx \sqrt{2n/3}$ for ternary keys, much shorter than the lattice’s expected shortest vector $\approx \sqrt{nq}$ . Recovering $(f, g)$ from $h$ is the NTRU problem.

NTRU Hardness — Lattice Structure and Resistance to Attacks

NTRU does not have a proven worst-case hardness reduction like LWE. Its security is based on the empirical observation that breaking NTRU requires solving SVP in the NTRU lattice — a fact supported by 28 years of public cryptanalysis but not proven by a reduction. This is the primary theoretical weakness relative to LWE-based schemes.

Why the NTRU Lattice Is Hard to Attack

The NTRU lattice $\Lambda_h$ is a $2n$ -dimensional lattice with a specific structure: it is a module lattice over the ring $R$ , meaning it has $n$ -fold symmetry that can be exploited algorithmically (making attacks faster) but also makes the lattice more regular (making it harder to distinguish the short vector from others).

The challenge: The private key $(f, g)$ is a vector of norm approximately $\sqrt{2n/3}$ (since each polynomial has $n/3$ nonzero $\pm 1$ coefficients). The expected shortest vector in the NTRU lattice from Gaussian heuristics has norm $\approx \sqrt{nq}$ . The ratio $\sqrt{nq} / \sqrt{2n/3} = \sqrt{3q/2}$ is large — the private key is far shorter than a “generic” short vector. This makes $(f, g)$ a uniquely short vector, but it also means BKZ must achieve a very small approximation factor to find it.

BKZ attack complexity: The best known attack applies BKZ- $\beta$ to the $2n$ -dimensional NTRU lattice. For Falcon-512 ( $n = 512$ , $q = 12289$ ), security is quoted as a Core-SVP estimate, $2^{0.292\beta}$ for the required block size $\beta$ . That figure is deliberately conservative (it counts a single SVP call and ignores memory), so it is not directly comparable to “128 bits”: NIST levels are defined relative to the cost of AES key search, and the Falcon team argues Falcon-512 meets Level 1 once the full attack cost is counted.

The NTRU fatigue point: As the ratio $q/n$ increases, the NTRU lattice becomes easier to attack via subfield attacks. The fatigue point is the threshold $q \approx n^{2.484}$ beyond which overstretched-NTRU attacks (Albrecht–Bai–Ducas 2016, Kirchner–Fouque 2017) beat the usual key-recovery estimates; the exponent 2.484 comes from Ducas–van Woerden (2021). Below the fatigue point, no polynomial-time algorithm is known. Falcon’s parameters are chosen well below this threshold: $q = 12289 \approx n^{1.5}$ for $n = 512$ ( $512^{1.5} \approx 11585$ ). Above the fatigue point (as in some NTRU-based FHE schemes with very large $q$ ), the subfield attack reduces the effective dimension to roughly $n/2$ , breaking the scheme. This ruled out NTRU as a basis for fully homomorphic encryption.

Lattice attacks (BKZ)

The strongest known attack on NTRU applies BKZ to the NTRU lattice to find the short vector $(f, g)$ . The NTRU lattice is a $2n$ -dimensional q-ary lattice with determinant $q^n$ . Security parameters are chosen so that BKZ needs a block size $\beta$ whose cost exceeds $2^{128}$ operations.

NTRU overstretched (above fatigue)

The “overstretched NTRU” attacks (Albrecht et al. 2016 and follow-ups) showed that NTRU with large modulus (above roughly $q > n^{2.484}$ , per Ducas–van Woerden 2021) can be broken using subfield lattice attacks — reducing the effective lattice dimension to $n/2$ . Falcon avoids this by using $q = 12289 \approx n^{1.5}$ — well below the fatigue point.

Hybrid meet-in-the-middle

Hybrid attacks combine lattice reduction with meet-in-the-middle search over the small coefficients of the private key. These are the most practical attacks for low dimensions. Falcon parameters are designed to keep this cost above $2^{128}$ .

From NTRU Encryption to Falcon Signatures

The NTRU lattice is the setting for Falcon (FIPS 206 / FN-DSA) — NIST’s second lattice signature standard alongside Dilithium. Falcon uses a “hash-and-sign” paradigm over the NTRU lattice rather than the Fiat-Shamir approach used by Dilithium.

Falcon: Hash-and-Sign over NTRU

Key generation: Generate an NTRU key pair $(f, g)$ with additional polynomials $(F, G)$ satisfying $fG - gF = q$ (the NTRU equation). The public key is $h = g/f \pmod{q}$ .

Sign message $\mu$ :
1. Hash: compute target $c = H(\mu, r) \in R_q$ for random salt $r$ .
2. Use the trapdoor $(f, g, F, G)$ to sample a short vector $(s_1, s_2) \in \Lambda_h$ such that $s_1 + hs_2 = c \pmod{q}$ . This uses fast Fourier sampling over the NTRU lattice.
3. Signature: $(r, s_2)$ .

Verify: Recompute $c$ , check that $(c - hs_2, s_2)$ is short.

Falcon vs Dilithium: A Comparison

Falcon-512

Based on NTRU. Hash-and-sign paradigm.

Public key: 897 bytes
Signature: 666 bytes
Security: ~128 bits

Advantage: very compact signatures. Disadvantage: requires Gaussian sampling over real numbers — harder to implement securely in constant time. Variable-length signatures complicate some protocols.

ML-DSA-44 (Dilithium)

Based on Module-LWE/SIS. Fiat-Shamir with aborts.

Public key: 1,312 bytes
Signature: 2,420 bytes
Security: ~128 bits

Advantage: simpler implementation, constant-time naturally, better-understood security. Disadvantage: larger signatures than Falcon.

Check Your Understanding

Q1. NTRU decryption computes a = f·e mod q and then lifts it to ordinary integers. Why does that lift work?
Q2. What makes the NTRU private key special from the lattice point of view?
Q3. What happens if NTRU is used with a very large modulus q relative to n (“overstretched” NTRU)?
Q4. How does NTRU’s security foundation differ from LWE’s?

References and Further Reading

Key resources on NTRU

Micciancio & Regev, “Lattice-based Cryptography” — §5 covers NTRU and related constructions. PDF ↗

Silverman, “An Introduction to Lattices, Lattice Reduction, and Lattice-Based Cryptography” (PCMI notes) — accessible treatment of NTRU and its security. IAS PDF ↗

← Previous2.5Lattice Signatures Next →2.7Post-Quantum SecurityWhat "quantum-safe" actually means — and what it doesn't.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.