NTRUEncrypt

NTRUEncrypt is an asymmetric encryption method that was developed in 1996 by mathematicians Jeffrey Hoffstein , Jill Pipher and Joseph H. Silverman . It is loosely based on lattice problems that are considered unbreakable even with quantum computers . However, NTRUEncrypt has so far not been as well researched as more common methods (e.g. RSA).

The algorithm is patented in the USA; the patents will expire in 2021. NTRUEncrypt is standardized by IEEE P1363.1. It is used z. B. from the US companies WiKID, Echosat and yaSSL.

Description of the procedure

Only the core algorithm is described below. Taken alone, this is susceptible to certain attacks; see the section Pre- and Post-Processing .

Unless otherwise stated, all calculations take place in the ring , i.e. H. the degree of the polynomial never exceeds . The multiplication “*” is a cyclic convolution modulo : The product of two polynomials and is . ${\displaystyle R=\mathbb {Z} _{q}[X]/(X^{N}-1)}$ ${\displaystyle N}$ ${\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}$

Key generation

1. Select the parameters with . ${\displaystyle N,p,q}$ ${\displaystyle q>p,\operatorname {ggT} (p,q)=1}$
2. Choosing a random polynomial whose coefficients are in {−1, 0, 1}. The inverses (the inverse modulo ) and (the inverse modulo ) must exist. ${\displaystyle f}$ ${\displaystyle f_{p}}$ ${\displaystyle p}$ ${\displaystyle f_{q}}$ ${\displaystyle q}$
3. Generation of a random polynomial whose coefficients are in {−1, 0, 1}. ${\displaystyle g}$
4. ${\displaystyle h\equiv f_{q}*g\mod q}$is the public key, the secret key. (For faster decryption, it can also be included in the secret key.) ${\displaystyle f}$ ${\displaystyle f_{p}}$

Encryption

1. Conversion of the plain text into a polynomial . ${\displaystyle m}$
2. Choosing a random polynomial with small coefficients. ${\displaystyle r}$
3. The polynomial is the ciphertext. ${\displaystyle e\equiv pr*h+m\mod q}$

Decryption

1. Calculation of with choice of the representatives of the coefficients of in the interval . ${\displaystyle a\equiv f*e\mod q}$ ${\displaystyle a}$ ${\displaystyle [-q/2,q/2)}$
2. Calculation of . ${\displaystyle c\equiv f_{p}*a\mod p}$
3. The plain text is obtained by converting the polynomial into the text representation. ${\displaystyle c}$

correctness

For polynomial applies: . Because the coefficients are all small, this equation also exists in the ring . Therefore, the calculation is correct in the second step . ${\displaystyle a}$ ${\displaystyle a\equiv f*e\equiv f*pr*h+f*m\mod q=f*pr*f_{q}*g+f*m\mod q=pr*g+f*m\mod q}$ ${\displaystyle R}$ ${\displaystyle c=f_{p}*pr*g+f_{p}*f*m\mod p=m\mod p}$

Efficiency

To speed up the multiplication, the polynomials and can be chosen so that many coefficients are zero. For this purpose, parameters are selected and in the selection of are coefficients equal to 1, coefficients equal to -1 and the rest set to 0. If you choose , coefficients are set equal to 1, coefficients equal to −1 and the remainder equal to 0 (Note: the number of ones must not be equal to the number of minus ones, otherwise the polynomial cannot be inverted). ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle d_{f},d_{g}}$ ${\displaystyle f}$ ${\displaystyle d_{f}}$ ${\displaystyle d_{f}-1}$ ${\displaystyle g}$ ${\displaystyle d_{g}}$ ${\displaystyle d_{g}-1}$

Decrypting becomes more efficient when the polynomial according to the formula with forms. Since then applies, the calculation of the inverse modulo is omitted . When choosing parameters, however, it is important to ensure that the desired level of security is maintained, since an attacker can now search through the set of . ${\displaystyle f}$ ${\displaystyle f=1+p\cdot f_{1}}$ ${\displaystyle f_{1}\in \mathbb {Z} _{p}[X]}$ ${\displaystyle f_{p}^{-1}=1}$ ${\displaystyle p}$ ${\displaystyle f_{1}}$

