Fine-grained deterministic hardness of the shortest vector problem
Authors
Markus Hittmeir
Abstract
Let $γ$-$\mathsf{GapSVP}_p$ be the decision version of the shortest vector problem in the $\ell_p$-norm with approximation factor $γ$, let $n$ be the lattice dimension and $0<\varepsilon\leq 1$. We prove that the following statements hold for infinitely many values of $p$.
$(2-\varepsilon)$-$\mathsf{GapSVP}_p$ is not in $O\left(2^{O(p)}\cdot n^{O(1)}\right)$-time, unless $\text{P}=\text{NP}$.
$(2-\varepsilon)$-$\mathsf{GapSVP}_p$ is not in $O\left(2^{2^{o(p)}}\cdot 2^{o(n)}\right)$-time, unless the Strong Exponential Time Hypothesis is false.
The proofs are based on a Karp reduction from a variant of the subset-sum problem that imposes restrictions on vectors orthogonal to the vector of its weights. While more extensive hardness results for the shortest vector problem in all $\ell_p$-norms have already been established under randomized reductions, the results in this paper are fully deterministic.
