NTRUSign

NTRUSign is a digital signature scheme, which was developed in 2003 and is based on the Goldreich - Goldwasser - Halevi - signature process and is the successor to the uncertain NSS process, but is also considered unsafe.

Description of the procedure

As well as in NTRUEncrypt NTRUSign also run the calculations (with the exception of the division of the resultant ) from the ring, wherein the multiplication "*" is a cyclic convolution is modulo: The product of two polynomials and.

It can be the basis for NTRUSign either the standard or the transposed grid. The transposed grid has the advantage that the polynomial contains only coefficients in { -1,0,1 }, and can thereby multiply faster.

Further, the parameters, the number of so-called perturbations be selected. However, it has been found that 0 perturbations as a non- necessary uncertain and more, therefore in practice always equal to 1

In addition, the sizes (number of polynomial coefficients ), (modulus ), ( number of coefficients = -1 ), ( Standard Adjustment Factor) and (standard barrier ) is important.

Key generation

It creates so-called bases. Each of which consists of three polynomials are referred to and. The polynomial of the first base is the public key, all polynomials of all other bases constitute the private key.

Base generation

It is the variant of Hoffstein et al here. described. In EESS standard for Inverting polynomials and not in but in takes place. This one comes from though without point numbers and gets 'better' (norm smaller ) polynomials F and G, but must also perform an elaborate resultant calculation.

To generate a base one proceeds as follows:

Signing

Let m be the message to be signed.

For to 0 following steps are performed:

Is the signature.

Note: Under certain circumstances, it may happen that the signature despite valid key is invalid. It is therefore advisable to check the signature after generation and possibly to sign again.

Signature verification

Be the message, the public key and the signature. The standard is given by a polynomial, wherein (the latter is referred to as centered Euclidean norm ).

The signature is then checked as follows:

Note: The calculation of the standard on the definition is inefficient. A better method is to add up all the polynomial coefficients is a constant, so that the two coefficients with the greatest distance equidistant from are removed ( respectively modulo ). The norm is then given by the centered Euklidnorm (see above) of the resulting polynomial.

Efficiency

To speed up the multiplication, the parameters and are chosen such that many coefficients are zero. For this, a parameter is selected and in the selection of coefficients, and equal to 1, coefficients equal to -1, and the remainder is equal to 0 are set.

The testing of multiple signatures can be sped up by instead of the individual standards checks the norm of the sum of the signatures. The parameter needs to be increased to.

Security

The signatures generated by the method reveal information about the secret key. This fact was exploited in 2006 to the attack method: Approximately 400 signatures were sufficient to compute the secret key. The method was adapted after the attack, perturbations should greatly complicate the calculation of the secret key. The improved method was assaulted in 2012, the secret key could be calculated from several thousand signatures.