Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)|| < 2N$.
One basis of the lattice $L$ that we use in attack is $$ \begin{pmatrix} I_N & H \\ 0 & 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 "gap" 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.
