NP-hardness of SVP in Euclidean Space

van Emde Boas (1981) conjectured that computing a shortest non-zero vector of a lattice in an Euclidean space is NP-hard.

In this paper, we prove that this conjecture is true and hence de-randomize the classical randomness result of Ajtai (1998).

We follow the locally dense lattice de-randomizion program as formulated and systematically studied by Micciancio (1998-2014).

Our proof builds on the construction of Bennett-Peikert (2023) on locally dense lattices via Reed-Solomon codes, and depends crucially on the work of Deligne on the Weil conjectures for higher dimensional varieties over finite fields.