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 in 1996 — two years before Ajtai's worst-case hardness result and nine years before Regev's LWE. It is the oldest lattice-based public key system and the only one that has survived 28 years of public cryptanalysis. Today it is the basis of FIPS 206 (Falcon / FN-DSA), one of NIST's four post-quantum standards.
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.
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.
Key Generation
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.
Construction 9 — NTRU Key Generation
1. Sample small polynomials $f, g \in R$ with coefficients in $\{-1, 0, 1\}$ and roughly $n/3$ nonzero coefficients each.
2. Require that $f$ is invertible modulo both $q$ and $p$ (small primes like $p = 3, q = 2048$). If not, resample.
3. Compute $F_q = f^{-1} \pmod{q}$ (polynomial inverse in $R_q$).
4. The public key is $h = p \cdot F_q \cdot g \pmod{q}$.
The private key is $(f, F_p)$ where $F_p = f^{-1} \pmod{p}$.
Encryption and Decryption
Construction 10 — NTRU Encryption
Encrypt message $m \in R_p$:
1. Sample a small random polynomial $r \in R$ (the "blinding factor").
2. Ciphertext: $e = r \cdot h + m \pmod{q}$.
Decrypt:
1. Compute $a = f \cdot e \pmod{q}$:
$a = f \cdot (r \cdot h + m) = f \cdot r \cdot p F_q g + f \cdot m = p \cdot r \cdot g + f \cdot m \pmod{q}$
2. Since $f, g, r, m$ are all small, $p \cdot rg + fm$ has small coefficients — lift from $R_q$ to integers without wraparound.
3. Reduce modulo $p$: $a \pmod{p} = fm \pmod{p}$ (since $p \cdot rg \equiv 0$). Multiply by $F_p$ to recover $F_p \cdot fm = m$.
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.
Hardness and 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.
Lattice attacks
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
The "overstretched NTRU" attack (Albrecht et al. 2016) showed that NTRU with large modulus $q$ (relative to $n$) can be broken using subfield lattice attacks. This ruled out some FHE constructions based on NTRU. Falcon avoids this by using small, carefully chosen $q$ relative to $n$.
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.