If the dimension $n$ is large, say $n\ge 100$, the LLL algorithm is not effective in finding short vectors. This allows lattices to be used in cryptographic constructions. Several cryptosystems based on lattices have been proposed. One of the most successful current systems is NTRU (rumored to stand for either “Number Theorists aRe Us” or “Number Theorists aRe Useful”). It is a public key system. In the following, we describe the algorithm for transmitting messages using a public key. There is also a related signature scheme, which we won’t discuss. Although the initial description of NTRU does not involve lattices, we’ll see later that it also has a lattice interpretation.

First, we need some preliminaries. Choose an integer $N$. We will work with the set of polynomials of degree less than $N$. Let

be two such polynomials. Define

where

The summation is over all pairs $j\text{,}k$ with $j+k\equiv i(\text{mod}N)$.

For example, let $N=3$, let $f=X^2+7X+9$, and let $g=3X^2+2X+5$. Then the coefficient $c_1$ of $X$ in $f\ast g$ is

and

From a slightly more advanced viewpoint, $f\ast g$ is simply multiplication of polynomials mod $X^N-1$ (see Exercise 5 and Section 3.11).

NTRU works with certain sets of polynomials with small coefficients, so it is convenient to have a notation for them. Let

We can now describe the NTRU algorithm. Alice wants to send a message to Bob, so Bob needs to set up his public key. He chooses three integers $N\text{,}p\text{,}q$ with the requirements that $gcd(p\text{,}q)=1$ and that $p$ is much smaller than $q$. Recommended choices are

for moderate security and

for very high security. Of course, these parameters will need to be adjusted as attacks improve. Bob then chooses two secret polynomials $f$ and $g$ with small coefficients (we’ll say more about how to choose them later). Moreover, $f$ should be invertible mod $p$ and mod $q$, which means that there exist polynomials $F_p$ and $F_q$ of degree less than $N$ such that

Bob calculates

Bob’s public key is

His private key is $f$. Although $F_p$ can be calculated easily from $f$, he should store (secretly) $F_p$ since he will need it in the decryption process. What about $g$? Since $g\equiv f\ast h(\text{mod}q)$, he is not losing information by not storing it (and he does not need it in decryption).

Alice can now send her message. She represents the message, by some prearranged procedure, as a polynomial $m$ of degree less than $N$ with coefficients of absolute value at most $(p-1)/2$. When $p=3$, this means that $m$ has coefficients $-1\text{,}0\text{,}1$. Alice then chooses a small polynomial $\varphi$ (“small” will be made more precise shortly) and computes

She sends the ciphertext $c$ to Bob.

Bob decrypts by first computing

with all coefficients of the polynomial $a$ of absolute value at most $q/2$, then (usually) recovering the message as

Why should this work? In fact, sometimes it doesn’t, but experiments with the parameter choices given below indicate that the probability of decryption errors is less than $5\times {10}^{-5}$. But here is why the decryption is usually correct. We have

Since $\varphi$, $g$, $f$, $m$ have small coefficients and $p$ is much smaller than $q$, it is very probable that $p\varphi \ast g+f\ast m$, before reducing mod $q$, has coefficients of absolute value less than $q/2$. In this case, we have equality

Then

so the decryption works.

For $(N\text{,}p\text{,}q)=(107\text{,}3\text{,}64)$, the recommended choices for $f\text{,}g\text{,}\varphi$ are

(recall that this means that the coefficients of $f$ are fifteen 1s, fourteen $-1$s, and the remaining 78 coefficients are 0).

For $(N\text{,}p\text{,}q)=(503\text{,}3\text{,}256)$, the recommended choices for $f\text{,}g\text{,}\varphi$ are

With these choices of parameters, the polynomials $f$, $g$, $\varphi$ are small enough that the decryption works with very high probability.

The reason $f$ has a different number of 1s and $-1$s is so that $f(1)\ne 0$. It can be shown that if $f(1)=0$, then $f$ cannot be invertible.