NTRUSign

NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99.[1] The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003.[2] The 2003 publication included parameter recommendations for 80-bit security. A subsequent 2005 publication revised the parameter recommendations for 80-bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm.

NTRUSign involves mapping a message to a random point in 2N-dimensional space, where N is one of the NTRUSign parameters, and solving the closest vector problem in a lattice closely related to the NTRUEncrypt lattice. NTRUSign is claimed to be faster than those algorithms at low security levels, and considerably faster at high security levels. However, analysis had shown that original scheme is insecure and would leak knowledge of private key.[3][4]

A redesigned pqNTRUSign had been submitted to the NIST Post-Quantum Cryptography Standardization competition.[5] It is based on "hash-and-sign" (contrasting Fiat–Shamir transformation) methodology, and claims to achieve smaller signature size.

NTRUSign is under consideration for standardization by the IEEE P1363 working group.[citation needed]

  1. ^ Hoffstein, Jeffrey; Lieman, Daniel; Silverman, Joseph H. (1999). "Polynomial Rings and Efficient Public Key Authentication" (PDF). International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC'99). City University of Hong Kong Press.
  2. ^ Hoffstein, Jeffrey; Howgrave-Graham, Nick; Pipher, Jill; Silverman, Joseph H.; Whyte, William (2003). "NTRUSign: Digital Signatures Using the NTRU Lattice" (PDF). Topics in Cryptology — CT-RSA 2003. LNCS. Vol. 2612. Springer. pp. 122–140.
  3. ^ Cite error: The named reference :0 was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference :1 was invoked but never defined (see the help page).
  5. ^ "NIST Post Quantum Crypto Submission". OnBoard Security. Archived from the original on 2017-12-29. Retrieved 2018-03-20.