Advertisement

NSS: An NTRU Lattice-Based Signature Scheme

  • Jeffrey Hoffstein
  • Jill Pipher
  • Joseph H. Silverman
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

Abstract

A new authentication and digital signature scheme called the NTRU Signature Scheme (NSS) is introduced. NSS provides an authentication/signature method complementary to the NTRU public key cryptosystem. The hard lattice problem underlying NSS is similar to the hard problem underlying NTRU, and NSS similarly features high speed, low footprint, and easy key creation.

Keywords

digital signature public key authentication lattice-based cryptography NTRU NSS 

References

  1. 1.
    E.F. Brickell and K.S. McCurley. Interactive Identification and Digital Signatures, AT&T Technical Journal, November/December, 1991, 73–86.Google Scholar
  2. 2.
    L.C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing bothtr ansmission and memory, Advances in Cryptology-Eurocrypt '88, Lecture Notes in Computer Science 330 (C.G. Günther, ed.), Springer-Verlag, 1988, 123–128.Google Scholar
  3. 3.
    J. Hoffstein, B.S. Kaliski, D. Lieman, M.J.B. Robshaw, Y.L. Yin, Secure user identification based on constrained polynomials, US Patent 6,076,163, June 13, 2000.Google Scholar
  4. 4.
    J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: A new high speed public key cryptosystem, in Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, Lecture Notes in Computer Science 1423 (J.P. Buhler, ed.), Springer-Verlag, Berlin, 1998, 267–288.Google Scholar
  5. 5.
    J. Hoffstein, J. Pipher, J.H. Silverman, NSS: A Detailed Analysis of the NTRU Lattice-Based Signature Scheme, < http://www.ntru.com >.
  6. 6.
    J. Hoffstein, D. Lieman, J.H. Silverman, Polynomial Rings and Efficient Public Key Authentication, in Proceeding of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC '99), Hong Kong, (M. Blum and C.H. Lee, eds.), City University of Hong Kong Press.Google Scholar
  7. 7.
    J. Hoffstein, J.H. Silverman, Polynomial Rings and Efficient Public Key Authentication II, in Proceedings of a Conference on Cryptography and Number Theory (CCNT '99), (I. Shparlinski, ed.), Birkhauser.Google Scholar
  8. 8.
    A.J. Menezes, Software Implementation of Elliptic Curve Cryptosystems Over Binary Fields, presentation at CHES 2000, August 17, 2000.Google Scholar
  9. 9.
    A.J. Menezes and P.C. van Oorschot and S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1996.Google Scholar
  10. 10.
    I. Mironov, A note on cryptanalysis of the preliminary version of the NTRU signature scheme, IACR preprint server, < http://eprint.iacr.org/2001/005/ >
  11. 11.
    T. Okamoto. Provably secure and practical identification schemes and corresponding signature schemes, Advances in Cryptology-Crypto '92, Lecture Notes in Computer Science 740 (E.F. Brickell, ed.) Springer-Verlag, 1993, 31–53.Google Scholar
  12. 12.
    C.-P. Schnorr. Efficient identification and signatures for smart cards, Advances in Cryptology-Crypto '89, Lecture Notes in Computer Science 435 (G. Brassard, ed), Springer-Verlag, 1990, 239–251.CrossRefGoogle Scholar
  13. 13.
    J.H. Silverman. Estimated Breaking Times for NTRU Lattices, NTRU Technical Note #012, March 1999, < http://www.ntru.com >.
  14. 14.
    J.H. Silverman. Almost Inverses and Fast NTRU Key Creation, NTRU Technical Note #014, March 1999, < http://www.ntru.com >.
  15. 15.
    J. Stern. A new identification scheme based on syndrome decoding, Advances in Cryptology-Crypto '93, Lecture Notes in Computer Science 773 (D. Stinson, ed.), Springer-Verlag, 1994, 13–21.CrossRefGoogle Scholar
  16. 16.
    J. Stern. Designing identification schemes with keys of short size, Advances in Cryptology-Crypto '94, Lecture Notes in Computer Science 839 (Y.G. Desmedt, ed), Springer-Verlag,1994, 164–173.Google Scholar
  17. 17.
    D. Stinson, Cryptography: Theory and Practice. CRC Press, 1997.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Jeffrey Hoffstein
    • 1
  • Jill Pipher
    • 1
  • Joseph H. Silverman
    • 1
  1. 1.NTRU Cryptosystems, Inc.BurlingtonUSA

Personalised recommendations