Hardness of Bounded Distance Decoding on Lattices in ${\ell }_p$ Norms

Abstract

$ \newcommand{\Z}{\mathbb{Z}} \newcommand{\eps}{\varepsilon} \newcommand{\cc}[1]{\mathsf{#1}} \newcommand{\NP}{\cc{NP}} \newcommand{\problem}[1]{\mathrm{#1}} \newcommand{\BDD}{\problem{BDD}} $Bounded Distance Decoding $\BDD_{p,α}$ is the problem of decoding a lattice when the target point is promised to be within an $\hat{I}\pm$ factor of the minimum distance of the lattice, in the ${\ell }_p$ norm. We prove that $\BDD_{p, α}$ is $\NP$-hard under randomized reductions where $\hat{I}\pm \to 1/2$ as $p\to \infty$ (and for $\hat{I}\pm =1/2$ when $p=\infty$), thereby showing the hardness of decoding for distances approaching the unique-decoding radius for large $p$. We also show fine-grained hardness for $\BDD_{p,α}$. For example, we prove that for all $p\in [1,\infty )\setminus 2\mathbb{Z}$ and constants $C > 1, \eps > 0$, there is no $2^{(1-\eps)n/C}$-time algorithm for $\BDD_{p,α}$ for some constant $\hat{I}\pm$ (which approaches $1/2$ as $p\to \infty$), assuming the randomized Strong Exponential Time Hypothesis (SETH). Moreover, essentially all of our results also hold (under analogous non-uniform assumptions) for $\BDD$ with preprocessing, in which unbounded precomputation can be applied to the lattice before the target is available. Compared to prior work on the hardness of $\BDD_{p,α}$ by Liu, Lyubashevsky, and Micciancio (APPROX-RANDOM 2008), our results improve the values of $\hat{I}\pm$ for which the problem is known to be $\NP$-hard for all $p>p_1\approx 4.2773$, and give the very first fine-grained hardness for $\BDD$ (in any norm). Our reductions rely on a special family of "locally dense" lattices in ${\ell }_p$ norms, which we construct by modifying the integer-lattice sparsification technique of Aggarwal and Stephens-Davidowitz (STOC 2018).