Making NTRUEncrypt and NTRUSign as Secure as 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 IdSIS and RLWE
problems.
Download:
Eurocrypt'11 proceedings version: pdf
Full version: pdf.
Homepage