6.9.

Convolution polynomial rings 387

v = 86w1 − 35w2 − 32w3 .

Now suppose that Eve tries to decrypt Bob’s message, but she knows only
the public basis w1 , w2 , w3 . If she applies Babai’s algorithm using the public
basis, she finds that

e ≈ 75.76w1 − 34.52w2 − 24.18w3 .

Rounding, she obtains a lattice vector

v = 75w1 − 35w2 − 24w3 = (−79508353, −35809745, 11095049)

that is somewhat close to e. However, this lattice vector gives the incorrect
plaintext (76, −35, −24), not the correct plaintext m = (86, −35, −32). It is
instructive to compare how well Babai’s algorithm did for the different bases.
We find that

e − v ≈ 5.3852 and e − v  ≈ 472000.

Of course, the GGH cryptosystem is not secure in dimension 3, since even

if we use numbers that are large enough to make an exhaustive search im-
practical, there are efficient algorithms to find good bases in low dimension.
In dimension 2, an algorithm for finding a good basis dates back to Gauss. A
powerful generalization to arbitrary dimension, known as the LLL algorithm,
is covered in Section 6.12.
Remark 6.37. We observe that GGH is an example of a probabilistic cryp-
tosystem (see Section 3.10), since a single plaintext leads to many different
ciphertexts due to the choice of the random perturbation r. This leads to
a potential danger if Bob sends the same message twice using different ran-
dom perturbations, or sends different messages using the same random per-
turbation. See Exercise 6.20. Thus in practice the random perturbation r is
determined by applying a hash function to the plaintext m.
Remark 6.38. An alternative version of GGH reverses the roles of m and r,
so the ciphertext has the form e = rW + m. Alice finds rW by computing the
lattice vector closest to e, and then she recovers the plaintext as m = e − rW .

6.9 Convolution polynomial rings

In this section we describe the special sort of polynomial quotient rings that
are used by the NTRU public key cryptosystem, which is the topic of Sec-
tions 6.10 and 6.11. The reader who is unfamiliar with basic ring theory should
read Section 2.10 before continuing.

Definition. Fix a positive integer N . The ring of convolution polynomials

(of rank N ) is the quotient ring
388 6. Lattices and Cryptography

Z[x]
R= .
(xN − 1)

Similarly, the ring of convolution polynomials (modulo q) is the quotient ring

(Z/qZ)[x]
Rq = .
(xN − 1)
Proposition 2.51 tells us that every element of R or Rq has a unique
representative of the form

a0 + a1 x + a2 x2 + · · · + aN −1 xN −1

with the coefficients in Z or Z/qZ, respectively. We observe that it is easier to

do computations in the rings R and Rq than it is in more general polynomial
quotient rings, because the polynomial xN − 1 has such a simple form. The
point is that when we mod out by xN − 1, we are simply requiring xN to
equal 1. So any time xN appears, we replace it by 1. For example, if we have
a term xk , then we write k = iN + j with 0 ≤ j < N and set

xk = xiN +j = (xN )i · xj = 1i · xj = xj .

In brief, the exponents on the powers of x may be reduced modulo N .

It is often convenient to identify a polynomial

a(x) = a0 + a1 x + a2 x2 + · · · + aN −1 xN −1 ∈ R

with its vector of coefficients

(a0 , a1 , a2 , . . . , aN −1 ) ∈ ZN ,

and similarly with polynomials in Rq . Addition of polynomials corresponds to

the usual addition of vectors,

a(x) + b(x) ←→ (a0 + b0 , a1 + b1 , a2 + b2 , . . . , aN −1 + bN −1 ).

The rule for multiplication in R is a bit more complicated. We write  for

multiplication in R and Rq , to distinguish it from standard multiplication of
polynomials.
Proposition 6.39. The product of two polynomials a(x), b(x) ∈ R is given
by the formula

a(x)  b(x) = c(x) with ck = ai bk−i , (6.27)
i+j≡k (mod N )

where the sum defining ck is over all i and j between 0 and N −1 satisfying the
condition i + j ≡ k (mod N ). The product of two polynomials a(x), b(x) ∈ Rq
is given by the same formula, except that the value of ck is reduced modulo q.
6.9. Convolution polynomial rings 389

Proof. We first compute the usual polynomial product of a(x) and b(x), after
which we use the relation xN = 1 to combine the terms. Thus
N −1  ⎛N −1 ⎞
 
a(x)  b(x) = ai xi  ⎝ bj xj ⎠
i=0 j=0
⎛ ⎞

