Why we couldn’t prove SETH hardness of the Closest Vector Problem for even norms!

This is the authors' abstract. We don't add key points for this paper.

Recent work has shown SETH hardness of CVP in the ₚ 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 ₚ norm where p is an even integer. We show that for any c>0, if for every k>0, 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ᶜ in the Euclidean norm, then coNP ⊂ 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 (nO(1)). Furthermore, we show that for any c>0, and any even integer p, if for every k>0, there exists an efficient reduction that maps a k-SAT instance on n variables to a SVPₚ instance for a lattice of rank at most nᶜ, then coNP ⊂ NP / Poly.1 While prior results have indicated that lattice problems in the ₂ 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 O(nk-ε) for any ε>0. 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.