NTRU Announces Signature Algorithm, NTRUSign

A preprint of the NTRUSign paper was released on Monday, December 10th at the rump session of AsiaCrypt 2001. The full paper was published in the proceedings of the Cryptographer's Track at the RSA Conference 2003. The following resources provide more information about the algorithm.

Links

NTRUSign: Digital Signatures Using the NTRU Lattice: the preprint distributed at AsiaCrypt 2001, in .pdf or .ps form.

NTRUSign: Digital Signatures Using the NTRU Lattice: the CT-RSA 2003 proceedings version of the paper, in .pdf or .ps form.

Peer Review and Independent Scrutiny of the NTRUEncrypt Public Key Cryptosystem - an updated document summarizing the results of independent scruntiny of the different proposed cryptosystems based on the NTRU lattice. Available as [.pdf] or [.html].

Tutorials - a tutorial introduction to NTRU security.

FAQ

1. What is the core idea of the NTRUSign algorithm?
2. Is there any difference between how NTRUSign and NTRUEncrypt use the NTRU lattice?
3. What's the difference between this algorithm and NSS?
4. What were the details of the attacks on NSS?
5. What hard problems does NTRUSign depend on?
6. Is the NTRUSign algorithm patented?
7. Is the NTRUSign algorithm available for software or hardware evaluation?

What is the core idea of the NTRUSign algorithm?
The NTRUSign algorithm is based on the difficulty of finding a point in a lattice which is close to a random vector in space. This is known as the Approximate Closest Vector Problem, or appr-CVP. For an introduction to lattices, see Technical FAQ, question 3.

In NTRUSign, the signer knows a good basis for the entire lattice, and uses this to solve appr-CVP for an arbitrary point in space which is linked to the document to be signed. The verifier knows a bad, public, basis for the lattice, and so can verify that the signature is a lattice point and that it is close to the point associated with the signed document.

The underlying idea of basing a signature scheme on the use of a good basis to find close vectors in a lattice was proposed by Goldreich, Goldwasser and Halevi in their 1998 paper, Public-key cryptography from lattice reduction problems. However, in that case the keys and signatures were of size N2 lnN (where N is the dimension of the lattice), making the keys impractically large if the scheme was to be secure. The breakthrough in NTRUSign is that we have been able to use the techniques of the NTRU lattice to achieve an N-fold improvement in speed and keylength.

back to top

Is there any difference between how NTRUSign and NTRUEncrypt use the NTRU lattice?
NTRUSign and NTRUEncrypt are based on exactly the same hard lattice problem. For an introduction to how this lattice is used in NTRUEncrypt, see the NTRU Learning Center.

In both NTRUSign and NTRUEncrypt, key generation starts by generating two small private polynomials, f and g, and the larger public polynomial h = g/f mod q. All of these polynomials have the same form in NTRUSign as they do in NTRUEncrypt, and they form a good basis for half of the NTRU lattice. However, in NTRUSign, the person generating the key must also find a good basis for the other half of the lattice. This means that NTRUSign private keys are larger than the corresponding private keys for NTRUEncrypt. However, the underlying lattice problem is the same.

back to top

What's the difference between this algorithm and NSS?
NSS, the NTRU Signature Scheme, was first proposed at the rump session of Crypto 2000, and successfully attacked (following a series of other results) by Gentry and Szydlo at the rump session of Crypto 2001. NSS was also related to solving appr-CVP in the NTRU lattice. However, because the signer only knew half of the good basis, it was necessary to introduce a certain structure into the points representing messages to be signed. This structure was exploited by attackers.

NTRUSign, in contrast, is a transparent implementation of appr-CVP in the NTRU lattice. The points to be signed do not have any structure, nor do they need to. None of the attacks against NSS have any applicability against NTRUSign.

back to top

What were the details of the attacks on NSS?
None of the attacks on NSS compromised the security of the NTRUEncrypt algorithm, or of the principles underlying NTRU's technology. Indeed, many of the attacks were based on observations of how the NSS algorithm differed from NTRUEncrypt:

• In an early version of the NSS algorithm, the private key polynomials had some coefficients that were much larger than the average. This fact, and an attack based on it, were noted independently by Mironov and the NTRU research team. The attack does not apply to NTRUEncrypt or NTRUSign. In these algorithms, the secret polynomials have very little structure, and their coefficients lie within a narrow range.
• The NSS algorithm relied for security on the fact that some coefficients of the signature polynomial had been reduced modulo the parameter q. However, the signature polynomial was the product of two small polynomials, and because of this it was possible for an attacker to detect which coefficients had been reduced and correct for this reduction, "lifting" the polynomial to the space of the integers and halving the effective size of the lattice. This attack does not apply to NTRUEncrypt. Although NTRUEncrypt relies for its security on the fact that the coefficients of the ciphertext have been reduced modulo q, the ciphertext is the product of one small polynomial and one (statistically) random one. This means that almost all coefficients will naturally be reduced mod q, and there appears to be no way for an attacker to lift in this case.
• In the version of the NSS algorithm that appears in the Eurocrypt proceedings, the verification tests did not check tightly enough that the signature was bound to the correct message. There is no analogy between this and any possible attack on NTRUEncrypt or NTRUSign.

back to top

What hard problems does NTRUSign depend on?
Forging a signature given only a public key, or recovering a private key from the corresponding public key, are equivalent respectively to solving the approximate closest vector problem and the short vector problem in the NTRU lattice.

All lattice-based signature schemes slowly leak information about the geometry of the lattice, and it is important to be able to quantify the point at which this information is useful to an attacker.

After about 10-20,000 signatures have been generated by a given key, the attacker knows additional information; this is known as the Gram matrix of the lattice basis. This information (known as "second-moment information") does not reduce the dimension of the lattice problem which must be solved, and there is currently no known way of exploiting it. The current version of the paper additionally suggests simple enhancements to the signing algorithm which appear to remove all possibility of recovering useful information from second moment attacks.

After many, many more signatures - significantly more than a billion - have been generated by a given key, additional information (known as "fourth-moment information") becomes available to an attacker which may endanger the security of the private key. This is the only known attack that recovers the private key in less time than an attack on the core NTRU lattice problem. To prevent it, it is sufficient to roll over the signing key after a billion signatures have been generated. In order to be conservative, we recommend that an implementation rolls over the signing key after 10⁷ signatures. This frequency of key rollover is consistent with good security practice for virtually any architecture. The enhancements mentioned above can also be extended to greatly reduce or eliminate the risk posed by fourth-moment attacks.

back to top

Is the NTRUSign algorithm patented?
The NTRUSign algorithm is patent pending worldwide. For further details, contact info@ntru.com.

back to top

Is the NTRUSign algorithm available for software or hardware evaluation?
To arrange an evaluation, please contact info@ntru.com.

back to top