(Gap/S)ETH Hardness of SVP

Abstract

We prove the following quantitative hardness results for the Shortest Vector Problem in the ${\ell }_p$ norm ($\SVP_p$), where $n$ is the rank of the input lattice. $\bullet$ For "almost all" $p>p_0\approx 2.1397$, there no $2^{n/C_p}$-time algorithm for $\SVP_p$ for some explicit constant $C_p>0$ unless the (randomized) Strong Exponential Time Hypothesis (SETH) is false. $\bullet$ For any $p>2$, there is no $2^{o(n)}$-time algorithm for $\SVP_p$ unless the (randomized) Gap-Exponential Time Hypothesis (Gap-ETH) is false. Furthermore, for each $p>2$, there exists a constant ${\gamma }_p>1$ such that the same result holds even for ${\gamma }_p$-approximate $\SVP_p$. $\bullet$ There is no $2^{o(n)}$-time algorithm for $\SVP_p$ for any $1\le p\le 2$ unless either (1) (non-uniform) Gap-ETH is false; or (2) there is no family of lattices with exponential kissing number in the ${\ell }_2$ norm. Furthermore, for each $1\le p\le 2$, there exists a constant ${\gamma }_p>1$ such that the same result holds even for ${\gamma }_p$-approximate $\SVP_p$.

References in corpus (2)

• Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
• (Gap/S)ETH Hardness of SVP

Cited by in corpus (2)

• (Gap/S)ETH Hardness of SVP
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ${\ell }_p$ norm