NTRUEncrypt cryptosystem of the future?

All modern asymmetric cryptography is currently based on two simple and understandable principles: faith and hope. The belief is that when the condition P ≠ NP is fulfilled, the cryptosystem is not cracked in polynomial time. The hope that a quantum computer is as far from us as the creation of Cassiopeia. So, these two principles are so unreliable and difficult to prove from a mathematical point of view, that the only way out of this situation is to acquire a hat like the one on the left. Alternative? She exists. A relatively young cryptosystem NTRUEncrypt, which may be able to defeat these two principles and quite possibly will become the prototype for all the asymmetric cryptography of the “post-quantum” era. Detailed analysis of this fastest asymmetric algorithm resistant to attacks using quantum computers

A brief description of the cryptosystem

So NTRU (Nth-degree TRUncated polynomial ring or simply Number Theorists aRe Us) was proposed in 1995. Unlike its eminent predecessors such as RSA or El Gamal, NTRU does not work on a residue ring modulo an integer N, but on a ring of polynomials of degree n-1, modulo x ⁿ -1. The addition of elements in such a group occurs as usual addition, and when multiplying, the element x ^{n is} reduced to 1, x ^{n + 1} to x, and so on. By multiplying two elements of the ring a (x) * b (x), we obtain the element c (x) = c ₀ + c ₁ x + ... + c _n-1 x ^n-1 , in which the coefficient c _{k is} calculated as follows:

This ring is called the ring of truncated polynomials. We denote it for convenience R. In the NTRU cryptosystem, all coefficients of polynomials are modulo integers p and q. For example, the polynomial 13 + 12x + 14x ² + 7x ³ mod 3 = 1-x ² + x ³ .

After this small prelude, we proceed directly to the description of the algorithm itself.
NTRU uses three constant parameters: N, p, q. The number N is the size of the polynomials chosen as keys. The numbers p and q need not be simple, but the GCD (p, q) must be equal to 1. It should be noted that the parameter p serves to determine the interval to which all coefficients of the polynomials used in the cryptosystem are required to belong. And more precisely, the message space L of the cryptosystem NTRU is defined as

Thus, if N = 11 and p = 3, then we can use in our cryptosystem only polynomials with coefficients {-1,0,1}. For example: -1 + x + x ³ -x ⁴ -x ⁵ + x ¹⁰
After selecting these three basic parameters, it will be necessary to select three more additional parameters, which are usually denoted by d _f , d _g , d. These three parameters are used to define a set of polynomials.
L _f = L (d _f , d _f -1), L _g = L (d _g , d _g ), L _r = L (d, d).
A small explanation: a record of the form L _f = L (d _f , d _f -1) means that L _f is a set of all possible polynomials of the ring R, which have exactly d _f units (1) and d _f -1 minus ones ( -1) all other coefficients are zero.
For example, the polynomial -1 + x + x ³ -x ⁴ + x ⁸ belongs to the set L (3,2) because it has 3 1 and 2 -1.
')
Now you can try to generate a pair of secret / public key. This is done as follows.

1. An arbitrary polynomial f (x) is chosen from the set L _f .
2. The polynomial g (x) is chosen from the set Lg.
3. The polynomials f _q (x) and f _p (x) are calculated such that f _p (x) * f (x) = 1 mod p and f _q (x) * f (x) = 1 mod q
4. The public key is defined as h (x) = f _q (x) * g (x) mod q
5. The secret key is a pair (f (x), f _p (x)).

We describe the encryption procedure in the NTRU cryptosystem:

1. Bob chooses message m and converts it into a polynomial M (x) ∈ L _m remind that the coefficients of the polynomials belonging to L _m lie in the interval
2. Bob chooses a so-called. “Blinding” the polynomial r (x) ∈L _r and using Alice’s public key computes C (x) = p * r (x) * h (x) + M (x) mod q. The polynomial c (x) and will be a ciphertext.

And the decryption procedure:

1. Having received C (x) from Bob, Alice uses her secret key to calculate At the same time, Alice carefully monitors that the coefficients of the obtained polynomial a (x) lie in the interval (–q / 2, q / 2]. Why this is done later.
2. Alice calculates
   the first term of the expression b (x) has a factor p and therefore b (x) = f (x) * M (x) mod p. However, this all happens only if, when calculating a (x), its coefficients were not greater than q, therefore, at the first stage of decryption, it is checked that all coefficients lie in the specified interval.
3. Calculating Alice recovers the original message M.

I personally consider the most interesting point in the entire encryption-decryption scheme is the moment of checking the coefficients of the resulting polynomial a (x) to the interval (-q / 2; q / 2). As I explained above, all the coefficients of the polynomial should not be greater than q in order not to violate divisibility by p of the left side of the sum. But why, then, do we check the interval (-q / 2; q / 2] and not (-q; q]. The point is this. Suppose q = 32. P = 3. As a result, modulo 32 turned out the number 18. Modulo 3 it will be zero, but 18 = -14 mod 32. And if we calculate -14 mod 3, we get an incorrect result. Accordingly, you should always know in advance at what interval the obtained coefficients will be. The NTRU developers claim that for the recommended parameters with a probability almost equal to 1, the coefficients will always be in the interval (-q / 2; q / 2], therefore when deciphering, Alice gives the conditionally obtained number 18 to -14.

