Improved Hardness of BDD and SVP Under Gap-(S)ETH

Abstract

We show improved fine-grained hardness of two key lattice problems in the ${\ell }_p$ norm: Bounded Distance Decoding to within an $\hat{I}\pm$ factor of the minimum distance (${\mathrm{BDD}}_{p,\hat{I}\pm }$) and the (decisional) ${\hat{I}}^3$-approximate Shortest Vector Problem (${\mathrm{SVP}}_{p,{\hat{I}}^3}$), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show: 1. For all $p\in [1,\infty )$, there is no $2^{o(n)}$-time algorithm for ${\mathrm{BDD}}_{p,\hat{I}\pm }$ for any constant $\hat{I}\pm >\hat{I}{\pm }_{\mathsf{kn}}$, where $\hat{I}{\pm }_{\mathsf{kn}}=2^{-c_{\mathsf{kn}}}$ and $c_{\mathsf{kn}}$ is the ${\ell }_2$ kissing-number constant, assuming $c_{\mathsf{kn}}>0$ and that non-uniform Gap-ETH holds. 2. For all $p\in [1,\infty )$, there is no $2^{o(n)}$-time algorithm for ${\mathrm{BDD}}_{p,\hat{I}\pm }$ for any constant $\hat{I}\pm >\hat{I}{\pm }_p^{‡}$, where $\hat{I}{\pm }_p^{‡}$ is explicit and satisfies $\hat{I}{\pm }_p^{‡}=1$ for $1\le p\le 2$, $\hat{I}{\pm }_p^{‡}<1$ for all $p>2$, and $\hat{I}{\pm }_p^{‡}\to 1/2$ as $p\to \infty$, unless randomized Gap-ETH is false. 3. For all $p\in [1,\infty )\setminus 2\mathbb{Z}$ and all $C>1$, there is no $2^{n/C}$-time algorithm for ${\mathrm{BDD}}_{p,\hat{I}\pm }$ for any constant $\hat{I}\pm >\hat{I}{\pm }_{p,C}^{†}$, where $\hat{I}{\pm }_{p,C}^{†}$ is explicit and satisfies $\hat{I}{\pm }_{p,C}^{†}\to 1$ as $C\to \infty$ for any fixed $p\in [1,\infty )$, assuming $c_{\mathsf{kn}}>0$ and that non-uniform Gap-SETH holds. 4. For all $p>p_0\approx 2.1397$, $p\notin 2\mathbb{Z}$, and all $C>C_p$, there is no $2^{n/C}$-time algorithm for ${\mathrm{SVP}}_{p,{\hat{I}}^3}$ for some constant ${\hat{I}}^3>1$, where $C_p>1$ is explicit and satisfies $C_p\to 1$ as $p\to \infty$, unless randomized Gap-SETH is false.

ITCS 2022. Updated to address (non-)existence of exponential kissing number lattices