论文标题
$ \ ell_p $ norms in lattices上有界距离解码的硬度
Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms
论文作者
论文摘要
$ \ newCommand {\ Z} {\ MathBb {z}}} \ newCommand {\ eps} {\ varepsilon} \ newcommand {\ cc} [1] \ newCommand {\ Quards} [1] {\ Mathrm {＃1}}} \ newCommand {\ bdd} {\ Quargess {bdd}} $有限的距离解码$ \ bdd_ {p，α} $是在目标点承诺在$ \ ell_ {p} $ norm中解码晶格的问题。 We prove that $\BDD_{p, α}$ is $\NP$-hard under randomized reductions where $α\to 1/2$ as $p \to \infty$ (and for $α=1/2$ when $p=\infty$), thereby showing the hardness of decoding for distances approaching the unique-decoding radius for large $p$.我们还显示了$ \ bdd_ {p，α} $的细粒硬度。例如，我们证明，对于[1，\ infty）\ setMinus 2 \ z $和常数$ c> 1，\ eps> 0 $，没有$ 2^{（1- \ eps）n/c} $ - $ \ bdd_ $ p，a $ p fors for n n n n n n n n n n n n N/C} $（p，1） \ infty $），假设有随机的强指数时间假设（SETH）。此外，从本质上讲，我们的所有结果（在类似的非均匀假设下）以及预处理的$ \ bdd $都可以得出，其中无限制的预录可以在目标可用之前应用于晶格。 与先前关于$ \ bdd_ {p，α} $硬度的工作相比，liu，lyubashevsky和micciancio（大约2008年），我们的结果提高了该问题的$α$的值，该问题已知$ \ np $ - hard as $ p> p> p> p> p> p_1 \ $ y 4.273 bd and forny of y 4.273 bd，并在第一个$ 4.273 $ hard fixed $ hard fixed $ hard an规范）。我们的减少依赖于$ \ ell_ {p} $ norms的特殊“本地密集”晶格的特殊系列，我们通过修改Aggarwal和Stephens-Davidowitz的整数静态稀疏技术来构建它（STOC 2018）。
$ \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 $α$ 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 $α\to 1/2$ as $p \to \infty$ (and for $α=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\Z$ and constants $C > 1, \eps > 0$, there is no $2^{(1-\eps)n/C}$-time algorithm for $\BDD_{p,α}$ for some constant $α$ (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 $α$ 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).