2N −2 
= ⎝ ai bj ⎠ xk
k=0 i+j=k
⎛ ⎞ ⎛ ⎞
N
 −1  
2N −2 
= ⎝ ai bj ⎠ xk + ⎝ ai bj ⎠ xk−N
k=0 i+j=k k=N i+j=k
⎛ ⎞ ⎛ ⎞
N
 −1  N
 −2 
= ⎝ ai bj ⎠ xk + ⎝ ai bj ⎠ xk
k=0 i+j=k k=0 i+j=k+N
N
 −1 
= ai bj xk .
k=0 i+j≡k (mod N )

Example 6.40. We illustrate multiplication in the convolution rings R and Rq

with an example. We take N = 5 and let a(x), b(x) ∈ R be the polynomials

a(x) = 1 − 2x + 4x3 − x4 and b(x) = 3 + 4x − 2x2 + 5x3 + 2x4 .

Then

a(x)  b(x) = 3 − 2x − 10x2 + 21x3 + 5x4 − 16x5 + 22x6 + 3x7 − 2x8

= 3 − 2x − 10x2 + 21x3 + 5x4 − 16 + 22x + 3x2 − 2x3
= −13 + 20x − 7x2 + 19x3 + 5x4 in R = Z[x]/(x5 − 1).

If we work instead in the ring R11 , then we reduce the coefficients modulo 11
to obtain

a(x)  b(x) = 9 + 9x + 4x2 + 8x3 + 5x4 in R11 = (Z/11Z)[x]/(x5 − 1).

Remark 6.41. The convolution product of two vectors is given by

(a0 , a1 , a2 , . . . , aN −1 )  (b0 , b1 , b2 , . . . , bN −1 ) = (c0 , c1 , c2 , . . . , cN −1 ),

where the ck are defined by (6.27). We use  interchangeably to denote con-

volution multiplication in the rings R and Rq and the convolution product of
vectors.
There is a natural map from R to Rq in which we simply reduce the
coefficients of a polynomial modulo q. This reduction modulo q map satisfies
390 6. Lattices and Cryptography

a(x) + b(x) mod q = a(x) mod q + b(x) mod q , (6.28)

a(x)  b(x) mod q = a(x) mod q  b(x) mod q . (6.29)

(In mathematical terminology, the map R → Rq is a ring homomorphism.)

It is often convenient to have a consistent way of going in the other direc-
tion. Among the many ways of lifting, we choose the following.

Definition. Let a(x) ∈ Rq . The centered lift of a(x) to R is the unique

polynomial a (x) ∈ R satisfying

a (x) mod q = a(x)

whose coefficients are chosen in the interval

q q
− < ai ≤ .
2 2
For example, if q = 2, then the centered lift of a(x) is a binary polynomial.

Remark 6.42. It is important to observe that the lifting map does not satisfy
the analogs of (6.28) and (6.29). In other words, the sum or product of the
lifts need not be equal to the lift of the sum or product.
Example 6.43. Let N = 5 and q = 7, and consider the polynomial

a(x) = 5 + 3x − 6x2 + 2x3 + 4x4 ∈ R7 .

The coefficients of the centered lift of a(x) are chosen from {−3, −2, . . . , 2, 3},
so
Centered Lift of a(x) = −2 + 3x + x2 + 2x3 − 3x4 ∈ R.
Similarly, the lift of b(x) = 3 + 5x2 − 6x3 + 3x4 is 3 − 2x2 + x3 + 3x4 . Notice
that

(Lift of a)  (Lift of b) = 20x + 10x2 − 11x3 − 14x4

and
(Lift of a  b) = −x + 3x2 + 3x3

are not equal to one another, although they are congruent modulo 7.
Example 6.44. Very few polynomials in R have multiplicative inverses, but
the situation is quite different in Rq . For example, let N = 5 and q = 2. Then
the polynomial 1 + x + x4 has an inverse in R2 , since in R2 we have

(1 + x + x4 )  (1 + x2 + x3 ) = 1 + x + x2 + 2x3 + 2x4 + x6 + x7 = 1.

(Since N = 5, we have x6 = x and x7 = x2 .) When q is a prime, the ex-

tended Euclidean algorithm for polynomials (Proposition 2.47) tells us which
polynomials are units and how to compute their inverses in Rq .
6.9. Convolution polynomial rings 391

Proposition 6.45. Let q be prime. Then a(x) ∈ Rq has a multiplicative

inverse if and only if

gcd a(x), xN − 1 = 1 in (Z/qZ)[x]. (6.30)

