Cryptology ePrint Archive: Report 2013/004

Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices

Damien Stehlé and Ron Steinfeld

Abstract: NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security and that of its digital signature counterpart. In the present work, we show how to modify NTRUEncrypt and NTRUSign to make them provably secure in the standard (resp. random oracle) model, under the assumed quantum (resp. classical) hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields.

Our main contribution is to show that if the secret key polynomials of the encryption scheme are selected from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. We also show how to rigorously extend the encryption secret key into a signature secret key. The security then follows from the already proven hardness of the R-SIS and R-LWE problems.

Category / Keywords: public-key cryptography / Lattice based cryptography, NTRU, ideal lattices, provable security.

Publication Info: Submitted. Some of the results in this paper have been presented in preliminary form at Eurocrypt 2011.

Date: received 3 Jan 2013

Contact author: ron steinfeld at monash edu

Available formats: PDF | BibTeX Citation

Note: The results in this paper improve and significantly extend those in the Eurocrypt 2011 version; the most significant addition is the security analysis of a provably secure variant of NTRUSign.

Version: 20130111:212943 (All versions of this report)

Discussion forum: Show discussion | Start new discussion