NP-hardness of SVP in Euclidean Space

In 1981, van Emde Boas conjectured that computing a shortest non-zero vector of a lattice in a Euclidean space is $\mathbf{N}\mathbf{P}$-hard. In this paper, we prove this conjecture, thereby derandomizing Ajtai’s classical randomized hardness result (1998). We follow the derandomization program formulated by Micciancio (1998–2014) who conjectured the existence of an efficient deterministic construction of locally dense lattices. The key is to resolve this conjecture. Our proof builds on the candidate construction via Reed-Solomon codes by Bennett and Peikert (2023), and depends crucially on Deligne’s work on the Weil conjectures for higher-dimensional varieties over finite fields.