Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ${\ell }_p$ norms for $p>2$

Abstract

We establish deterministic hardness of approximation results for the Shortest Vector Problem in ${\ell }_p$ norm (${\mathsf{SVP}}_p$) and for Unique-SVP (${\mathsf{uSVP}}_p$) for all $p>2$. Previously, no deterministic hardness results were known, except for ${\ell }_{\infty }$. For every $p>2$, we prove constant-ratio hardness: no polynomial-time algorithm approximates ${\mathsf{SVP}}_p$ or ${\mathsf{uSVP}}_p$ within a ratio of $\sqrt{2}-o(1)$, assuming $\text{3SAT}\notin \text{DTIME}(2^{O(n^{2/3}\log n)})$, and, $\text{Unambiguous-3SAT}\notin \text{DTIME}(2^{O(n^{2/3}\log n)})$. We also show that for any $\epsilon >0$ there exists $p_{\epsilon }>2$ such that for every $p\ge p_{\epsilon }$: no polynomial-time algorithm approximates ${\mathsf{SVP}}_p$ within a ratio of $2^{(\log n{)}^{1-\epsilon }}$, assuming $\text{NP}⊈\text{DTIME}(n^{(\log n{)}^{\epsilon }})$; and within a ratio of $n^{1/(\log \log (n){)}^{\epsilon }}$, assuming $\text{NP}⊈\text{SUBEXP}$. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for ${\mathsf{uSVP}}_p$ under the assumptions $\text{Unambiguous-3SAT}⊈\text{DTIME}(n^{(\log n{)}^{\epsilon }})$ and $\text{Unambiguous-3SAT}⊈\text{SUBEXP}$, improving the previously known $1+o(1)$ [Stephens-Davidowitz, Approx 2016]. Strengthening the hardness of $\text{uSVP}$ has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for $\gamma$-${\mathsf{uSVP}}_p$ carries over to $\frac{1}{\gamma }$-${\mathsf{BDD}}_p$ (Bounded Distance Decoding). Thus, understanding the hardness of $\text{uSVP}$ improves worst-case guarantees for two core problems that underpin security in lattice-based cryptography.