Welcome to the resource topic for 2013/004
Title:
Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices
Authors: Damien Stehlé, 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.
ePrint: https://eprint.iacr.org/2013/004
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .