A Variant of NTRU with Non-Invertible Polynomials

This is a preprint of a book chapter published in Lecture Notes in Computer Science, 2551, Springer-Verlag, Berlin (2003). The original publication is available at www.springerlink.com.We introduce a generalization of the NTRU cryptosystem and describe its advantages and disadvantages as compared with the original NTRU protocol. This extension helps to avoid the potential problem of finding “enough” invertible polynomials within very thin sets of polynomials, as in the original version of NTRU. This generalization also exhibits certain attractive “pseudorandomness” properties that can be proved rigorously using bounds for exponential sums