Unconditional deterministic NP-hardness of Euclidean (ℓ₂) shortest vector problem, and at polynomial factors

Randomised hardness. Ajtai (STOC 1998) proved SVP NP-hard under randomised reductions; Micciancio (2001) extended hardness to factors below $\sqrt2$; Khot (J. ACM 2005) to every constant under randomised reductions; Haviv and Regev (STOC 2007) to $2^{(\log n)^{1-\varepsilon}}$ by tensoring; Micciancio (Theory of Computing 2012, doi:10.4086/toc.2012.v008a022) gave reductions with one-sided error and no false positives and suggested derandomisation as the route to deterministic hardness. Bennett and Peikert (arXiv:2202.07736, 2022) gave a simpler proof via Reed–Solomon codes for all norms.

Deterministic NP-hardness for $\ell_2$ would settle a 45-year-old question and remove the last randomness and assumption caveats from the foundations of lattice complexity. It concerns worst-case complexity, not cryptographic security, so it does not change deployed lattice cryptography; the proof techniques (explicit Reed–Solomon and Vandermonde gadgets) may inform reductions for related lattice and code problems.

A deterministic polynomial-time reduction from an NP-complete problem to exact SVP in $\ell_2$, or to $\mathrm{GapSVP}_\gamma$ in for some constant , with proof from alone. Extending to for some in would be a further result.