Fine-grained deterministic hardness of the shortest vector problem

Let $\gamma$-${\mathsf{G}\mathsf{a}\mathsf{p}\mathsf{S}\mathsf{V}\mathsf{P}}_p$ be the decision version of the shortest vector problem in the ${\mathrm{\ell }}_p$-norm with approximation factor $\gamma$, let $n$ be the lattice rank and $0<\epsilon \le 1$. We prove that there is no algorithm that solves $(2-\epsilon )$-${\mathsf{G}\mathsf{a}\mathsf{p}\mathsf{S}\mathsf{V}\mathsf{P}}_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{G}\mathsf{a}\mathsf{p}\mathsf{S}\mathsf{V}\mathsf{P}}_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{G}\mathsf{a}\mathsf{p}\mathsf{S}\mathsf{V}\mathsf{P}}_{\mathrm{\infty }}$.