NTRU Lattice

Out of all the attacks proposed on NTRU, the lattice based attack is by far the best in present day literature.

NTRU Public Key

Let \(T(r_1,r_2) = \lbrace f \in \frac{\mathbb{Z}[X]}{<X^N-1>} \rbrace\) such that \(r_1\) coefficients in \(f\) are \(1\), \(r_2\) coefficients in \(f\) are \(-1\) and remaining coefficients in \(f\) are \(0\). The set \(T(r_1,r_2)\) is known as the set of ternary polynomials, as the coefficients of these polynomias only take \(3\) different values.
Now let \(d = \lfloor \frac{N}{3} \rfloor\). It is observed that with high probability, the elements of \(T(d,d)\) are invertible in \(\frac{\mathbb{Z}_q[X]}{<X^N-1>}\) and \(\frac{\mathbb{Z}_p[X]}{<X^N-1>}\).
Let \(f \in T(d,d)\) and \(g \in T(d+1,d)\).
Let \(h = f^{-1} * g\) (mod \(q\)).
The polynomial \(h\) is the public key.

Lattice construction from Public Key

Let \(h = f^{-1} * g\) (mod \(q\)) be a Public Key for NTRU cryptosystem.
Then, \(g = f*h\) (mod \(q\)) \(\Rightarrow g = f*h + q*u\), for some \(u \in \frac{\mathbb{Z}[X]}{<X^N-1>}\).
Also, \(f = 1*f + 0*u\).
Thus, consider the matrix equation,
\(\begin{bmatrix} f_0 & f_1 & \cdots & f_{N-1} & g_0 & g_1 & \cdots & g_{N-1} \end{bmatrix} = \)
\(\begin{bmatrix} f_0 & f_1 & \cdots & f_{N-1} & u_0 & u_1 & \cdots & u_{N-1} \end{bmatrix} * \begin{bmatrix} 1 & 0 & \cdots & 0 & h_0 & h_1 & \cdots & h_{N-1} \\ 0 & 1 & \cdots & 0 & h_{N-1} & h_0 & \cdots & h_{N-2} \\ \cdots \\ 0 & 0 & \cdots & 1 & h_1 & h_2 & \cdots & h_0 \\ 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0 \\ \cdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q \\ \end{bmatrix}\).
This equation represents the matrix form of the Public Key equations. In a more compact form one can write,
\(\begin{bmatrix} f & g \end{bmatrix} = \begin{bmatrix} f & u \end{bmatrix} * L\),
where \(L = \begin{bmatrix} I_N & H \\ 0_N & qI_N \end{bmatrix}\) is a matrix of dimension \(2N \times 2N\),
\(I_N\) is the identity matrix of dimension \(N \times N\) and
\(0_N\) is the null matrix of dimension \(N \times N\) and
\(H = \begin{bmatrix} h_0 & h_1 & \cdots & h_{N-1} \\ h_{N-1} & h_0 & \cdots & h_{N-2} \\ \cdots \\ h_1 & h_2 & \cdots & h_0 \\ \end{bmatrix}\)

Now, note that \(\begin{bmatrix} f & g \end{bmatrix}\) is a short vector in \(L\).
Thus, finding \(f\) and \(g\) from \(h\) is equivalent to finding short vector in \(L\).