Everything NTRU does happens in one algebraic structure: polynomials whose
exponents wrap around at N and whose coefficients wrap around at a modulus.
This page builds that structure from the ground up. If you are comfortable
with quotient rings, skip to The NTRU algorithm.
A ring is a set with addition and multiplication that behave the way you expect from the integers: addition is commutative and has a zero and negatives, multiplication is associative and distributes over addition. All rings here are commutative and have a 1.
Examples:
An element $a$ is a unit (is invertible) if some $b$ satisfies $ab = 1$. In $\mathbb{Z}$ only $\pm 1$ are units. In $\mathbb{Z}_n$ the units are exactly the numbers coprime to $n$; when $n$ is prime every non-zero element is a unit, and $\mathbb{Z}_p$ is a field.
An ideal $I$ of a ring $R$ is a subset that
The third rule is what distinguishes an ideal from a mere subring: multiplying by anything in the ring keeps you inside.
The ideal generated by an element $a$ is the set of all its multiples,
\[\langle a \rangle = \lbrace ra : r \in R \rbrace.\]The even integers are $\langle 2 \rangle \subset \mathbb{Z}$. The ideal NTRU cares about is $\langle x^N - 1 \rangle \subset \mathbb{Z}[x]$: every polynomial that is a multiple of $x^N - 1$.
Given an ideal $I$, call two elements congruent when their difference lies in $I$. The set of everything congruent to $a$ is its coset
\[a + I = \lbrace a + i : i \in I \rbrace.\]The quotient ring $R/I$ is the set of all cosets, added and multiplied through any representatives. The absorption rule is exactly what makes the result independent of which representatives you pick.
The familiar case is $\mathbb{Z}/\langle n \rangle = \mathbb{Z}_n$: “work with integers, but treat multiples of $n$ as zero”.
Quotienting by $\langle x^N - 1 \rangle$ means “work with polynomials, but treat $x^N - 1$ as zero”, in other words
\[x^N = 1.\]Every polynomial then has a unique representative of degree below $N$, obtained by replacing $x^{N+k}$ with $x^k$. That is why these are called truncated polynomials.
Fix a prime $N$ and write
\[R = \mathbb{Z}[x]/\langle x^N - 1\rangle,\qquad R_q = \mathbb{Z}_q[x]/\langle x^N - 1\rangle,\qquad R_p = \mathbb{Z}_p[x]/\langle x^N - 1\rangle.\]An element is a list of $N$ coefficients,
\[a = a_0 + a_1 x + \dots + a_{N-1}x^{N-1} \leftrightarrow (a_0, a_1, \dots, a_{N-1}).\]Phoenix stores polynomials exactly like this: a NumPy array where a[i] is
the coefficient of $x^i$.
Addition is coefficient-wise.
Multiplication is ordinary polynomial multiplication followed by the wrap-around $x^N = 1$. The coefficient of $x^k$ in a product collects every pair of indices that sums to $k$ modulo $N$:
\[(a \star b)_k = \sum_{i + j \equiv k \pmod N} a_i b_j.\]This is a cyclic convolution, written $\star$ throughout these docs.
In $\mathbb{Z}_3[x]/\langle x^5 - 1\rangle$, multiply $a = x^4 + 2x^3 + 3$ by $b = x^4 + 3x^2 + x + 2$.
Ordinary multiplication gives
\[x^8 + 2x^7 + 3x^6 + 7x^5 + 7x^4 + 4x^3 + 9x^2 + 3x + 6.\]Wrap with $x^5 = 1$, so $x^8 \to x^3$, $2x^7 \to 2x^2$, $3x^6 \to 3x$ and $7x^5 \to 7$:
\[7x^4 + 5x^3 + 11x^2 + 6x + 13.\]Reduce coefficients modulo 3:
\[a \star b = x^4 + 2x^3 + 2x^2 + 1.\]>>> import numpy as np
>>> from phoenix import poly
>>> a = np.array([3, 0, 0, 2, 1]) # constant term first
>>> b = np.array([2, 1, 3, 0, 1])
>>> poly.convolve(a, b).tolist()
[13, 6, 11, 5, 7]
>>> poly.format_poly(poly.convolve(a, b, 3))
'x^4 + 2x^3 + 2x^2 + 1'
$\mathbb{Z}_q$ is usually pictured as $\lbrace 0, \dots, q-1 \rbrace$, but NTRU needs to tell small numbers from large ones, and for that the natural picture is the interval centered on zero:
\[\left(-\tfrac{q}{2}, \tfrac{q}{2}\right].\]Modulo 41, the residue 40 is really $-1$: small. Converting to this range is called a center lift. Decryption depends on it, as the algorithm page shows.
>>> poly.center(np.array([0, 1, 20, 21, 40]), 41).tolist()
[0, 1, 20, -20, -1]
Key generation needs the inverse of a polynomial $f$ in $R_p$ and in $R_q$.
For integers, the Euclidean algorithm computes $\gcd(a, b)$, and running it backwards yields $s, t$ with
\[s a + t b = \gcd(a, b).\]The same holds for polynomials over a field, because polynomial long division works there: you can always divide by the leading coefficient.
Apply it to $f$ and $x^N - 1$ over $\mathbb{Z}_p$ with $p$ prime. If their gcd is 1,
\[s(x) f(x) + t(x) (x^N - 1) = 1.\]In the quotient ring $x^N - 1$ is zero, so this reads $s \star f = 1$: $s$ is the inverse of $f$. If the gcd is not 1, $f$ shares a factor with $x^N - 1$ and has no inverse.
Invert $f = x + 1$ in $\mathbb{Z}_3[x]/\langle x^3 - 1\rangle$. One division step suffices:
\[x^3 - 1 = (x + 1)(x^2 - x + 1) - 2.\]Rearranged, $(x+1)(x^2 - x + 1) = (x^3 - 1) + 2 \equiv 2$. Multiply both sides by $2^{-1} = 2 \pmod 3$:
\[f^{-1} = 2(x^2 - x + 1) = 2x^2 + x + 2 \pmod 3.\]>>> f = np.array([1, 1, 0])
>>> poly.format_poly(poly.invert(f, 3))
'2x^2 + x + 2'
>>> poly.convolve(f, poly.invert(f, 3), 3).tolist()
[1, 0, 0]
Since $x^N - 1 = (x - 1)(x^{N-1} + \dots + x + 1)$, anything divisible by $x - 1$ is not invertible. A polynomial is divisible by $x - 1$ exactly when it vanishes at $x = 1$, that is, when its coefficients sum to zero.
This is why NTRU draws $f$ with one more $+1$ than $-1$: then $f(1) = 1$. A polynomial with equally many would never be invertible. Passing this test is necessary but not sufficient, so key generation simply tries again when inversion fails.
Phoenix uses $q = 2048 = 2^{11}$ or $4096 = 2^{12}$, and $\mathbb{Z}_{2048}$ is not a field, so Euclid does not apply directly. Instead:
Each round doubles the exponent of the modulus. If $f \star b = 1 - c$ with $c \equiv 0 \pmod{2^k}$, then
\[f \star b \star (2 - f \star b) = (1 - c)(1 + c) = 1 - c^2,\]and $c^2 \equiv 0 \pmod{2^{2k}}$. Starting from $2^1$, four rounds reach $2^{16}$, more than enough for $2^{12}$.
poly.invert implements both steps and works for any prime-power modulus.
NTRU’s secrets are ternary: every coefficient is $-1$, $0$ or $1$. $T(a, b)$ denotes the ternary polynomials with exactly $a$ coefficients equal to $+1$ and $b$ equal to $-1$.
The product of two small polynomials is still fairly small: a coefficient of $u \star v$ is a sum of at most $\min(\text{weight}(u), \text{weight}(v))$ terms, each $\pm 1$. By contrast, multiplying by the inverse of a small polynomial yields something that looks uniformly random modulo $q$. NTRU lives in the gap between those two facts.
The public key $h$ satisfies $f \star h \equiv p g \pmod q$ with $f$ and $g$ small. The set of all pairs $(u, v)$ with $u \star h \equiv v \pmod q$ is closed under addition and under integer scaling: it is a lattice in $2N$-dimensional space. Almost all of its points are long vectors, but $(f, p g)$ is an unusually short one.
Recovering the private key therefore means finding a very short vector in a lattice of dimension about a thousand. That is the shortest vector problem, and no known algorithm, classical or quantum, solves it efficiently at these sizes. That is the entire security argument, and also why NTRU is called lattice-based even though no lattice appears in the implementation.
Next: The NTRU algorithm.