A few words about the practical side of the issue

pros
So, what advantages and disadvantages can be seen from the transition to the NTRU now.
First, a great speed of work. Performing encryption / decryption operations requires O (n ² ) operations, unlike O (n ³ ) in the same RSA.
Secondly, it is small, but an increase in durability with virtually the same key length.

Minus
He is alone for now, but for paranoids it is very serious. The need to use only the recommended parameters. It was the same requirement that caused general discontent during the transition to elliptic curves and contributed to all sorts of suspicions about the presence of backdoors.

NTRU strength

Let {b ₁ , b ₂ , ..., b _n } be a linearly independent system of vectors. The lattice L is the set of integer linear combinations.

For example, the lattice generated by a pair of vectors b1 = (2,0) and b2 = (1,1) consists of all the vectors of the form or in other words view vectors such that
The frontal attack on the NTRU is based on the lattices and the search for the shortest vector in the lattice. To unlock the secret key f (x), an attacker can build a matrix

And generate from the rows of this matrix the lattice L. Since Alice's public key h (x) = g (x) * f ^-1 (x) this lattice will contain the vector t = (a * f (x), g (x)). Moreover, this vector is the shortest in the lattice L. Accordingly, finding such a vector will lead to finding the secret key f (x). The task of finding the shortest lattice vector is considered to be computationally difficult. The temporal estimate of NTRU hacking using the lattice method can be calculated using the formula T = 2 ^(0.4N-3.5) . For N = 251, this is about ^2,100 .

A few words about quantum computing. The fact is that with the advent of a quantum computer, it will be possible to implement Shor’s algorithm, which allows to solve the factorization problem, and the discrete logarithm for the company. Naturally, in the light of this, RSA, DSA, and other similar algorithms become useless. But differently, the situation is with the NTRU, because there is no quantum algorithm for solving the problem of the shortest lattice vector (although the search is actively conducted from the first half of the 90s), which means it is fully applicable in the “post-quantum” era.

Well, one more thing about persistence. The fact is that although NTRU, like RSA, does not guarantee stability in the case of proving the inequality P NP (this is explained by the fact that the task belongs to the NP class even if there is at least one difficultly solvable variant or, more simply, on the worst case While the remaining options can have an easy solution. Accordingly, no one can guarantee that even if P ≠ NP is proved, the attacker will not get an easier version of the task and the hacking will not be possible in polynomial time), some tasks based on lattices interconnection resistance was proved average and worst case. This gives hope that in the future the emergence of a cryptosystem similar to that of the NTRU guaranteeing polynomial stability is possible if the condition P ≠ NP is fulfilled. It is these two differences that make the NTRU so different from its predecessors.

Known System Vulnerabilities

Let's briefly go over the vulnerabilities of the system and consider the most successful attacks.
Brute force
When breaking with brute force, the main task of the enemy is to pick up Alice's secret key, i.e. polynomial f (x). The adversary knows that a polynomial f (x) of length N has d _f unit coefficients and (d _f -1) coefficients -1. Selection of such a polynomial will require checking options. For N = 251 and d _f = 50, this expression is 3 * 10 ¹⁰⁰ . Comparing this assessment with the assessment of the complexity of solving the problem of finding the shortest lattice vector, we can conclude that, as in the case of RSA, brute-force key is not the most successful attack against the NTRU.

Attack meeting in the middle
But Andrew Odlyzko (I will not undertake to write Russian transcription) suggested the option of an attack meeting in the middle, which requires the NTRU to successfully open the secret key. time and exactly the same space on the hard disk (r-integer not greater than N). As a matter of fact, attacks of this type are called a meeting in the middle because they allow exchanging the time required for memory calculations necessary for storing temporary data.
The attack proposed by Odlyzko is as follows.
The definition of the public key h = f _q * g mod q implies the equality g = h * f mod q.
In this case, the attacker presents f as the concatenation of two polynomials of length N / 2.
f (x) = f ₁ || f ₂ g = h * (f ₁ || f ₂ ) = f ₁ * h + f ₂ * h mod q. We know that the polynomial g consists of the coefficients {1,0, -1} for the case p = 3 or the coefficients {1, 0} for the case p = 2, i.e. in other words
f ₁ * h = {1,0} -f ₂ * h.
Based on this fact, an attacker can act according to the following algorithm (for the case p = 2):

1. The number k is chosen. And 2 ^k baskets are written in which suitable candidates f ₁ and f ₂ will be stored. An increase in the number k leads to a decrease in the algorithm time, but to an increase in the memory required for cracking.
2. The attacker enumerates all variants of the polynomial f ₁ whose length is equal to N / 2 and which contains d / 2 1ki. Such a search will require iterations.
3. Each attacking polynomial is placed in the basket as follows: f _{1 is} written into the basket with the number consisting of the most significant bits of the first k coefficients f ₁ * h mod q.
   For example: let N = 4, q = 8. Then the polynomial with coefficients {7,2,3,5} will be placed in the basket with the number {1,0,0,1}. A polynomial with coefficients {6,4,3,1}
   Add to cart {1,1,0,0}.
   
