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

This is the authors' abstract. We don't add key points for this paper.

We show improved fine-grained hardness of two key lattice problems in the 𝓁_p norm: Bounded Distance Decoding to within an α factor of the minimum distance (BDDp, α) and the (decisional) γ-approximate Shortest Vector Problem (GapSVPp,γ), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show: 1) For all p ∈ [1, ∞), there is no 2ᵒ⁽ⁿ⁾-time algorithm for BDDp, α for any constant α > α_kn, where α_kn = 2-c_kn < 0.98491 and c_kn is the 𝓁₂ kissing-number constant, unless non-uniform Gap-ETH is false. 2) For all p ∈ [1, ∞), there is no 2ᵒ⁽ⁿ⁾-time algorithm for BDDp, α for any constant α > α^‡_p, where α^‡_p is explicit and satisfies α^‡_p = 1 for 1 ≤ p ≤ 2, α^‡_p < 1 for all p > 2, and α^‡_p → 1/2 as p → ∞, unless randomized Gap-ETH is false. 3) For all p ∈ [1, ∞) ⧵ 2 ℤ and all C > 1, there is no 2n/C-time algorithm for BDDp, α for any constant α > α^†p, C, where α^†p, C is explicit and satisfies α^†p, C → 1 as C → ∞ for any fixed p ∈ [1, ∞), unless non-uniform Gap-SETH is false. 4) For all p > p₀ ≈ 2.1397, p ∉ 2ℤ, and all C > C_p, there is no 2n/C-time algorithm for GapSVPp, γ for some constant γ > 1, where C_p > 1 is explicit and satisfies C_p → 1 as p → ∞, unless randomized Gap-SETH is false. Our results for BDDp, α improve and extend work by Aggarwal and Stephens-Davidowitz (STOC, 2018) and Bennett and Peikert (CCC, 2020). Specifically, the quantities α_kn and α^‡_p (respectively, α^†p,C) significantly improve upon the corresponding quantity α_p^* (respectively, αp,C^*) of Bennett and Peikert for small p (but arise from somewhat stronger assumptions). In particular, Item 1 improves the smallest value of α for which BDDp, α is known to be exponentially hard in the Euclidean norm (p = 2) to an explicit constant α < 1 for the first time under a general-purpose complexity assumption. Items 1 and 3 crucially use the recent breakthrough result of Vlăduţ (Moscow Journal of Combinatorics and Number Theory, 2019), which showed an explicit exponential lower bound on the lattice kissing number. Finally, Item 4 answers a natural question left open by Aggarwal, Bennett, Golovnev, and Stephens-Davidowitz (SODA, 2021), which showed an analogous result for the Closest Vector Problem.