NTRU

Definition (NTRU)

Since its introduction in 1998, several versions of NTRU have emerged in the literature.
NTRU is now recognized as a hard problem in cryptography rather than a unique cryptosystem that can be extended to different algebraic structures.
The NTRU design and the problem can be outlined as:

NTRU:
Let \(N\) be a prime, \(q\) be a positive integer, and \(f,g \in \mathbb{Z}[x]/\langle x^N-1\rangle\) be two polynomials with small coefficients (mostly ternary) such that \(f\) is invertible modulo \(q\).
The pair \((f,g)\) forms the secret key and

\[ h = f^{-1} \ast g \pmod{q} \in \mathbb{Z}_q[x]/\langle x^N-1\rangle \]

is the public key. The NTRU problem asks to find the private key or its rotations \((x^i \ast f, x^i \ast g)\).

---

The most renowned technique to attack the NTRU problem is to solve SVP in the \(2N\)-dimensional lattice \(\Lambda_{CS}\) generated by the basis

\[\begin{split} \mathcal{M}_{CS} = \begin{pmatrix} I_N & \mathcal{H} \\ 0_N & qI_N \end{pmatrix}, \end{split}\]

since the vector \((\mathbf{f}, \mathbf{g})\) associated with the private key \((f,g)\) or its rotations are the shortest vectors in the lattice \(\Lambda_{CS}\) with high probability.