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

Recent work [BGS17,ABGS19] has shown SETH hardness of CVP in the ℓ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 ℓp 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 nc in the Euclidean norm, then mathsfcoNP subset mathsfNP/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 SVPp instance for a lattice of rank at most nc, then mathsfcoNP subset mathsfNP/Poly. The result for SVP does not require any additional promise. While prior results have indicated that lattice problems in the ℓ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 [JACM, 2014] 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.