World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0003513327
Reproduction Date:

Title: NTRUSign  
Author: World Heritage Encyclopedia
Language: English
Subject: NTRUEncrypt, GGH signature scheme, NTRU, Computational hardness assumption, Benaloh cryptosystem
Publisher: World Heritage Encyclopedia


NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. 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 close vector problem in a lattice closely related to the NTRUEncrypt lattice. This lattice has the property that a private 2N-dimensional basis for the lattice can be described with 2 vectors, each with N coefficients, and a public basis can be described with a single N-dimensional vector. This enables public keys to be represented in O(N) space, rather than O(N2) as is the case with other lattice-based signature schemes. Operations take O(N2) time, as opposed to O(N3) for elliptic curve cryptography and RSA private key operations. NTRUSign is therefore claimed to be faster than those algorithms at low security levels, and considerably faster at high security levels.

NTRUSign is under consideration for standardization by the IEEE P1363 working group.


NTRUSign is not a zero-knowledge signature scheme and a transcript of signatures leaks information about the private key, as first observed by Gentry and Szydlo.[1] Nguyen and Regev demonstrated in 2006 that for the original unperturbed NTRUSign parameter sets an attacker can recover the private key with as few as 400 signatures.[2]

The current proposals use perturbations to increase the transcript length required to recover the private key: the signer displaces the point representing the message by a small secret amount before the signature itself is calculated. NTRU claimed that at least 230 signatures are needed, and probably considerably more, before a transcript of perturbed signatures enabled any useful attack. In 2012 an attack on the scheme with perturbations was presented that required a few thousand signatures for standard security parameters.[3]

External links

  • Most recent NTRUSign paper, including parameter sets for multiple security levels
  • A Java implementation of NTRUSign


  1. ^
  2. ^ P. Nguyen and O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures", available from
  3. ^ Ducas, Léo; Nguyen, Phong (2012). "Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures" (PDF). ASIACRYPT 2012. LNCS 7658. Springer. pp. 433–450.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.