TY - GEN
T1 - Making NTRU as secure as worst-case problems over ideal lattices
AU - Stehlé, Damien
AU - Steinfeld, Ron
PY - 2011
Y1 - 2011
N2 - 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 could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum 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 are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.
AB - 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 could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum 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 are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.
UR - http://www.scopus.com/inward/record.url?scp=79958014767&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20465-4_4
DO - 10.1007/978-3-642-20465-4_4
M3 - Conference proceeding contribution
AN - SCOPUS:79958014767
SN - 9783642204647
VL - 6632 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 27
EP - 47
BT - Advances in Cryptology - EUROCRYPT 2011, 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Paterson, Kenneth G.
PB - Springer, Springer Nature
CY - Heidelberg, Germany
T2 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, EUROCRYPT 2011
Y2 - 15 May 2011 through 19 May 2011
ER -