# 23.4 NTRU

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{,}\text{}k$ with $j+k\equiv i\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}N)$.

For example, let $N=3$, let $f={X}^{2}+7X+9$, and let $g=3{X}^{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{,}\text{}p\text{,}\text{}q$ with the requirements that $gcd(p\text{,}\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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{,}\text{}0\text{,}\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{,}\text{}p\text{,}\text{}q)=(107\text{,}\text{}3\text{,}\text{}64)$, the recommended choices for $f\text{,}\text{}g\text{,}\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{,}\text{}p\text{,}\text{}q)=(503\text{,}\text{}3\text{,}\text{}256)$, the recommended choices for $f\text{,}\text{}g\text{,}\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.

# Example

Let $(N\text{,}\text{}p\text{,}\text{}q)=(5\text{,}\text{}3\text{,}\text{}16)$ (this choice of $N$ is much too small for any security; we use it only in order to give an explicit example). Take $f={X}^{4}+X-1$ and $g={X}^{3}-X$. Since

we have

Also,

Bob’s public key is

His private key is

Alice takes her message to be $m={X}^{2}-X+1$. She chooses $\varphi =X-1$. Then the ciphertext is

Bob decrypts by first computing

then

Therefore, Bob has obtained the message.

# 23.4.1 An Attack on NTRU

Let $h={h}_{N-1}{X}^{N-1}+\cdots +{h}_{0}$. Form the $N\times N$ matrix

If we represent $f={f}_{N-1}{X}^{N-1}+\cdots +{f}_{0}$ and $g={g}_{N-1}{X}^{N-1}+\cdots +{g}_{0}$ by the row vectors

then we see that $\stackrel{\u203e}{f}H\equiv \stackrel{\u203e}{g}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}q)$.

Let $I$ be the $N\times N$ identity matrix. Form the $2N\times 2N$ matrix

Let $L$ be the lattice generated by the rows of $M$. Since $g\equiv f\ast h\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}q)$, we can write $g=f\ast h+qy$ for some polynomial $y$. Represent $y$ as an $N$-dimensional row vector $\stackrel{\u203e}{y}$, so $(\stackrel{\u203e}{f}\text{,}\text{}\phantom{\rule{thinmathspace}{0ex}}\stackrel{\u203e}{y})$ is a $2N$-dimensional row vector. Then

so $\left(\overline{f}\text{,}\text{}\overline{g}\right)$ is in the lattice $L$ (see Exercise 3). Since $f$ and $g$ have small coefficients, $\left(\overline{f}\text{,}\text{}\overline{g}\right)$ is a small vector in the lattice $L$. Therefore, the secret information for the key can be represented as a short vector in a lattice. An attacker can try to apply a lattice reduction algorithm to find short vectors, and possibly obtain $\left(\overline{f}\text{,}\text{}\overline{g}\right)$. Once the attacker has found $f$ and $g$, the system is broken.

To stop lattice attacks, we need to make the lattice have high enough dimension that lattice reduction algorithms are inefficient. This is easily achieved by making $N$ sufficiently large. However, if $N$ is too large, the encryption and decryption algorithms become slow. The suggested values of $N$ were chosen to achieve security while keeping the cryptographic algorithms efficient.

Lattice reduction methods have the best success when the shortest vector is small (more precisely, small when compared to the $2N$th root of the determinant of the $2N$-dimensional lattice). Improvements in the above lattice attack can be obtained by replacing $I$ in the upper left block of $M$ by $\alpha I$ for a suitably chosen real number $\alpha $. This makes the resulting short vector $\left(\alpha \overline{f}\text{,}\text{}\overline{g}\right)$ comparatively shorter and thus easier to find. The parameters in NTRU, especially the sizes of $f$ and $g$, have been chosen so as to limit the effect of these lattice attacks.

So far, the NTRU cryptosystem appears to be strong; however, as with many new cryptosystems, the security is still being studied. If no successful attacks are found, NTRU will have the advantage of providing security comparable to RSA and other public key methods, but with smaller key size and with faster encryption and decryption times.