Furthermore, to speed up the multiplication, the polynomial can be formed according to the formula , where , and can be very sparsely populated. The three parameters , and , then take the place of the parameter . The increase in efficiency results from the fact that applies ( but still has enough coefficients other than zero) and can therefore be multiplied by faster than by . ${\displaystyle f}$ ${\displaystyle f(x)=1+p(f_{1}(x)*f_{2}(x)+f_{3}(x)}$ ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{3}}$ ${\displaystyle d_{f}}$ ${\displaystyle d_{f1}}$ ${\displaystyle d_{f2}}$ ${\displaystyle d_{f3}}$ ${\displaystyle d_{f1}+d_{f2}+d_{f3}<d_{f}}$ ${\displaystyle f_{1}*f_{2}+f_{3}}$ ${\displaystyle f_{1}*f_{2}+f_{3}}$ ${\displaystyle f}$

Finally, instead of a prime number, a polynomial can be chosen, whereby the most favorable choice is. This variant only appears in older literature. ${\displaystyle p}$ ${\displaystyle p(x)=x+2}$

safety

There is no formal proof of security for NTRUEncrypt as there is for other cryptographic methods, but the method is considered to be secure for sufficiently large parameters. At the beginning of 2011 a work by the cryptologists Damien Stehlé and Ron Steinfeld appeared, in which a security proof for a modified form of NTRUEncrypt is provided.

Various attacks on NTRUEncrypt are possible. The simplest of these is to try out all the polynomials that come into question for the parameters and . A more effective attack is the half attack ( meet-in-the-middle attack ), in which instead of one polynomial of the full length, two polynomials with only coefficients are tried out at the same time. As a result, this attack only needs the square root of the number of steps involved in primitive trial and error. A grid reduction is even more effective , e.g. B. by means of the LLL algorithm . ${\displaystyle f}$ ${\displaystyle N}$ ${\displaystyle d_{f}}$ ${\displaystyle N}$ ${\displaystyle N/2}$

Pre- and post-processing

The NTRUEncrypt core algorithm does not offer any security against attackers who manipulate the data after encryption. This can be remedied with a special padding , which the recipient can use to recognize manipulated ciphers.

Three such methods are known. SVES-1 and SVES-2 are older and vulnerable to attacks that exploit decryption errors. SVES-3 eliminates these weaknesses and is described in the P1363.1 standard under the designation SVES.

256 bit security level parameters

Originally, values ​​between 167 and 503 were recommended for the length , but the recommendations were adjusted accordingly after various attacks became known. The following parameters meet all currently known (as of 9/2011) attacks: ${\displaystyle N}$

	designation	N	p	q	d f	d g
Smallest key length	EES1087EP2	1087	3	2048	120	362
Medium key length, medium duration	EES1171EP1	1171	3	2048	106	390
Shortest closing and closing time	EES1499EP1	1499	3	2048	79	499

See also

• Post-quantum cryptography

Web links

• Description of the algorithm and recommended parameters (registration required)
• Description of the algorithm (accessible without registration) (PDF file; 315 kB)
• NTRUEncrypt as Java source code
• An NTRUEncrypt implementation from TU Darmstadt is available via SVN with the command svn co --username guest --password guest https://svn.cdc.informatik.tu-darmstadt.de/svn/repos/flexiprovider (The NTRU code is located in the directory flexiprovider / trunk / FlexiProvider / src / de / flexiprovider / pqc / ntru /).

Individual evidence

1. ↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring Based Public Key Cryptosystem ( 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. . In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, JP Buhler (Ed.), Lecture Notes in Computer Science 1423, Springer-Verlag Berlin, 1998, 267-288. 
2. ↑ Patent US7031468 : Speed ​​enhanced cryptographic method and apparatus. Filed August 24, 2001 , published April 18, 2006 , assignee: NTRU Cryptosystems, Inc., inventors: Jeffrey Hoffstein, Joseph H. Silverman. (Expiry of the 20-year period on 24 August 2021)
3. ↑ WiKID authentication devices ( Memento of the original dated December 14, 2011 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. . 
4. ↑ Article about NTRU in Networkworld from April 20, 2011  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. .  
5. ↑ CyaSSL Embedded SSL Library .
6. ↑ ^{a b c} Hoffstein u. Silverman: Optimizations for NTRU .
7. ↑ Damien Stehlé and Ron Steinfeld: Making NTRU as Secure as worst-case problem over ideal lattices . ( ens-lyon.fr [PDF]).
8. ↑ The impact of decryption failures on the security of NTRU encryption .
9. ↑ IEEE P1363.1 ( Memento of the original from June 29, 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. ( PDF ( Memento of the original from December 30, 2016 in the Internet Archive ) Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this note. Of a draft)