4. After that, the attacker begins to iterate over the variants of the polynomial f ₂ containing d / 2 1ki. This bust will also take iterations.
5. During the iteration of the polynomial f _{2, the} attacker writes the resulting polynomial not in one basket, but in a slightly different way: first, he writes f ₂ into the basket that corresponds to the high bits of the polynomial –f ₂ * h mod q, and secondly, adding for each coefficient from –f ₂ * h, the unit and getting a new version of the baskets writes a polynomial f ₂ and in them. So for example the polynomial –f ₂ * h mod q = {6,2,1,5} is written only in the basket {1,0,0,1} and the polynomial – f ₂ * h mod q = {7,2,3, 5} into baskets {1,0,0,1}, {1,0,1,1}, {0,0,0,1}, {0,0,1,1}.
6. If the basket in which the attacker writes the polynomial f ₂ already contains f _1, then the condition f ₁ * h = {1,0} -f ₂ * h mod q is satisfied for these polynomials. Therefore, they are considered good candidates for recovery f. The attacker calculates (f ₁ || f ₂ ) * h mod q and if the result is a polynomial with coefficients {0,1} which corresponds to the polynomial g, then the secret key f is found.

Thus, if the cryptosystem key space of the NTRU is , then the search for a key by the method of a meeting in the middle requires to sort through options.
So for NTRU with parameters N = 251, p = 2, d = 35, the key space has a size of ≈2,140, ​​and the attack in the middle of the meeting requires going through ≈2 ⁷⁰ options (using 2 ⁷⁰ memory). Those. in order to guarantee a 2 ^x durability level, it is necessary to select the NTRU cryptosystem parameters with 2 ^2x key space.

Attack with selected ciphertext
And finally, I want to talk about the most interesting and most dangerous attack from a practical point of view.
I remind you that when deciphering a message, Alice calculates the expression
.
I also remind you that all the coefficients of the obtained polynomial lie in the interval (-q / 2, q / 2]. This means that .
Those. a polynomial before modulo q corresponds to a polynomial after a modulo q. An attack with a selected ciphertext on the NTRU is to create a polynomial a (x) for which a (x) mod q a (x).
The attack is as follows:

1. The attacker creates a ciphertext C (x) = y * h (x) + y (where y is an integer and h (x) is Alice’s public key) and sends it to Alice.
2. When trying to decrypt a message, Alice calculates Because Since the polynomials g (x) and f (x) have coefficients {-1,0,1}, then the coefficients of a polynomial a belong to the set {0, y, -y, 2y, -2y}. It turns out that if the attacker chose y, such that y <q / 2 and 2y> q / 2, then when a (x) is minimized modulo q, only those elements of a (x) polynomial the coefficients of which are equal to ± 2y change.
3. Imagine now that the i-th coefficient a _i = 2y, then
   
   and then the final message after decryption takes the form
   .
   So if the attacker chooses y by dividing completely on p, then the result is a polynomial .
4. To calculate Alice’s secret key, all that remains is to calculate

Using this attack scheme, the enemy can restore the secret key with a probability of P = 0.13, or, roughly speaking, to recover the secret key, the attacker will need to send in total about 10 selected ciphertexts.

Protection against attack with ciphertext
In order to protect the NTRU from such an attack, it is recommended to use the NTRU in conjunction with the FORST supplement scheme.
When encrypting using the NTRU-FORST method, Bob, as in the usual NTRU scheme, calculates the plaintext polynomial m (x). Complementing the polynomial with a random set of k bits of R, Bob computes r (x) = H (m (x) || R), where H (x) is a cryptographically strong hash function.
Further, to obtain a ciphertext as in the usual NTRU scheme, Bob forms the polynomial c (x) = r (x) * h (x) + m (x) mod q.
Upon receiving the ciphertext, Alice recovers the message m (x), and calculates H (m (x) || R).
Then Alice calculates H (m (x) || R) * h (x) + m (x) mod q and compares the obtained value with c (x). If H (m (x) || R) * h (x) + m (x) mod q = c (x) then Alice accepts the message, otherwise rejects it.

Conclusion

Although the NTRU algorithm is patented, which reduces the interest of researchers to it, the lack of publications about serious vulnerabilities over the almost 15-year period of existence allows one to look at its further use with optimism. Moreover, even in the most pessimistic case for asymmetric cryptography, namely the invention of the quantum computer today, there is no reason for panic and the NTRU is a completely reliable version of the cryptosystem of the “post-quantum” era.

Bibliography

1. Stamp M., Low RM Applied cryptanalysis
2. Mariano Monteverde NTRU software implementation for constrained devices.
3. Phong Q. Nguyen and David Pointcheval Analysis and Improvements of NTRU Encryption Paddings
4. Nick Howgrave-Graham A hybrid attack against NTRU