Significance of parameter q in NTRU lattice attack In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is much higher?
For example, N=127, q=256 will give me an unsuccessful lattice attack but N=127, q=2^16 will give me a successful lattice attack
Basically, the norm of the secret key does not depend on $q$, while the norm of the second minimum of the lattice does, so, when you increase $q$, you increase the gap between the first and the second minima of the lattice, which makes the problem easier.
For instance, if the secret key is composed by two degree-$(N-1)$ polynomials $f$ and $g$ with coefficients in $\{-1, 0, 1\}$, then we have $||(f, g)|| &lt; 2N$.
One basis of the lattice $L$ that we use in attack is
$$
\begin{pmatrix}
I_N &amp; H \\
0   &amp; q\cdot I_N
\end{pmatrix}
\in \mathbb{Z}^{2N\times 2N}
$$
So, it is clear that $\det(L) = q^N$ and $\dim(L) = 2N$.
Then, by the Gaussian Heuristic, we expect the short vectors of $L$ to have norm close to
$\sqrt{N}(\det(L))^{1/\dim(L)} = \sqrt{Nq}$.
Because $(f, g) \in L$ and $||(f, g)||$ is smaller than the value predicted by the Gaussian Heuristic, there is a &quot;gap&quot; in $L$, that is, we expect that
$\lambda_1(L) = ||(f, g)||$ and
$\lambda_2(L) \approx \sqrt{Nq}$.
Now, roughly speaking, if the vector that we recovered is shorter than the second shortest vector, then it has to be the first shortest vector.
So, when we run a lattice basis reduction, if we recover a vector smaller than
$\sqrt{Nq}$, it will already be (a short multiple of) $(f, g)$ and we win.