The NTRU Trapdoor One-way Function

NTRU : Nth Degree Truncated Polynomial Ring Units

The NTRU problem: Let  Given  where  for  and  being invertible in  and  find .

Based on the presumed hardness of the above problem, we can construct a trapdoor one-way function familyas follows: to generate a random element from the family, we choose secret invertible polynomials with  being invertible in  and  and output the public key to be

The secret key is .

The one-way function mapping  to  computes

Observe that in order to recover  it is enough to recover these modulo  since there is a correspondence between elements in  and residues modulo 

To recover  modulo  using the secret key, one first computes

The first equality (in the ring  ) simply follows from the definition of  and . The second equality only holds true if the preceding equation holds true not only in  but also over  Here is where we again use the fact that the coefficients of  and  are small with respect to  and can bound them to be less than  (either always or with very high probability). If this is the case, then we have

where we multiplied by the inverse of  in 

Once we have  which is the same as  we can also compute