23.4 NTRU – Introduction to Cryptography with Coding Theory, 3rd Edition

23.4 NTRU

If the dimension n is large, say n100, 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

f=aN1XN1++a0 and g=bN1XN1++b0

be two such polynomials. Define

h=fg=cN1XN1++c0, 

where

ci=j+kiajbk.

The summation is over all pairs j, k with j+ki(modN).

For example, let N=3, let f=X2+7X+9, and let g=3X2+2X+5. Then the coefficient c1 of X in fg is

a0b1+a1b0+a2b2=92+75+13=56, 

and

fg=46X2+56X+68.

From a slightly more advanced viewpoint, fg is simply multiplication of polynomials mod XN1 (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

L(j, k)=the set of polynomials of degree <Nwith j coefficients equal to +1and k coefficients equal to 1.The remaining coefficients are 0.

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, p, q with the requirements that gcd(p, q)=1 and that p is much smaller than q. Recommended choices are

(N, p, q)=(107, 3, 64)

for moderate security and

(N, p, q)=(503, 3, 256)

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 Fp and Fq of degree less than N such that

Fpf1(modp), Fqf1(modq).

Bob calculates

hFqg(modq).

Bob’s public key is

(N, p, q, h).

His private key is f. Although Fp can be calculated easily from f, he should store (secretly) Fp since he will need it in the decryption process. What about g? Since gfh(modq), 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 (p1)/2. When p=3, this means that m has coefficients 1, 0, 1. Alice then chooses a small polynomial ϕ (“small” will be made more precise shortly) and computes

cpϕh+m(modq).

She sends the ciphertext c to Bob.

Bob decrypts by first computing

afc(modq)

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

mFpa(modp).

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×105. But here is why the decryption is usually correct. We have

afcf(pϕh+m)fpϕFqg+fmpϕg+fm(modq).

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

a=pϕg+fm.

Then

Fpa=pFpϕg+Fpfm0+1mm(modp), 

so the decryption works.

For (N, p, q)=(107, 3, 64), the recommended choices for f, g, ϕ are

fL(15, 14), gL(12, 12), ϕL(5, 5)

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

For (N, p, q)=(503, 3, 256), the recommended choices for f, g, ϕ are

fL(216, 215), gL(72, 72), ϕL(55, 55).

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

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

Example

Let (N, p, q)=(5, 3, 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=X4+X1 and g=X3X. Since

(X3+X21)(X4+X1)1(mod3), 

we have

Fp=X3+X21.

Also,

Fq=X3+X21h=X42X3+2X+1Fqg(mod16).

Bob’s public key is

(N, p, q, h)=(5, 3, 16, X42X3+2X+1).

His private key is

f=X4+X1.

Alice takes her message to be m=X2X+1. She chooses ϕ=X1. Then the ciphertext is

c3ϕh+m3X4+6X3+7X24X5(mod16).

Bob decrypts by first computing

afc4X42X35X2+6X2(mod16), 

then

FpaX2X+1(mod3).

Therefore, Bob has obtained the message.

23.4.1 An Attack on NTRU

Let h=hN1XN1++h0. Form the N×N matrix

H=(h0h1hN1hN1h0hN2h1h2h0).

If we represent f=fN1XN1++f0 and g=gN1XN1++g0 by the row vectors

f¯=(f0, , fN1)andg¯=(g0, , gN1), 

then we see that fHg(modq).

Let I be the N×N identity matrix. Form the 2N×2N matrix

M=IH0qI.

Let L be the lattice generated by the rows of M. Since gfh(modq), we can write g=fh+qy for some polynomial y. Represent y as an N-dimensional row vector y, so (f, y) is a 2N-dimensional row vector. Then

(f, y)M=(f, g), 

so (f¯, g¯) is in the lattice L (see Exercise 3). Since f and g have small coefficients, (f¯, g¯) 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 (f¯, g¯). 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 2Nth 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 αI for a suitably chosen real number α. This makes the resulting short vector (αf¯, g¯) 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.