Abstract
In 1996, a new cryptosystem called NTRU was introduced, related to the hardness of finding short vectors in specific lattices. At Eurocrypt 2001, the NTRU Signature Scheme (NSS), a signature scheme apparently related to the same hard problem, was proposed. In this paper, we show that the problem on which NSS relies is much easier than anticipated, and we describe an attack that allows efficient forgery of a signature on any message. Additionally, we demonstrate that a transcript of signatures leaks information about the secret key: using a correlation attack, it is possible to recover the key from a few tens of thousands of signatures. The attacks apply to the recently proposed parameter sets NSS251-3-SHA1-1, NSS347-3-SHA1-1, and NSS503-3-SHA1-1 in [2]. Following the attacks, NTRU researchers have investigated enhanced encoding/verification methods in [11].
This work has been partially supported by the French Ministry of Research under the RNRT Project “Turbo-Signatures”
Chapter PDF
Similar content being viewed by others
Keywords
References
H. Cohen. A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, 138. Springer, 1993.
D. Coppersmith and A. Shamir. Lattice Attacks on NTRU. In Proc. of Eurocrypt’ 97, LNCS 1233, pages 52–61. Springer-Verlag, 1997.
G. H. Hardy, E. M. Wright. An Introduction to the Theory of Numbers, 5th edition. Oxford University Press, 1979.
J. Hoffstein, J. Pipher and J.H. Silverman. NTRU: A New High Speed Public Key Cryptosystem. In Proc. of Algorithm Number Theory (ANTS III), LNCS 1423, pages 267–288. Springer-Verlag, 1998.
J. Hoffstein, J.H. Silverman. NSS: The NTRU Signature Scheme. Preliminary version, August 2000.
J. Hoffstein, J. Pipher, J.H. Silverman. NSS: The NTRU Signature Scheme. Preprint, November 2000. Available from http://www.ntru.com.
J. Hoffstein, J. Pipher, J.H. Silverman. NSS: The NTRU Signature Scheme. In Proc. of Eurocrypt’ 01, LNCS 2045, pages 211–228. Springer-Verlag, 2001.
J. Hoffstein, J. Pipher, J.H. Silverman. NSS: The NTRU Signature Scheme: Theory and Practice. Preprint, 2001. Available from http://www.ntru.com.
J. Hoffstein, J. Pipher, J.H. Silverman. Enhanced encoding and verification methods for the NTRU signature scheme. Previously posted on http://www.ntru.com/technology/tech.technical.htm.
J. Hoffstein, J. Pipher, J.H. Silverman. Enhanced encoding and verification methods for the NTRU signature scheme (ver. 2). May 30, 2001. Available from http://www.ntru.com/technology/tech.technical.htm.
A. Lenstra, H. Lenstra, and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann. 261, pages 515–534, 1982.
I. Mironov. A Note on Cryptanalysis of the Preliminary Version of the NTRU Signature Scheme. Preprint, January 2001. Available at http://eprint.iacr.org/2001/005/.
P. Nguyen and J. Stern. Lattice Reduction in Cryptology: An Update. In Proc. of Algorithm Number Theory (ANTS IV), LNCS 1838, pages 85–112. Springer-Verlag, 2000.
J. Stern. A method for finding codewords of small weight. Coding Theory and applications, LNCS 388, pages 106–113. Springer-Verlag, 1989.
R. Scheidler and H. C. Williams. A public-key cryptosystem utilizing cyclotomic fields. Designs, Codes and Cryptography 6, pages 117–131, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gentry, C., Jonsson, J., Stern, J., Szydlo, M. (2001). Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001. In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_1
Download citation
DOI: https://doi.org/10.1007/3-540-45682-1_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42987-6
Online ISBN: 978-3-540-45682-7
eBook Packages: Springer Book Archive