On the Quantitative Hardness of CVP

Abstract

For odd integers $p\ge 1$ (and $p=\infty$), we show that the Closest Vector Problem in the ${\ell }_p$ norm ($\CVP_p$) over rank $n$ lattices cannot be solved in $2^{(1-\eps) n}$ time for any constant $\eps > 0$ unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to "almost all" values of $p\ge 1$, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of $\CVP_2$ (i.e., $\CVP$ in the Euclidean norm), for which a $2^{n+o(n)}$-time algorithm is known. In particular, our result applies for any $p=p(n)\ne 2$ that approaches $2$ as $n\to \infty$. We also show a similar SETH-hardness result for $\SVP_\infty$; hardness of approximating $\CVP_p$ to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for $\CVP_p$ and $\CVPP_p$ for any $1\le p<\infty$ under different assumptions.