Fine-grained deterministic hardness of the shortest vector problem

Abstract

Let ${\hat{I}}^3$-${\mathsf{GapSVP}}_p$ be the decision version of the shortest vector problem in the ${\ell }_p$-norm with approximation factor ${\hat{I}}^3$, let $n$ be the lattice rank and $0<\epsilon \le 1$. We prove that there is no algorithm that solves $(2-\epsilon )$-${\mathsf{GapSVP}}_p$ uniformly for all $p\in \mathbb{N}$ in time\[ 2^{2^{o(p)}}\cdot 2^{o(n)},\] unless the Exponential Time Hypothesis is false. The proof is based on a deterministic Karp reduction from a constrained variant of the subset-sum problem to ${\mathsf{GapSVP}}_p$ for fixed $p$. While most hardness results for the shortest vector problem in finite norms rely on randomized reductions, our method is entirely deterministic. As a consequence, we also obtain a deterministic Karp reduction from the standard subset-sum problem to $(2-\epsilon )$-${\mathsf{GapSVP}}_{\infty }$.

14 pages. v3: Reformulation of main results