The NTRU Public Key Cryptosystem

This tutorial describes how the NTRU Public Key Cryptosystem (PKCS) works.

1. NTRU PKCS Parameters
2. Key Generation
3. Encryption
4. Decryption
5. Why It Works
6. Next Steps
7. Further Reading

1. NTRU PKCS Parameters

The basic collection of objects used by the NTRU Public Key Cryptosystem is the ring R that consists of all truncated polynomials of degree N-1 having integer coefficients:

a = a₀ + a₁X + a₂X² + a₃X³ + . . . + a_N-2X^N-2 + a_N-1X^N-1.

Polynomials are added in the usual way. They are also multiplied more-or-less as usual, except that X^N is replaced by 1, X^N+1 is replaced by X, X^N+2 is replaced by X², and so on. For more details about the ring R, see Section 2 of the Algebra Tutorial.

A full implementation of the NTRU Public Key Cryptosystem is specified by a number of parameters. However, for the purposes of this overview we'll concentrate on the three most important:

N - the polynomials in the truncated polynomial ring have degree N-1.
q - large modulus: usually, the coefficients of the truncated polynomials will be reduced mod q.
p - small modulus. As the final step in decryption, the coefficients of the message are reduced mod p.

In order to ensure security, it is essential that p and q have no common factors. The following table gives some possible values for NTRU parameters at various security levels.

N q p Moderate Security 167 128 3 Standard Security 251 128 3 High Security 347 128 3 Highest Security 503 256 3

These values are provided to give you some idea of the quantities used in commercial applications (in fact, for commerical applications we take p to have a slightly different form; more details are in the Advanced Topics section). For the examples in this tutorial we will use much smaller parameter values:

N q p Small Illustration Parameters 11 32 3

back to top

2. Key Generation

Key Generation Overview
Bob wants to create a public/private key pair for the NTRU Public Key Cryptosystem. He first randomly chooses two "small" polynomials f and g in the ring of truncated polynomials R.

• A "small" polynomial is small relative to a random polynomial mod q. In a random polynomial, the coefficients will in general be randomly distributed mod q; in a small polynomial, the coefficients are much smaller than q.

Bob must keep the values of the polynomials f and g private, since anyone who knows the value of either one of them will be able to decrypt messages sent to Bob.

Bob's next step is to compute the inverse of f modulo q and the inverse of f modulo p. Thus he computes polynomials f_q and f_pwith the property that

f*f_q = 1 (modulo q) and f*f_p = 1 (modulo p).

(If by some chance these inverses do not exist, Bob will need to go back and choose another f. For information about computing inverses in the ring of truncated polynomials, see Section 3 of the Algebra Tutorial.) Now Bob computes the product

h = pf_q*g (modulo q).

Bob's private key is the pair of polynomials f and f_p. Bob's public key is the polynomial h.

Key Generation: Example

As described in Section 1, the example parameters are:

N=11   q=32   p=3

We also need to define a "small" polynomial more precisely. For the purposes of this example, we do this using the quantities d_f and d_g.

• The polynomial f has d_f coefficients equal to +1, (d_f-1) coefficients equal to -1, and the rest equal to 0.
• The polynomial g has dg coefficients equal to +1, d_g coefficients equal to -1, and the rest equal to 0.

