NTRU

Introduction

NTRU (from “Number Theorists aRe Us,” or per other accounts “N-th degree TRUncated polynomial ring”) was proposed by Hoffstein, Pipher, and Silverman in 1996 — nearly two decades before “post-quantum cryptography” became an urgent research priority, and roughly a decade before Learning With Errors (the problem underlying Kyber, FrodoKEM, and SABER) was even formalized. It rests on a different, closely related hard problem: finding short vectors in a special class of lattices derived from truncated polynomial rings. NTRU is fast, has been studied for nearly 30 years, and directly inspired the NIST-standardized signature scheme Falcon — making it one of the most influential ideas in the entire post-quantum toolkit.

Table of Contents

• The Convolution Ring
• Key Generation
• Encryption and Decryption
• A Worked Example
• Why Decryption Recovers the Message
• NTRU vs. Ring-LWE Schemes
• FAQ
• References

The Convolution Ring

NTRU works in the ring ℤ[x]/(xᴺ − 1) — polynomials of degree less than N, multiplied with wraparound (xᴺ ≡ 1, so exponents reduce mod N; this operation is literally a cyclic convolution of coefficient vectors). Keys and messages are polynomials with small coefficients — usually ternary: just -1, 0, or 1. The security of NTRU rests on the difficulty of finding a short polynomial (specifically, the private key) given only a public polynomial derived from it — a lattice problem in disguise, since every convolution polynomial ring element corresponds to a specific structured lattice.

Key Generation

1. Choose two small, ternary “private” polynomials f and g — coefficients restricted to {-1, 0, 1}. f must be invertible both modulo a small prime p (traditionally p=3) and modulo a larger power of two q.
2. Compute f_p = f⁻¹ mod p (polynomial inverse in the ring, found via the extended Euclidean algorithm over GF(p)) and f_q = f⁻¹ mod q (found the same way modulo 2, then lifted to modulo q via Hensel lifting — repeatedly doubling precision with the update f_q ← f_q·(2 − f·f_q) mod 2ᵏ).
3. Compute the public key: h = p · f_q · g (mod q).
4. The private key is the pair (f, f_p).

Encryption and Decryption

To encrypt a ternary message polynomial m:

1. Sample a random small “blinding” polynomial r (also ternary).
2. Compute the ciphertext: e = r·h + m (mod q).

To decrypt, the recipient (holding f, f_p):

1. Compute a = f·e (mod q), then re-center the coefficients into the range (−q/2, q/2] rather than [0, q).
2. Reduce a modulo p: b = a mod p.
3. Recover the message: m = f_p · b (mod p), re-centered.

Interactive Visualizer

Real NTRU uses N in the hundreds (401 or higher for current security recommendations) with correspondingly larger q — parameters chosen so that finding a short vector in the resulting lattice is computationally infeasible. The visualizer above runs the exact same convolution ring arithmetic, invertibility search, and Hensel-lifted inversion — at N=7, p=3, q=32 — small enough to read every polynomial coefficient by eye, while every operation (extended Euclid over GF(2)/GF(3), Hensel lifting, cyclic convolution) is the genuine algorithm.

A Worked Example

Using the visualizer’s toy parameters:

1. A ternary polynomial f is tested for invertibility mod 3 and mod 32; once found, g is sampled and the public key h = 3·f_q·g mod 32 is published.
2. A random ternary message m and blinding polynomial r are sampled; the ciphertext is e = r·h + m mod 32.
3. The recipient computes a = f·e mod 32, centered — this equals 3·r·g + f·m as an exact integer polynomial (not just mod 32), because the coefficients stay small enough to never wrap around.
4. Reducing a mod 3 kills the 3·r·g term entirely, leaving f·m mod 3; multiplying by f_p inverts f and recovers m exactly.

Why Decryption Recovers the Message

Expand a = f·e = f·(r·h + m) = f·r·h + f·m. Since h = p·f_q·g and f·f_q ≡ 1 (mod q), the first term becomes f·r·p·f_q·g ≡ p·r·g (mod q). So a ≡ p·r·g + f·m (mod q) — and as long as every coefficient of the true integer sum p·r·g + f·m stays within (−q/2, q/2] (which is exactly why f, g, r, m are all restricted to small ternary coefficients), reducing mod q and re-centering recovers that exact integer sum, not just its residue. From there, reducing mod p makes the p·r·g term vanish completely (it’s a multiple of p by construction), leaving f·m mod p, which f_p inverts to recover m. This “reduce mod q to get an exact sum, then reduce mod p to strip the blinding term” two-step is the signature move of every NTRU-family scheme.

NTRU vs. Ring-LWE Schemes

NTRU’s core idea — a fast decryption trapdoor hidden inside convolution polynomial multiplication — directly inspired Falcon’s lattice structure, so while NTRU itself wasn’t chosen as a standalone NIST standard, its mathematical DNA is present in one of the four algorithms that was.

FAQ

Why does key generation sometimes fail to find an invertible f?

Not every random ternary polynomial is invertible modulo both p and q — the extended Euclidean algorithm only succeeds when gcd(f(x), xᴺ−1) is a unit in the respective ring. Real NTRU implementations simply resample f until an invertible one is found, exactly like the visualizer’s retry loop.

What is Hensel lifting, and why is it needed here?

It’s a technique for finding an inverse modulo a large power of two by starting from the (easy) inverse modulo 2 and iteratively “lifting” it to modulo 4, then 16, then 256, doubling precision each step via the Newton-like update f_q ← f_q(2 − f·f_q). Computing the mod-q inverse directly would be far more expensive; lifting from mod 2 is efficient and exact.

Is NTRU still considered secure?

Yes — despite nearly 30 years of cryptanalysis, no attack breaks NTRU at recommended parameters faster than solving the underlying lattice shortest-vector problem, which is why it remains actively used (e.g., in some VPN and messaging implementations) and why its structure was carried forward into Falcon.

How does this differ from the toy Hamming-code trick used for McEliece?

They’re unrelated problems from different mathematical families — McEliece hides an error-correcting code’s fast decoder; NTRU hides a short lattice vector’s implicit blinding cancellation. Both use the same overall visualizer philosophy (genuine structure at a size too small to be secure), but the actual math — GF(2) linear algebra for McEliece versus polynomial ring convolution and Hensel lifting for NTRU — is completely different.

References

1. Hoffstein, J., Pipher, J., Silverman, J.H. “NTRU: A Ring-Based Public Key Cryptosystem.” ANTS III, 1998.

2. NTRU Team. “NTRU: A Lattice Based Cryptosystem.” Available at: https://ntru.org/

3. NIST. “Post-Quantum Cryptography Standardization.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

4. Silverman, J.H. “Almost Inverses and Fast NTRU Key Creation.” NTRU Cryptosystems Technical Report, 1999.