# 23.4 NTRU

If the dimension  is large, say , 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 . We will work with the set of polynomials of degree less than . Let



be two such polynomials. Define



where



The summation is over all pairs  with .

For example, let , let , and let . Then the coefficient  of  in  is



and



From a slightly more advanced viewpoint,  is simply multiplication of polynomials mod  (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  with the requirements that  and that  is much smaller than . 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  and  with small coefficients (we’ll say more about how to choose them later). Moreover,  should be invertible mod  and mod , which means that there exist polynomials  and  of degree less than  such that



Bob calculates



Bob’s public key is



His private key is . Although  can be calculated easily from , he should store (secretly)  since he will need it in the decryption process. What about ? Since , 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  of degree less than  with coefficients of absolute value at most . When , this means that  has coefficients . Alice then chooses a small polynomial  (“small” will be made more precise shortly) and computes



She sends the ciphertext  to Bob.

Bob decrypts by first computing



with all coefficients of the polynomial  of absolute value at most , 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 . But here is why the decryption is usually correct. We have



Since , , ,  have small coefficients and  is much smaller than , it is very probable that , before reducing mod , has coefficients of absolute value less than . In this case, we have equality



Then



so the decryption works.

For , the recommended choices for  are



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

For , the recommended choices for  are



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

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

# Example

Let  (this choice of  is much too small for any security; we use it only in order to give an explicit example). Take  and . Since



we have



Also,



Bob’s public key is



His private key is



Alice takes her message to be . She chooses . Then the ciphertext is



Bob decrypts by first computing



then



Therefore, Bob has obtained the message.

# 23.4.1 An Attack on NTRU

Let . Form the  matrix



If we represent  and  by the row vectors



then we see that .

Let  be the  identity matrix. Form the  matrix



Let  be the lattice generated by the rows of . Since , we can write  for some polynomial . Represent  as an -dimensional row vector , so  is a -dimensional row vector. Then



so  is in the lattice  (see Exercise 3). Since  and  have small coefficients,  is a small vector in the lattice . 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 . Once the attacker has found  and , 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  sufficiently large. However, if  is too large, the encryption and decryption algorithms become slow. The suggested values of  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 th root of the determinant of the -dimensional lattice). Improvements in the above lattice attack can be obtained by replacing  in the upper left block of  by  for a suitably chosen real number . This makes the resulting short vector  comparatively shorter and thus easier to find. The parameters in NTRU, especially the sizes of  and , 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.