If (6.30) is true, then the inverse a(x)−1 ∈ Rq can be computed using the ex-
tended Euclidean algorithm (Proposition 2.47) to find polynomials u(x), v(x) ∈
(Z/qZ)[x] satisfying

a(x)u(x) + (xN − 1)v(x) = 1.

Then a(x)−1 = u(x) in Rq .

Proof. Proposition 2.47 says that we can find polynomials u(x) and v(x) in
the polynomial ring (Z/qZ)[x] satisfying

a(x)u(x) + (xN − 1)v(x) = gcd a(x), xN − 1 .

If the gcd is equal to 1, then reducing modulo xN − 1 yields a(x)  u(x) = 1

in Rq . Conversely, if a(x) is a unit in Rq , then we can find a polynomial u(x)
such that a(x)  u(x) = 1 in Rq . By definition of Rq , this means that

a(x)u(x) ≡ 1 (mod (xN − 1)),

so by definition of congruences, there is a polynomial v(x) satisfying

a(x)u(x) − 1 = (xN − 1)v(x) in (Z/qZ)[x].

Example 6.46. We let N = 5 and q = 2 and give the full details for computing
(1 + x + x4 )−1 in R2 . First we use the Euclidean algorithm to compute the
greatest common divisor of 1 + x + x4 and 1 − x5 in (Z/2Z)[x]. (Note that
since we are working modulo 2, we have 1 − x5 = 1 + x5 .) Thus

x5 + 1 = x · (x4 + x + 1) + (x2 + x + 1),

x4 + x + 1 = (x2 + x)(x2 + x + 1) + 1.

So the gcd is equal to 1, and using the usual substitution method yields

1 = (x4 + x + 1) + (x2 + x)(x2 + x + 1)

= (x4 + x + 1) + (x5 + 1 + x(x4 + x + 1))
= (x4 + x + 1)(x3 + x2 + 1) + (x5 + 1)(x2 + x).

Hence
(1 + x + x4 )−1 = 1 + x2 + x3 in R2 .
(See Exercise 1.12 for an efficient computer algorithm and Figure 1.3 for the
“magic box method” to compute a(x)−1 in Rq .)
392 6. Lattices and Cryptography

Remark 6.47. The ring Rq makes perfect sense regardless of whether q is

prime, and indeed there are situations in which it can be advantageous to
take q composite, for example q = 2k . In general, if q is a power of a prime p,
then in order to compute the inverse of a(x) in Rq , one first computes the
inverse in Rp , then “lifts” this value to an inverse in Rp2 , and then lifts to
an inverse in Rp4 , and so on. (See Exercise 6.26.) Similarly, if q = q1 q2 · · · qr ,
where each qi = pki i is a prime power, one first computes inverses in Rqi and
then combines the inverses using the Chinese remainder theorem.

6.10 The NTRU public key cryptosystem

Cryptosystems based on the difficulty of integer factorization or the discrete
logarithm problem are group-based cryptosystems, because the underlying
hard problem involves only one operation. For RSA, Diffie–Hellman, and El-
Gamal, the group is the group of units modulo m for some modulus m that
may be prime or composite, and the group operation is multiplication mod-
ulo m. For ECC, the group is the set of points on an elliptic curve modulo p
and the group operation is elliptic curve addition.
Rings are algebraic objects that have two operations, addition and mul-
tiplication, which are connected via the distributive law. In this section we
describe the NTRU public key cryptosystem. NTRU is most naturally de-
scribed using convolution polynomial rings, but the underlying hard mathe-
matical problem can also be interpreted as SVP or CVP in a lattice. We discuss
the connection with lattices in Section 6.11.

6.10.1 The NTRU public key cryptosystem

In this section we describe the NTRU (pronounced en-trū) public key cryp-
tosystem. We begin by fixing an integer N ≥ 1 and two moduli p and q, and
we let R, Rp , and Rq be the convolution polynomial rings

Z[x] (Z/pZ)[x] (Z/qZ)[x]

R= , Rp = , Rq = ,
(xN − 1) (xN − 1) (xN − 1)

described in Section 6.9. As usual, we may view a polynomial a(x) ∈ R as an

element of Rp or Rq by reducing its coefficients modulo p or q. In the other
direction, we use centered lifts to move elements from Rp or Rq to R. We make
various assumptions on the parameters N , p and q, in particular we require
that N be prime and that gcd(N, q) = gcd(p, q) = 1. (The reasons for these
assumptions are explained in Exercises 6.30 and 6.33.)
We need one more piece of notation before describing the NTRU cryp-
tosystem.

Definition. For any positive integers d1 and d2 , we let