3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.