# 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} ${\ 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