Format of NTRUEncrypt Challenge Problems

This page describes the information provided for each of the challenge problems. Click here to return to the challenges home page. This page contains the following:

• Information Provided for each Challenge Problem
• Fundamental Parameters
• Key Generation
• Message Encryption
• Representation of polynomials

Representation of polynomials

Polynomials of degree N-1 are given here as lists of their coefficients. Thus the list of numbers
h = [h₀, h₁, h₂, . . . , h_N-2, h_N-1]

represents the polynomial
h = h₀+ h₁X + h₂X² + h₃X³ + . . . + h_N-2X^N-2 + h_N-1X^N-1.

The following polynomials have this representation:

• p, the small modulus
• h, the public key.
• H, the pseudo-inverse of the public key.
• P, the inverse of p modulo q in the ring R (that is, Pp = 1 modulo q)
• E, the challenge encrypted message.
  • Summary of Information Provided for each Problem
• The Challenge Problems
  • The Decryption Challenge
  • The Key Recovery Challenge

Information Provided for each Challenge Problem

Fundamental Parameters
Operations in the NTRUEncrypt cryptosystem are performed on polynomials of degree N-1 whose coefficients are reduced mod q. See the Introductory Tutorial for more details. The cryptosystem is further characterized by a small modulus, p. As explained in the Advanced Tutorial, standard practice is to take p to be the polynomial 2+X. For each challenge problem, we provide N, q, p, and P, the inverse of p modulo q in the ring R (that is, Pp = 1 modulo q). This last value is used to check candidate answers to the problem.

back to top

Key Generation
An NTRUEncrypt private key consists of two polynomials, f and g.

• The polynomial f has the form 1 + p.F, where F is a polynomial chosen to have d_f coefficients equal to 1 and N-d_f coefficients equal to 0. We provide the value d_f for each challenge problem.
• The polynomial g is a binary polynomial chosen to have d_g coefficients equal to 1 and N-d_g coefficients equal to 0. We provide the value d_g for each challenge problem.

The NTRUEncrypt public key corresponding to f and g is h = p . g . f^-1 mod q. For each challege problem, we provide h. We also provide the polynomial H, which is a pseudo-inverse modulo q of h. It has the property that if a(X) is a polynomial satisfying a(1)=0, then a*H*h = a (modulo q), so H is a sort of inverse modulo q for h. The quantity H will be used below to check if a hypothetical decryption is the correct plaintext message. In practice, the owner of the private key has no need for H unless he for some reason wants to look at the random polynomial used to encrypt the message.

back to top

Message Encryption
The encrypted message e is formed from the plaintext message polynomial m and a randomly chosen polynomial r. The message polynomial m has d_m coefficients equal to 1, and N-d_m coefficients equal to 0. The random polynomial has d_r coefficients equal to 1 and all other coefficients equal to 0. The encrypted message e is a polynomial satisfying e = r*h + m (modulo q).

For each challenge problem, we provide d_m and d_r.

Note that in real-life encryption, an attacker will not know the exact value of d_m.

We also provide the "centering value" A for use in decryption. Its use is explained in the NTRUEncrypt Advanced Tutorial and below in the description of the decryption challenge.

back to top

Representation of polynomials
Polynomials of degree N-1 are given here as lists of their coefficients. Thus the list of numbers
h = [h₀, h₁, h₂, . . . , h_N-2, h_N-1]

represents the polynomial
h = h₀+ h₁X + h₂X² + h₃X³ + . . . + h_N-2X^N-2 + h_N-1X^N-1.

The following polynomials have this representation:

• p, the small modulus
• h, the public key.
• H, the pseudo-inverse of the public key.
• P, the inverse of p modulo q in the ring R (that is, Pp = 1 modulo q)
• E, the challenge encrypted message.

Summary of Information Provided for each Problem
The following information is provided for each challenge problem.
N - the polynomials in the truncated polynomial ring R have degree N-1.
q - large modulus.
p - small modulus (equal to 2+X for all challenge problems).
P - inverse of p modulo q in the ring R (that is, Pp = 1 modulo q).
d_f - the F part of the key has d_f coefficients equal to 1.
d_g - the g part of the key has d_gcoefficients equal to 1.
d_r - the random encryption polynomial has d_r coefficients equal to 1.
d_m - the message has d_m coefficients equal to 1.
h - the public key.
H - the pseudo-inverse modulo q of h.
E - the encrypted message.
A - the centering value.

back to top

The Challenge Problems

The challenge problems presented are for N = 251, 347, and 503. Each problem has both a decryption component and a key recovery component, each with its own reward (see the terms and conditions of the challenge). There is also a warm-up problem with N = 107. We provide the solution for this to help you in testing your algorithms.

back to top

The Decryption Challenge
The first part of each challenge problem is to decrypt the message e. In other words, find the plaintext message m. The plaintext messages used in the challenge problems are random strings with d_m coefficients equal to 1, and all the other coefficients equal to 0.

The centering value A is provided to help in decryption. If you have recovered the key, or if for some other reason you are going to place the coefficients of the message into a range mod q and then reduce mod p, the range mod q should be [A, A+q -1]. A further explanation of the use of A when decrypting with the private key is given in the NTRUEncrypt Advanced Tutorial.

Here is the algorithm for determining if a guessed message m' is equal to the actual plaintext message m.

Decryption Verification Algorithm:

1. If d_m coefficients of m' are +1, and the rest are 0, go to Step 2. Otherwise STOP, m' is NOT the correct message.
2. Compute r = H*(e - m' ) (modulo q).
3. If r has exactly d_r coefficients equal to 1 and all of the rest of its coefficients equal to 0, go to Step 4. Otherwise STOP, m' is NOT the correct message.
4. The guessed message m' is equal to the plaintext message m.

back to top

The Key Recovery Challenge
The second part of each challenge problem is to find the private key f. Solution of the key recovery portion of a challenge problem will also count as solution of the decryption portion.

Here is the algorithm for determining if a guessed key f' is correct.

Key Verification Algorithm:

1. Subtract 1 from f' and multiply the result by P, the inverse of p. This gives F', a candidate for F.
2. If F' has exactly d_f coefficients equal to +1 and all of the rest of its coefficients equal to 0, go to Step 3. Otherwise STOP, f' is NOT the correct key.
3. Compute g = Pf'*h (modulo q).
4. If g has exactly d_g coefficients equal to +1 and all of the rest of its coefficients equal to 0, go to Step 5. Otherwise STOP, f' is NOT the correct key.
5. The guessed key f' is equal to the correct key f.

back to top

Click here to return to the challenges home page.