Abstract
We give a simple proof that the (approximate, decisional) Shortest Vector Problem is NPhard under a randomized reduction. Specifically, we show that for any p ≥ 1 and any constant γ < 2^{1/p}, the γapproximate problem in the ?_p norm (γGapSVP_p) is not in RP unless NP ⊆ 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 ReedSolomon 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 NPhardness results for GapSVP_p with p < ∞, our reduction uses randomness. Indeed, it is a notorious open problem to prove NPhardness 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 stateoftheart explicit ReedSolomon listdecoding lower bounds of Guruswami and Rudra (STOC 2005 and IEEE Transactions on Information Theory 2006).
As a related contribution of independent interest, we also give a polynomialtime algorithm for decoding ndimensional "Construction A ReedSolomon lattices" (with different parameters than those used in our hardness proof) to a distance within an O(√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 Transactions on Information Theory 2022), whose work we build on with a somewhat simpler construction and analysis.
BibTeX  Entry
@InProceedings{bennett_et_al:LIPIcs.APPROX/RANDOM.2023.37,
author = {Bennett, Huck and Peikert, Chris},
title = {{Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via ReedSolomon Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {37:137:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18862},
URN = {urn:nbn:de:0030drops188622},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.37},
annote = {Keywords: Lattices, Shortest Vector Problem, ReedSolomon codes, NPhardness, derandomization}
}
Keywords: 

Lattices, Shortest Vector Problem, ReedSolomon codes, NPhardness, derandomization 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 