Why we couldn’t prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar · 2023
Recent work has shown SETH hardness of CVP in the $\ell_{p}$ norm for any p that is not an even integer. This result was shown by giving a Karp reduction from k-SAT on n variables to CVP on a lattice of rank n. In this work, we show a barrier towards proving a similar result for CVP in the $\ell_{p}$ norm where p is an even integer. We show that for any $c\gt0$, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a CVP instance for a lattice of rank at most $n^{c}$ in the Euclidean norm, then coNP $\subset NP/Poly$. We prove a similar result for CVP for all even norms under a mild additional promise that the ratio of the distance of the target from the lattice and the shortest non-zero vector in the lattice is bounded by $\exp \left(n^{O(1)}\right)$. Furthermore, we show that for any $c\gt0$, and any even integer p, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a $SVP_{p}$ instance for a lattice of rank at most $n^{c}$, then coNP $\subset NP /$ Poly.1While prior results have indicated that lattice problems in the $\ell_{2}$ norm (Euclidean norm) are easier than lattice problems in other norms, this is the first result that shows a separation between these problems. We achieve this by using a result by Dell and van Melkebeek on the impossibility of the existence of a reduction that compresses an arbitrary k-SAT instance into a string of length $\mathcal{O}\left(n^{k-\varepsilon}\right)$ for any $\varepsilon\gt0$. In addition to CVP, we also show that the same result holds for the Subset-Sum problem using similar techniques.1The result for SVP does not require any additional promise.