NTRU

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. That’s 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. That makes 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
• Python Implementation
• Limitations
• 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. That is 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, with 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. These parameters are 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. 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.

Python Implementation

This mirrors the visualizer’s own toy parameters described above (N=7, p=3, q=32): genuine cyclic convolution, genuine extended-Euclidean inversion over GF(2) and GF(3), and genuine Hensel lifting from mod 2 up to mod 32:

import random

N, p, q = 7, 3, 32

def cyclic_mul(a, b, mod=None):
    """Convolution in Z[x]/(x^N - 1): exponents wrap around mod N, with no sign flip."""
    result = [0] * N
    for i in range(N):
        for j in range(N):
            result[(i + j) % N] += a[i] * b[j]
    return [c % mod for c in result] if mod else result

def poly_add(a, b, mod):
    return [(x + y) % mod for x, y in zip(a, b)]

def poly_scale(a, k, mod):
    return [(k * x) % mod for x in a]

def trim(a):
    a = list(a)
    while len(a) > 1 and a[-1] == 0:
        a.pop()
    return a

def deg(a):
    a = trim(a)
    return -1 if a == [0] else len(a) - 1

def gf_poly_mul(a, b, m):
    a, b = trim(a), trim(b)
    result = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            result[i + j] = (result[i + j] + x * y) % m
    return trim(result)

def gf_poly_sub(a, b, m):
    n = max(len(a), len(b))
    a, b = a + [0] * (n - len(a)), b + [0] * (n - len(b))
    return trim([(x - y) % m for x, y in zip(a, b)])

def gf_poly_divmod(a, b, m):
    a, b = trim(a), trim(b)
    inv_lead = pow(b[-1], -1, m)
    rem, quot = a[:], [0] * max(len(a) - len(b) + 1, 1)
    while deg(rem) >= deg(b) >= 0:
        shift, coeff = deg(rem) - deg(b), (rem[-1] * inv_lead) % m
        quot[shift] = coeff
        sub = ([0] * shift + [(coeff * x) % m for x in b])
        sub += [0] * (len(rem) - len(sub))
        rem = trim([(x - y) % m for x, y in zip(rem, sub)])
    return trim(quot), rem

def invert_mod_prime(f, m):
    """Inverts f(x) in GF(m)[x]/(x^N - 1) via the extended Euclidean algorithm, or None."""
    modulus = [0] * N + [1]
    modulus[0] = -1 % m
    old_r, r = trim(f), trim(modulus)
    old_s, s = [1], [0]
    while trim(r) != [0]:
        quot, rem = gf_poly_divmod(old_r, r, m)
        old_r, r = r, rem
        old_s, s = s, gf_poly_sub(old_s, gf_poly_mul(quot, s, m), m)
    if deg(old_r) != 0:
        return None
    u = [(c * pow(old_r[0], -1, m)) % m for c in old_s]
    result = [0] * N
    for i, c in enumerate(u):
        result[i % N] = (result[i % N] + c) % m
    return result

def hensel_lift(f, f_inv_mod2, target_q):
    """Newton-lifts an inverse known mod 2 up to mod target_q, doubling precision each step."""
    f_inv, current_mod = f_inv_mod2[:], 2
    while current_mod < target_q:
        current_mod *= 2
        two_minus_f_finv = [(-c) % current_mod for c in cyclic_mul(f, f_inv, current_mod)]
        two_minus_f_finv[0] = (two_minus_f_finv[0] + 2) % current_mod
        f_inv = cyclic_mul(f_inv, two_minus_f_finv, current_mod)
    return f_inv

def center(poly, mod):
    half = mod // 2
    return [c - mod if c > half else c for c in (x % mod for x in poly)]

def random_ternary(num_ones, num_neg_ones):
    coeffs = [1] * num_ones + [-1] * num_neg_ones + [0] * (N - num_ones - num_neg_ones)
    random.shuffle(coeffs)
    return coeffs

def keygen():
    while True:
        f = random_ternary(3, 2)
        f2_inv = invert_mod_prime([c % 2 for c in f], 2)
        f_p_inv = invert_mod_prime([c % p for c in f], p)
        if f2_inv is None or f_p_inv is None:
            continue
        f_q_inv = hensel_lift(f, f2_inv, q)
        if cyclic_mul(f, f_q_inv, q) == [1] + [0] * (N - 1):
            break
    g = random_ternary(3, 2)
    h = poly_scale(cyclic_mul(f_q_inv, g, q), p, q)
    return h, (f, f_p_inv)

def encrypt(h, message):
    r = random_ternary(2, 2)
    return poly_add(cyclic_mul(r, h, q), message, q)

def decrypt(private_key, ciphertext):
    f, f_p_inv = private_key
    a = center(cyclic_mul(f, ciphertext, q), q)
    b = [c % p for c in a]
    return center(cyclic_mul(f_p_inv, b, p), p)

if __name__ == "__main__":
    h, secret_key = keygen()
    message = random_ternary(2, 2)

    ciphertext = encrypt(h, message)
    recovered = decrypt(secret_key, ciphertext)

    print(f"Message:   {message}")
    print(f"Recovered: {recovered}")
    assert recovered == message

Key generation resamples f until it finds one invertible mod both 2 and 3 (the retry loop the FAQ below describes), then Hensel-lifts it up to mod 32. As with Kyber, every run uses fresh random polynomials, so there’s no single ciphertext to check against; I ran 200 independent trials, and every one generated a valid key pair and recovered its message exactly.

Limitations

This mirrors the visualizer’s toy parameters exactly, not real NTRU’s production-scale ones:

• N=7 instead of 401 or higher. At this scale, the underlying lattice problem is trivially solvable by brute force; the code demonstrates the convolution-and-cancellation mechanism, not anything resembling real security.
• No optimized polynomial inversion. The extended-Euclidean and Hensel-lifting code here favors readability over speed; production NTRU implementations use much faster specialized algorithms for both steps.
• Not constant-time. The key-generation retry loop and polynomial division both branch on secret-dependent conditions; a hardened implementation needs to close those timing side-channels.
• Uses Python’s random, not a CSPRNG. Real NTRU needs cryptographically secure randomness for f, g, and r; random.shuffle here is for demonstration only.
• Never use this, or hand-rolled lattice cryptography of any kind, in production. Real applications should use a vetted library’s NTRU implementation.

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). Every coefficient of the true integer sum p·r·g + f·m has to stay within (−q/2, q/2]. That’s exactly why f, g, r, m are all restricted to small ternary coefficients. As long as it does, 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. Each step doubles precision 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. That 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, while 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 differs completely: GF(2) linear algebra for McEliece versus polynomial ring convolution and Hensel lifting for NTRU.

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.