NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature

Digital signature

A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

 algorithm based on the GGH signature scheme

GGH signature scheme

The Goldreich-Goldwasser-Halevi signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem in a lattice...

. It was first presented at the rump session of Asiacrypt

Asiacrypt

Asiacrypt is an important international conference for cryptography research. The full name of the conference is currently International Conference on the Theory and Application of Cryptology and Information Security, though this has varied over time...

 2001 and published in peer-reviewed form at the RSA Conference

RSA Conference

The RSA Conference is a cryptography and information security-related conference held annually in the San Francisco Bay Area.The RSA Conference started in 1991 as a forum for cryptographers to gather and share the latest knowledge and advancements in the area of Internet security...

 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.

NTRU Cryptosystems, Inc.

Ntru Cryptosystems, Inc. is a provider of embedded security solutions. It was founded in 1996 by Joseph H. Silverman, Jeffrey Hoffstein, Jill Pipher and Daniel Lieman, four mathematicians at Brown University...

 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

Lattice (group)

In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...

 closely related to the NTRUEncrypt

NTRUEncrypt

The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice...

 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(N²) as is the case with other lattice-based signature schemes. Operations take O(N²) time, as opposed to O(N³) for elliptic curve cryptography

Elliptic curve cryptography

Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

 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

IEEE P1363

IEEE P1363 is an Institute of Electrical and Electronics Engineers standardization project for public-key cryptography. It includes specifications for:* Traditional public-key cryptography...

 working group.

Security

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. 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.

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 claim that at least 2³⁰ signatures are needed, and probably considerably more, before a transcript of perturbed signatures enables any useful attack.

External links

• NTRU Cryptosystems, Inc.
• NTRU Cryptosystems's technical website, containing specifications, tutorials and analysis of NTRUEncrypt.
• NTRUSign specification from CT-RSA 2003 (pdf)
• Extended version of CT-RSA paper (pdf)
• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign