SVP

• Unlike CVP, SVP is not known to be NP-complete! There are some hardness results for SVP, but just considering very specific scenarios (for instance, using the $\ell_\infty$ norm) or under other types of reductions (such as randomized or non-uniform reductions). Therefore it may be possible that solving SVP is easier than solving CVP! But even so, SVP is beleived to be NP-Hard.


• For any constant $\gamma \in [1,2[$ and any function $\alpha(n) > \sqrt{\frac{ n}{(2/\gamma)^2 - 1}}$, we can solve $CVP_\alpha$ with $O(n\log n)$ calls to an oracle that solves $SVP_\gamma$ [MC2002, theorem 4.2].

  Note, however, that it is not sufficient to show that $SVP_\gamma$ is NP-Hard because $CVP_\alpha$ is not known to be NP-Hard for such values of $\alpha$.



• If a specific number theoretic conjecture concerning the distribution of square free smooth numbers holds, then $\forall p \in \mathbb{N}^*$, $GapSVP_\gamma$ is NP-Hard if $\gamma < \sqrt[p]{2}$ [MC2002, Corollary 4.10].

References

• [MC2002] See chapter 3 of Complexity of Lattice Problems: A Cryptographic Perspective. By Daniele Micciancio and Shafi Goldwasser (2002)"