NTRUSign, also known as the NTRU Signature Algorithm, is an
NTRU
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unli ...
public-key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
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. 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
The RSA Conference is a series of IT security conferences. Approximately 45,000 people attend one of the conferences each year. It was founded in 1991 as a small cryptography conference. RSA conferences take place in the United States, Europe, Asia ...
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 2''N''-dimensional space, where ''N'' is one of the NTRUSign parameters, and solving the
closest vector problem in a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
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.
A redesigned pqNTRUSign had been submitted to the
NIST Post-Quantum Cryptography Standardization competition. 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
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operat ...
P1363 working group.
Security
It was demonstrated in 2000 by Wu, Bao, Ye and Deng that the signature of PASS, the original version of NTRUSign, can be forged easily without knowing the private key. 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.
[http://www.szydlo.com/ntru-revised-full02.pdf ] 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.
[P. Nguyen and O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures", available from https://cims.nyu.edu/~regev/papers/gghattack.pdf]
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 2
30 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.
The pqNTRUSign claims a 128-bit classical and quantum security for their given parameter set.
References
External links
Most recent NTRUSign paper, including parameter sets for multiple security levelsA Java implementation of NTRUSign
{{Cryptography navbox , public-key
Digital signature schemes
Post-quantum cryptography
Lattice-based cryptography