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.

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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Submitted. Some of the results in this paper have been presented in preliminary form at Eurocrypt 2011.
Keywords
Lattice based cryptographyNTRUideal latticesprovable security.
Contact author(s)
ron steinfeld @ monash edu
History
Short URL
https://ia.cr/2013/004

CC BY

BibTeX

@misc{cryptoeprint:2013/004,
author = {Damien Stehlé and Ron Steinfeld},
title = {Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices},
howpublished = {Cryptology ePrint Archive, Paper 2013/004},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/004}},
url = {https://eprint.iacr.org/2013/004}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.