论文标题
（近似）最短矢量问题的硬度：通过芦苇 - 固体代码的简单证明
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
论文作者
论文摘要
$ \ newCommand {\ np} {\ MathSf {np}} \ newCommand {\ gapsvp} {\ textrm {gapsvp}} $我们简单地证明了（大约是（近似）最短的矢量问题是$ \ np $ - $ \ np $ - hard the $ \ np $ - hard。具体来说，我们表明，对于任何$ p \ geq 1 $和任何常数$γ<2^{1/p} $，$ \ ell_p $ norm中的$γ$ - approximate问题（$ \ gapsvp_p $）不在$ \ mathsf {rp} $中，否则不在我们的证明是遵循Ajtai开创的方法（Stoc 1998），并由Micciancio加强（Focs 1998和Sicomp 2000），用于使用本地致密的晶格显示出$γ$ - $ \ gapsvp_p $的硬度。我们仅通过将“构造A”应用于具有合适参数的芦苇 - 固体代码，并通过最初在Craig lattices上下文中使用的基本参数证明其局部密度来构建此类晶格。 如所有已知的$ \ np $ -HARDNESS结果，$ \ gapsvp_p $带有$ p <\ infty $的结果，我们的还原使用了随机性。确实，通过确定性的减少证明$ \ np $ - hard是一个臭名昭著的开放问题。为此，我们还讨论了潜在的方向和相关的挑战，以使我们的减少减少。特别是，我们表明，我们局部密度构建的紧密确定性类似物将改善最先进的明确的芦苇 - 固体列表列表，但Guruswami和Rudra的下限（Stoc 2005和IEEETrans。Inf。trood。2006）。 作为独立兴趣的相关贡献，我们还提供了一种多项式时间算法，用于解码$ n $ n $维度的“构建a reed solomon lattices”（与我们硬度证明中使用的参数不同）到$ o（\ sqrt {\ log n}）$ MINKOWSKI的$（\ sqrt {\ log n}）内的距离内的距离。由于Mook和Peikert（IEEETrans。Inf。2022），该渐近与最著名的距离相匹配，该距离在Minkowski的界限附近解码，我们的工作以更简单的结构和分析为基础。
$\newcommand{\NP}{\mathsf{NP}}\newcommand{\GapSVP}{\textrm{GapSVP}}$We give a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP$-hard under a randomized reduction. Specifically, we show that for any $p \geq 1$ and any constant $γ< 2^{1/p}$, the $γ$-approximate problem in the $\ell_p$ norm ($γ$-$\GapSVP_p$) is not in $\mathsf{RP}$ unless $\NP \subseteq \mathsf{RP}$. Our proof follows an approach pioneered by Ajtai (STOC 1998), and strengthened by Micciancio (FOCS 1998 and SICOMP 2000), for showing hardness of $γ$-$\GapSVP_p$ using locally dense lattices. We construct such lattices simply by applying "Construction A" to Reed-Solomon codes with suitable parameters, and prove their local density via an elementary argument originally used in the context of Craig lattices. As in all known $\NP$-hardness results for $\GapSVP_p$ with $p < \infty$, our reduction uses randomness. Indeed, it is a notorious open problem to prove $\NP$-hardness via a deterministic reduction. To this end, we additionally discuss potential directions and associated challenges for derandomizing our reduction. In particular, we show that a close deterministic analogue of our local density construction would improve on the state-of-the-art explicit Reed-Solomon list-decoding lower bounds of Guruswami and Rudra (STOC 2005 and IEEE Trans. Inf. Theory 2006). As a related contribution of independent interest, we also give a polynomial-time algorithm for decoding $n$-dimensional "Construction A Reed-Solomon lattices" (with different parameters than those used in our hardness proof) to a distance within an $O(\sqrt{\log n})$ factor of Minkowski's bound. This asymptotically matches the best known distance for decoding near Minkowski's bound, due to Mook and Peikert (IEEE Trans. Inf. Theory 2022), whose work we build on with a somewhat simpler construction and analysis.
