Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

Question

It was shown in

P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice

that the construction of a shortest nonzero vector of a Euclidean lattice w.r.t. the $L^{\infty}$-norm is NP-hard.

But for the $L^2$ norm, is this question still open? Can anyone explain the difficulty and progress in this problem?

Answer 1

The NP-hardness of the shortest vector problem in $L_2$ norm is discussed in this 2015 lecture by Vinod Vaikuntanathan. An algorithm for this problem would give a randomised algorithm for any problem in NP.

The original reference is The Shortest Vector Problem in $L_2$ is NP-hard for Randomized Reductions by Miklós Ajtai.

The problem remains NP-hard if the shortest vector must only be found within any constant factor (a result by Subhash Khot).

This table from the lecture notes summarizes the situation. SVP$_\gamma$ is the shortest vector problem within a factor $\gamma$, the $\ast$ refers to the randomized reduction, and "quasi" refers to super-polynomial (though still sub-exponential) scaling.

Answer 2

Just adding some brief clarification to Carlo's answer.

The randomness in the randomized constructions is used solely to randomly produce a lattice that satisfies certain properties. In particular, one solely needs to produce a "Locally Dense Lattice" (see section 4 of Locally Dense Codes by Micciancio). Briefly, for any lattice $L$, if $\lambda_1(L)$ is the length of the shortest vector, then any ball of radius $\lambda_1(L)/2$ contains at most a single lattice point. A locally dense lattice is a lattice $L$ such that there exists some center $c$ such that the ball of radius $\approx\lambda_1(L)$ centered at $c$ contains exponentially many lattice points.

The reduction alluded to in Carlo's answer is almost deterministic in the following sense. An explicit lattice $L$ is known to be locally dense, but an explicit center $c$ is not known. One could either

• randomly pick the center (which works with high probability). This leads to the randomized NP hardness reduction mentioned, or
• deterministically pick the center (if a certain number-theoretic conjecture holds).

The conjecture is as follows.

For all $\epsilon>0$ and (large enough) $n$, the interval $[n, n + n^\epsilon]$ contains a square-free number with prime factors $< \log^{O(1)} n.$

Explicitly, if this conjecture is true, $\mathsf{SVP}_2$ is already known to be $\mathsf{NP}$-hard. It may be easier to find some other locally dense lattice though.

For some (informal) summary of this matter, Micciancio has some slides from last year that are probably useful.