NTRUSign

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.

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 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. 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 claimed that at least 2³⁰ 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.