Editing NTRUEncrypt (section)

==Attacks==

Since the proposal of NTRU several attacks on the NTRUEncrypt public key cryptosystem have been introduced. Most attacks are focused on making a total break by finding the secret key '''f''' instead of just recovering the message '''m'''.
If '''f''' is known to have very few non-zero coefficients Eve can successfully mount a [[brute force attack]] by trying all values for '''f'''. When Eve wants to know whether '''f'''´ is the secret key, she simply calculates <math> \ \textbf{f}' \cdot \textbf{h} \pmod q </math>. If it has small coefficients it might be the secret key '''f''', and Eve can test if '''f'''´ is the secret key by using it to decrypt a message she encrypted herself.
Eve could also try values of '''g''' and test if  <math> \ \textbf{g}' \cdot \textbf{h}^{-1} \pmod q </math>has small values.

It is possible to mount a [[meet-in-the-middle attack]] which is more powerful. It can cut the search time by square root. The attack is based on the property that <math> \ \textbf{f} \cdot \textbf{h} = p\textbf{g} \pmod q </math>.

Eve wants to find 
<math> \ \textbf{f}_1 </math> and <math> \ \textbf{f}_2 </math> such that <math> \ \textbf{f} = \textbf{f}_1 + \textbf{f}_2 </math> holds and such that they have the  property 
:<math> \left( \textbf{f}_1+\textbf{f}_2 \right) \cdot \textbf{h} = \textbf{g} \pmod q </math>
:<math> \textbf{f}_1 \cdot \textbf{h} = \textbf{g} -\textbf{f}_2 \cdot \textbf{h} \pmod q</math>

If '''f''' has ''d'' one's and ''N''-''d'' zero's, then Eve creates all possible <math> \ \textbf{f}_1 </math> and <math> \ \textbf{f}_2 </math> in which they both have length <math> \ \frac{1}{2} N </math> (e.g. <math> \ \textbf{f}_1 </math> covers the <math> \ \frac{1}{2} N </math> lowest coefficients of '''f''' and <math> \ \textbf{f}_2 </math> the highest)
with ''d''/2 one's. Then she computes <math> \textbf{f}_1 \cdot \textbf{h} \pmod q </math> for all <math> \ \textbf{f}_1 </math> and orders them in bins based on the first k coordinates. After that she computes all <math> \ -\textbf{f}_2 \cdot \textbf{h} \pmod q </math> and orders them in bins not only based on the first k coordinates, but also based on what happens if you add 1 to the first k coordinates. Then you check the bins that contain both <math> \ \textbf{f}_1 </math> and <math> \ \textbf{f}_2 </math> and see if the property <math> \ \textbf{f}_1 \cdot \textbf{h} = \textbf{g} -\textbf{f}_2 \cdot \textbf{h} \pmod q </math> holds.

The lattice reduction attack is one of the best known and one of the most practical methods to break the NTRUEncrypt. In a way it can be compared to the factorization of the modulus in RSA. The most used algorithm for the lattice reduction attack is the [[Lenstra-Lenstra-Lovász lattice reduction algorithm|Lenstra-Lenstra-Lovász algorithm]].
Because the public key '''h''' contains both '''f''' and '''g''' one can try to obtain them from '''h'''. It is however too hard to find the secret key when the NTRUEncrypt parameters are chosen secure enough. The lattice reduction attack becomes harder if the dimension of the lattice gets bigger and the shortest vector gets longer.
 
The [[chosen ciphertext attack]] is also a method which recovers the secret key '''f''' and thereby results in a total break. In this attack Eve tries to obtain her own message from the ciphertext and thereby tries to obtain the secret key. In this attack Eve doesn't have any interaction with Bob.

'''How it works''':

First Eve creates a ciphertext <math> \ \textbf{e} = c\textbf{h} + c </math> such that <math> \ c = 0 \pmod p, c < \frac{q}{2} </math> and <math> \ 2c > \frac{q}{2} </math> 
When Eve writes down the steps to decipher e (without actually calculating the values since she does not know f) she finds <math> \ \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod q </math>:

:<math> \textbf{a} = \textbf{f} \left(c\textbf{h} + c\right) \pmod q </math>
:<math> \textbf{a} = c\textbf{g} +c\textbf{f} \pmod q </math>
:<math> \textbf{a} = c\textbf{g} + c\textbf{f} -qK </math>

In which <math> \ K = \sum k_i x^i </math>  such that
:<math>k_i=\begin{cases} 1 \ \ \qquad \text{if the} \ i^{th} \ \text{coefficient of} \ \textbf{f} \ \text{and} \ \textbf{g} \ \text{is} \ 1 \\ -1 \qquad \text{if the} \ i^{th} \ \text{coefficient of} \ \textbf{f} \ \text{and} \ \textbf{g} \ \text{is} \ -1\\ 0 \ \ \qquad \text{Otherwise}\end{cases}</math>

'''Example''':
:<math> \textbf{f} = -1+X+X^2-X^4+X^6+X^9-X^{10} </math>
:<math> \textbf{g} = -1 +X^2+X^3+X^5-X^8-X^{10} </math>

Then ''K'' becomes <math> \ K = -1+X^2-X^{10} </math>.

Reducing the coefficients of '''a''' mod ''p'' really reduces the coefficients of <math> \ c\textbf{g}+c\textbf{f}-qK \pmod p </math>. After multiplication with <math> \ \textbf{f}_p </math>, Eve finds:
:<math> \textbf{m} = c\textbf{f}_p \cdot \textbf{g}+c\textbf{f}_p \cdot \textbf{f}-q\textbf{f}_p \cdot K \pmod p </math>
:<math> \textbf{m} = c\textbf{h}+c -q\textbf{f}_p \cdot K \pmod p </math>

Because c was chosen to be a multiple of ''p'', '''m''' can be written as
:<math> \textbf{m} = -q\textbf{f}_p \cdot K \pmod p </math>

Which means that <math> \ \textbf{f} = -qK \cdot \textbf{m}^{-1} \pmod p </math>.

Now if '''f''' and '''g''' have few coefficients which are the same at the same factors, ''K'' has few non zero coefficients and is thereby small. By trying different values of ''K'' the attacker can recover '''f'''.

By encrypting and decrypting a message according to the NTRUEncrypt the attacker can check whether the function '''f''' is the correct secret key or not.