NTRUEncrypt
NTRUEncrypt is an asymmetric encryption method, which was developed in 1996 by mathematicians Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. It is loosely based on lattice problems, which are applicable to quantum computers as not crackable. However NTRUEncrypt has not as well studied, such as more conventional methods (e.g. RSA).
- 2.1 Pre and Post-
- 2.2 Parameter 256 bit security level
Description of the procedure
It is described in the following, only the core algorithm. This is, taken alone, vulnerable to certain attacks; see the section " Pre-and Post ".
Find all calculations, unless otherwise noted, in the ring instead, ie never exceeds the degree of the polynomial. Multiplication "*" is a cyclic convolution Modulus: The product of two polynomials and.
Key generation
Encoding
Decryption
Correctness
For the polynomial is considered. Because the coefficients are all small, this equation is also in the ring. Therefore, correctly calculated in the second step.
Efficiency
To speed up the multiplication, the polynomials and selected such that many coefficients are zero. These parameters are selected and the choice of coefficients equal to 1, coefficient equal to -1 and the rest equal to 0 are set. The choice of coefficients equal to 1, coefficient equal to -1 and the rest are set to 0 (note: The number of ones must not equal the number of minus ones be because otherwise the polynomial is not invertible ).
The decryption will be more efficient in making the polynomial according to the formula with. Since then applies, eliminates the calculation of the inverse modulo. However, it is to pay attention to the choice of parameters that the desired level of security is maintained since an attacker, the amount can search.
Finally, it can also be chosen as a polynomial instead of a prime number, which is the cheapest choice. This variant appeared but only in the older literature.
Security
There is no formal proof of security for NTRUEncrypt as for other cryptographic methods, yet the process for sufficiently large parameter is considered safe. Beginning of 2011 appeared a work of cryptographers Damien Stehlé and Ron Steinfeld, in a security proof of a modified form of NTRUEncrypt is performed.
There are several attacks on NTRUEncrypt possible. The simplest of these is to try all the polynomials that are eligible for the parameters and question. A more effective attack is the half attack (English meet-in - the-middle attack), in which instead of a polynomial of the full length of two polynomials are tried with only coefficients simultaneously. Thus, this attack requires only the square root of the number of steps that are executed when primitive through trial and error. Even more effective is a lattice reduction, eg by means of the LLL algorithm.
Pre-and post
The NTRUEncrypt - core algorithm provides no security against attackers who manipulate the data after encryption. Fixes this by the provision of the control data in the encryption by which the receiver can detect manipulated cipher texts.
There are known three such methods. PAC -1 and PAC -2 are older and from attempts to exploit the decryption error prone. PAC -3 addresses these weaknesses and is described in P1363.1 standard under the name PAC.
Parameters with 256-bit security level
Originally recommended for the length of values 167-503, after the announcement of several attacks but the recommendations have been adjusted accordingly. The following parameters are all currently known (as of 9/2011 ) attacks meet: