2021/09/09 by Bennett, Huck, Peikert, Chris, Tang, Yi · 1 citation
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2109.04025
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 (SVPp,γ), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show: 1. For all p ∈ [1, ∞), there is no 2o(n)-time algorithm for BDDp, α for any constant α> αkn, where αkn = 2-ckn and ckn is the ℓ2 kissing-number constant, assuming ckn > 0 and that non-uniform Gap-ETH holds. 2. For all p ∈ [1, ∞), there is no 2o(n)-time algorithm for BDDp, α for any constant α> α^\ddaggerp, where α^\ddaggerp is explicit and satisfies α^\ddaggerp = 1 for 1 ≤ p ≤ 2, α^\ddaggerp < 1 for all p > 2, and α^\ddaggerp → 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, ∞), assuming ckn > 0 and that non-uniform Gap-SETH holds. 4. For all p > p0 ≈ 2.1397, p ∉ 2ℤ, and all C > Cp, there is no 2n/C-time algorithm for SVPp, γ for some constant γ> 1, where Cp > 1 is explicit and satisfies Cp → 1 as p → ∞, unless randomized Gap-SETH is false.