(The reason for the slight difference in form between f and g is that f has to be invertible, while g doesn't).

For the purposes of this tutorial, we take

d_f = 4   d_g = 3.

So Bob needs to choose a polynomial f of degree 10 with four 1's and three -1's, and he needs to choose a polynomial g of degree 10 with three 1's and three -1's. Suppose he chooses:

f = -1 + X + X² - X⁴ + X⁶ + X⁹ - X¹⁰
g = -1 + X² + X³ + X⁵ - X⁸ - X¹⁰

Next Bob computes the inverse f_p of f modulo p and the inverse f_q of f modulo q. He finds that:

f_p = 1 + 2X + 2X³ + 2X⁴ + X⁵ + 2X⁷ + X⁸ + 2X⁹
f_q = 5 + 9X + 6X² + 16X³ + 4X⁴ + 15X⁵ + 16X⁶ + 22X⁷ + 20X⁸ + 18X⁹ + 30X¹⁰

The final step in key creation is to compute the product

h = pf_q*g = 8 + 25X + 22X² + 20X³ + 12X⁴ + 24X⁵ + 15X⁶ + 19X⁷ + 12X⁸ + 19X⁹ + 16X¹⁰ (modulo 32).

Bob's private key is the pair of polynomials f and f_p, and his public key is the polynomial h.

back to top

3. Encryption

Encryption: Overview

Alice wants to send a message to Bob using Bob's public key h. She first puts her message in the form of a polynomial m whose coefficients are chosen modulo p, say between -p/2 and p/2 (in other words, m is a small polynomial mod q). Next she randomly chooses another small polynomial, r. This is the "blinding value", which is used to obscure the message (similar to the way that the ElGamal algorithm uses a one-time random value when encrypting).

Alice uses the message m, her randomly chosen polynomial r, and Bob's public key h to compute the polynomial

e = r*h + m (modulo q).

The polynomial e is the encrypted message which Alice sends to Bob.

Encryption: Example

As before, we need to specify what we mean by saying that r is a "small" polynomial. We do this using the quantity d_r.

• r has d_r of its coefficients equal to 1, it has d_r of its coefficients equal to -1, and it has all of the rest of its coefficients equal to 0.

For the purposes of this tutorial, we take

d_r = 3.

Now, suppose Alice wants to send the message

m = -1 + X³ - X⁴ - X⁸ + X⁹ + X¹⁰

to Bob using Bob's public key

h = 8 + 25X + 22X² + 20X³ + 12X⁴ + 24X⁵ + 15X⁶ + 19X⁷ + 12X⁸ + 19X⁹ + 16X¹⁰.

She first chooses a random polynomial r of degree 10 with three 1's and three -1's. Say she chooses

r = -1 + X² + X³ + X⁴ - X⁵ - X⁷.

Then her encrypted message e is

e = r*h + m = 14 + 11X + 26X² + 24X³ + 14X⁴ + 16X⁵ + 30X⁶ + 7X⁷ + 25X⁸ + 6X⁹ + 19X¹⁰ (modulo 32).

Alice sends the encrypted message e to Bob.

back to top

4. Decryption

Decryption: Overview

Now Bob has received Alice's encrypted message e and he wants to decrypt it. He begins by using his private polynomial f to compute the polynomial

a = f*e (modulo q).

Since Bob is computing a modulo q, he can choose the coefficients of a to lie between -q/2 and q/2. (In general, Bob will choose the coefficients of a to lie in an interval of length q. The specific interval depends on the form of the small polynomials. See the Advanced Topics tutorial for details.) It is very important that Bob does this before performing the next step. Bob next computes the polynomial

b = a (modulo p).

That is, he reduces each of the coefficients of a modulo p. Finally Bob uses his other private polynomial f_p to compute

c = fp*b (modulo p).

The polynomial c will be Alice's original message m.

Decryption: Example

Bob has received the encrypted message

e = 14 + 11X + 26X² + 24X³ + 14X⁴ + 16X⁵ + 30X⁶ + 7X⁷ + 25X⁸ + 6X⁹ + 19X¹⁰

from Alice. He uses his private key f to compute

a = f*e = 3 - 7X - 10X² - 11X³ + 10X⁴ + 7X⁵ + 6X⁶ + 7X⁷ + 5X⁸ - 3X⁹ - 7X¹⁰ (modulo 32).

Note that when Bob reduces the coefficients of f*e modulo 32, he chooses values lying between -15 and 16, not between 0 and 31. It is very important that he choose the coefficients in this way. Next Bob reduces the coefficients of a modulo 3 to get

b = a = - X - X² + X³ + X⁴ + X⁵ + X⁷ - X⁸ - X¹⁰ (modulo 3).

Finally Bob uses f_p, the other part of his private key, to compute

c = fp*b = - 1 + X³ - X⁴ - X⁸ + X⁹ + X¹⁰ (modulo 3).

The polynomial c is Alice's message m, so Bob has successfully decrypted Alice's message.

back to top

5. Why It Works

Alice's encrypted message e looks like e = r*h + m (modulo q), but of course Bob doesn't initially know the values of r and m. Bob's first step is to compute f*e and reduce the coefficients modulo q. Remember that Bob's public key h was actually formed by multiplying pf_q*g and reducing its coefficients modulo q. So although Bob doesn't know r and m, when he computes a = f*e (modulo q), he is actually performing the following computation:

a = f*e (modulo q)   = f*(r*h + m) (modulo q) [since e = r*h + m (modulo q)] = f*(r*pfq*g + m) (modulo q) [since h = pfq*g (modulo q)] = pr*g + f*m (modulo q) [since f*fq = 1 (modulo q)]

Now look back at the sizes of the various parameters. The polynomials r, g, f, and m all have coefficients that are quite small. This means that the coefficients of the products r*g and f*m are also quite small, at least in comparison to q. Since the prime p is also small compared to q, this means (assuming that the parameters have been properly chosen) that the coefficients of the polynomial pr*g + f*m already lie between -q/2 and q/2, so reducing the coefficients modulo q has no effect at all!

In other words, when Bob computes a by first mulitplying f*e and then reducing the coefficients modulo q, the polynomial a that he ends up with is exactly equal to the polynomial pr*g + f*m. When Bob next reduces the coefficients of a modulo p to form the polynomial b, he is really reducing the coefficients of pr*g + f*m modulo p, so the b that he ends up with is equal to

b = f*m (modulo p).

Keep in mind that Bob still doesn't know the value of m, but he now knows the value of b. So his final step is to multiply b by f_p and use the fact that f_p*f = 1 (modulo p) to compute

c = fp* b = fp* f*m = m (modulo p),

which allows him to recover Alice's message m.

back to top

Next Steps

This page has outlined the main concepts behind the NTRU cryptosystem. As described, it is already highly efficient. However, there are some parameter and implementation enhancements that we can use to speed up operations even more. These additional techniques are explained in the Advanced Topics tutorial and in the Low Hamming Weight Polynomials tutorial.

back to top

Further Reading

A complete description of the NTRU Public Key Cryptosystem with full technical details is given in the paper

NTRU: A Ring Based Public Key Cryptosystem, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, in Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.

Further enhancements to NTRU, including the use of f=1+p*F and p=X+2, are described in

Optimizations for NTRU, J. Hoffstein, J. Silverman, Public-Key Cryptography and Computational Number Theory (Warsaw, September 11-15, 2000), DeGruyter, to appear.

A description of how to speed up NTRU and other cryptosystems by the use of quantities with small Hamming weight can be found in

Random Small Hamming Weight Products with Applications to Cryptography, J. Hoffstein, J. Silverman, Com2MaC Workshop on Cryptography (Pohang, Korea, June 2000), Discrete Mathematics, to appear.

These papers and short notes giving further information may be downloaded in a variety of formats from the NTRU Technical Center.

The following are some additional sources to learn about algebra, number theory, algorithms, and cryptography.

• A Course in Computational Algebraic Number Theory, H. Cohen, GTM 138, Springer-Verlag, Berlin, 1993.
• A Friendly Introduction to Number Theory, J.H. Silverman, Prentice-Hall, New Jersey, 1997.
• Cryptography: Theory and Practice, D. Stinson, CRC Press, Boca Raton, 1995.

Handbook of Cryptography, S. Vanstone, P. Van Oorschot, A. Menezes, CRC Press, Boca Raton, 1996.

back to top