Abstract
We show improved finegrained hardness of two key lattice problems in the ?_p norm: Bounded Distance Decoding to within an α factor of the minimum distance (BDD_{p, α}) and the (decisional) γapproximate Shortest Vector Problem (GapSVP_{p,γ}), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap(S)ETH). Specifically, we show:
1) For all p ∈ [1, ∞), there is no 2^{o(n)}time algorithm for BDD_{p, α} for any constant α > α_kn, where α_kn = 2^{c_kn} < 0.98491 and c_kn is the ?₂ kissingnumber constant, unless nonuniform GapETH is false.
2) For all p ∈ [1, ∞), there is no 2^{o(n)}time algorithm for BDD_{p, α} 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 GapETH is false.
3) For all p ∈ [1, ∞) ⧵ 2 ℤ and all C > 1, there is no 2^{n/C}time algorithm for BDD_{p, α} for any constant α > α^†_{p, C}, where α^†_{p, C} is explicit and satisfies α^†_{p, C} → 1 as C → ∞ for any fixed p ∈ [1, ∞), unless nonuniform GapSETH is false.
4) For all p > p₀ ≈ 2.1397, p ∉ 2ℤ, and all C > C_p, there is no 2^{n/C}time algorithm for GapSVP_{p, γ} for some constant γ > 1, where C_p > 1 is explicit and satisfies C_p → 1 as p → ∞, unless randomized GapSETH is false.
Our results for BDD_{p, α} improve and extend work by Aggarwal and StephensDavidowitz (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 BDD_{p, α} is known to be exponentially hard in the Euclidean norm (p = 2) to an explicit constant α < 1 for the first time under a generalpurpose 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 StephensDavidowitz (SODA, 2021), which showed an analogous result for the Closest Vector Problem.
BibTeX  Entry
@InProceedings{bennett_et_al:LIPIcs.ITCS.2022.19,
author = {Bennett, Huck and Peikert, Chris and Tang, Yi},
title = {{Improved Hardness of BDD and SVP Under Gap(S)ETH}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {19:119:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15615},
URN = {urn:nbn:de:0030drops156151},
doi = {10.4230/LIPIcs.ITCS.2022.19},
annote = {Keywords: lattices, latticebased cryptography, finegrained complexity, Bounded Distance Decoding, Shortest Vector Problem}
}
Keywords: 

lattices, latticebased cryptography, finegrained complexity, Bounded Distance Decoding, Shortest Vector Problem 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 