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.
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.
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.