Abstract
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 š_p norm. We prove that BDD_{p, Ī±} is NPhard under randomized reductions where Ī± ā 1/2 as p ā ā (and for Ī± = 1/2 when p = ā), thereby showing the hardness of decoding for distances approaching the uniquedecoding radius for large p. We also show finegrained hardness for BDD_{p,Ī±}. For example, we prove that for all p ā [1,ā) ā§µ 2ā¤ and constants C > 1, Īµ > 0, there is no 2^((1Īµ)n/C)time algorithm for BDD_{p,Ī±} for some constant Ī± (which approaches 1/2 as p ā ā), assuming the randomized Strong Exponential Time Hypothesis (SETH). Moreover, essentially all of our results also hold (under analogous nonuniform 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 (APPROXRANDOM 2008), our results improve the values of Ī± for which the problem is known to be NPhard for all p > pā ā 4.2773, and give the very first finegrained hardness for BDD (in any norm). Our reductions rely on a special family of "locally dense" lattices in š_p norms, which we construct by modifying the integerlattice sparsification technique of Aggarwal and StephensDavidowitz (STOC 2018).
BibTeX  Entry
@InProceedings{bennett_et_al:LIPIcs:2020:12588,
author = {Huck Bennett and Chris Peikert},
title = {{Hardness of Bounded Distance Decoding on Lattices in š_p Norms}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {36:136:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12588},
URN = {urn:nbn:de:0030drops125881},
doi = {10.4230/LIPIcs.CCC.2020.36},
annote = {Keywords: Lattices, Bounded Distance Decoding, NPhardness, FineGrained Complexity}
}
Keywords: 

Lattices, Bounded Distance Decoding, NPhardness, FineGrained Complexity 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 