NTRUSign

NTRUSign is a digital signature process that was developed in 2003. It is based on the Goldreich-Goldwasser-Halewi signature procedure and is the successor to the insecure NSS procedure, but is also considered insecure.

Description of the procedure

As in NTRUEncrypt , NTRUSign also performs the calculations (with the exception of division by the resultant) in the ring , whereby the multiplication “*” is a cyclic convolution modulo : The product of two polynomials and is . ${\displaystyle R=\mathbb {Z} _{q}[X]/(X^{N}-1)}$ ${\displaystyle q}$ ${\displaystyle f=[f_{0},f_{1},\ldots ,f_{N-1}]}$ ${\displaystyle g=[g_{0},g_{1},\ldots ,g_{N-1}]}$ ${\displaystyle f*g=\sum _{i+j\equiv k\mod N}f_{i}\cdot g_{j}\mod q}$

With NTRUSign, either the standard or the transposed grid can be used. The transposed grid has the advantage that the polynomial only contains coefficients in {-1, 0, 1} and can therefore be multiplied more quickly. ${\displaystyle f'}$

Furthermore, the parameter , the number of so-called perturbations, can be selected. However, it has been found that 0 perturbations are unsafe and more than one is not necessary, so in practice it is always 1. ${\displaystyle B}$ ${\displaystyle B}$

In addition, the variables (number of polynomial coefficients), (modulus), (number of coefficients = −1), (standard correction factor) and (standard limit) are important. ${\displaystyle N}$ ${\displaystyle q}$ ${\displaystyle d}$ ${\displaystyle \beta }$ ${\displaystyle {\mathcal {N}}}$

Key generation

Are generated so-called bases. Each of them consists of three polynomials with and be called. The polynomial of the first base forms the public key, all other polynomials of all bases together form the private key. ${\displaystyle B}$ ${\displaystyle f,f'}$ ${\displaystyle h}$ ${\displaystyle h}$

Base generation

The variant according to Hoffstein et al. described. In EESS standard inversion of polynomials place and not in , but in place. As a result, you can get by without a point number and get “better” (standard smaller) polynomials F and G, but you also have to perform a complex resultant calculation. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {Z} }$

To generate a base , proceed as follows: ${\displaystyle (f,f',h)}$

1. Choosing a random polynomial whose coefficients are in {-1, 0, 1} and which is modulo invertible. ${\displaystyle f}$ ${\displaystyle q}$
2. Choosing a random polynomial whose coefficients are in {-1, 0, 1} and which is modulo invertible. ${\displaystyle g}$ ${\displaystyle q}$
3. Calculate the resultant of and a polynomial such that holds for any polynomial . This step is the most computationally intensive. This can be mitigated by calculating the resultant modulo for several prime numbers and reconstructing the total resultant from the moduli. For details of the resultant calculation, see Sections 2.2.7.1 and 2.2.7.2 of the EESS standard. ${\displaystyle R_{f}}$ ${\displaystyle f}$ ${\displaystyle \rho _{f}}$ ${\displaystyle \rho _{f}*f+\tau _{f}*(x^{n}-1)=R_{f}}$ ${\displaystyle \tau _{f}}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$
4. Calculate the resultant of and a polynomial such that holds for any polynomial . ${\displaystyle R_{g}}$ ${\displaystyle g}$ ${\displaystyle \rho _{g}}$ ${\displaystyle \rho _{g}*g+\tau _{g}*(x^{n}-1)=R_{g}}$ ${\displaystyle \tau _{g}}$
5. If ≠ is 1, start over from step 1. ${\displaystyle GGT(R_{f},R_{g})}$
6. Using the extended Euclidean algorithm, determine two numbers and so that . ${\displaystyle S_{f}}$ ${\displaystyle S_{g}}$ ${\displaystyle S_{f}R_{f}+S_{g}R_{g}=1}$
7. ${\displaystyle A(x)=qS_{f}\rho _{f}(x)}$and put. ${\displaystyle B(x)=-qS_{g}\rho _{g}(x)}$
8. Calculate inverse and in to a sufficient number of decimal places. ${\displaystyle f^{-1}(x)=\rho _{f}(x)/R_{f}}$ ${\displaystyle g^{-1}(x)=\rho _{g}(x)/R_{g}}$ ${\displaystyle \mathbb {R} [x]/(x^{N}-1)}$
9. ${\displaystyle C(x)=\lfloor 1/2(B(x)*f^{-}1(x)+A(x)*g^{-}1(x))\rceil }$. Note: and are Gaussian brackets . ${\displaystyle \lfloor }$ ${\displaystyle \rceil }$
10. ${\displaystyle F(x)=B(x)-C(x)*f(x)}$and . ${\displaystyle G(x)=A(x)-C(x)*g(x)}$
11. ${\displaystyle f_{q}}$= the inverse of modulo . ${\displaystyle f}$ ${\displaystyle q}$
12. In the standard case: and ${\displaystyle f'=F}$ ${\displaystyle h=g*f_{q}\mod q}$
13. In the transposed case: and ${\displaystyle f'=g}$ ${\displaystyle h=F*f_{q}\mod q}$

signing

Let m be the message to be signed.

For to 0 the following steps are carried out: ${\displaystyle i=B}$

1. ${\displaystyle (f,f',h)}$= -th base ${\displaystyle i}$
2. ${\displaystyle x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil }$
3. ${\displaystyle y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil }$
4. ${\displaystyle s_{i}=x*f+y*f'}$
5. ${\displaystyle m_{i}=si*(h_{i}-h_{i-1})\mod q}$
6. ${\displaystyle s=s+s_{i}}$

${\displaystyle s}$ is the signature.

Note: Under certain circumstances it can happen that the signature is invalid despite a valid key. It is therefore advisable to check the signature after creation and, if necessary, to sign it again.

Signature verification

Be the message, the public key and the signature. The norm of a polynomial is given by, where is (the latter is called the centered Euclidean norm ). ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle s}$ ${\displaystyle ||t||}$ ${\displaystyle t}$ ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z}}$ ${\displaystyle ||r||_{z}=\sum _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N}}\sum _{i=0}^{N}r_{i}}$

The signature is then verified as follows:

1. ${\displaystyle b={\sqrt {||s||^{2}+\beta ^{2}||s*h-m||^{2}}}}$
2. The signature is valid if is. ${\displaystyle b<{\mathcal {N}}}$

Note: The calculation of the norm via the definition is inefficient. A better method is to add a constant to all polynomial coefficients so that the two coefficients with the greatest distance are equidistant from (each modulo ). The norm is then given by the centered Euclidean norm (see above) of the resulting polynomial. ${\displaystyle {\frac {q}{2}}}$ ${\displaystyle q}$

Efficiency

To speed up the multiplication, the parameters and can be chosen so that many coefficients are zero. To do this, a parameter is selected and when and are selected, coefficients equal to 1, coefficients equal to −1 and the remainder equal to 0. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle d}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle d}$ ${\displaystyle d-1}$

The checking of several signatures can be accelerated by checking the norm of the sum of the signatures instead of the individual norms. The parameters and must be increased for this. ${\displaystyle N}$ ${\displaystyle {\mathcal {N}}}$

safety

The signatures created with the process reveal information about the secret key. This fact was exploited in 2006 to attack the method: Around 400 signatures were sufficient to calculate the secret key. The procedure was adapted after this attack, perturbations should make calculating the secret key considerably more difficult. The improved method was attacked in 2012, the secret key could be calculated from several thousand signatures.

Individual evidence

1. ↑ Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte: NTRUSign: Digital Signatures Using the NTRU Lattice . ( securityinnovation.com [PDF]). NTRUSign: Digital Signatures Using the NTRU Lattice ( Memento of the original from January 30, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
2. ^ Hoffstein, Pipher, Silverman: An Introduction to mathematical Cryptography, Springer 2008, ISBN 978-0-387-77993-5
3. ↑ ^{a b} Archived copy ( memento of the original from March 16, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Efficient Embedded Security Standard 
4. ↑ Phong Q. Nguyen and Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures . In: EUROCRYPT 2006 (=  LNCS ). tape 4004 . Springer, 2006, p. 271–288 ( ens.fr [PDF]).
5. ↑ Léo Ducas and Phong Q. Nguyen: Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures . In: ASIACRYPT 2012 (=  LNCS ). tape 7658 . Springer, 2012, p. 433-450 ( ens.fr [PDF]). Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures ( Memento of the original dated September 3, 2014 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  

Web links

• http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf Description of the algorithm
• http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/NTRUSignParams-2005-08.pdf Additions, optimizations and derivation of parameters
• http://www.freepatentsonline.com/7308097.pdf US software patent on NTRUSign, expires after the 20-year period on December 6, 2022
• http://sourceforge.net/projects/ntru/ NTRUSign as Java source code