2.6 NTRU
The oldest lattice cryptosystem — polynomial rings, small coefficients, and the Falcon signature standard.
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's approach is different from LWE in a crucial 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.
Beginner's Intuition 💡
Think of NTRU as a complex mathematical recipe where two secret spices (the private key) are blended together to create a unique flavor profile (the public key).
Anyone can "taste" the final flavor and use it to encrypt a message, but once blended, it's mathematically impossible for an attacker to separate the flavor back into the two original secret spices without knowing exactly what they were. This makes NTRU one of the oldest, most compact, and most reliable lattice cryptography systems.
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)$ (NTRU Prime / Falcon, with $n$ prime or power of 2). 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.
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 : u \equiv hv \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 private key gives the short vector $(f, g) \in \Lambda_h$ with $\|(f, g)\| \approx \sqrt{n}$, 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$), the required block size is $\beta \approx 363$, with estimated cost $\approx 2^{106}$ classically — above the 128-bit security target when accounting for hidden constants and implementation overhead.
The NTRU fatigue point: As the ratio $q/n$ increases, the NTRU lattice becomes easier to attack via subfield attacks. The fatigue pointis the threshold $q \approx n^{2.484}$ beyond which the "overstretched NTRU" attack (Albrecht, Bai, Ducas 2016) applies. Below the fatigue point, no polynomial-time algorithm is known. Falcon's parameters are chosen well below this threshold: $q = 12289 \approx n^{1.9}$ for $n = 512$. 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 most powerful 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" attack (Albrecht et al. 2016) showed that NTRU with large modulus $q > n^{2.484}$ 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.9}$ — 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 samplingover 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.