Fine-grained deterministic hardness of the shortest vector problem

2025/11/03 by Hittmeir, Markus
#11H06 #11Y16 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2511.01626

Abstract

Let γ-GapSVP_p be the decision version of the shortest vector problem in the ℓ_p-norm with approximation factor γ, let n be the lattice dimension and 0<ε≤ 1. We prove that the following statements hold for infinitely many values of p. (2-ε)-GapSVP_p is not in O(2^O(p)⋅ n^O(1))-time, unless P=NP. (2-ε)-GapSVP_p is not in O(2^2^o(p)⋅ 2^o(n))-time, unless the Strong Exponential Time Hypothesis is false. The proofs are based on a Karp reduction from a variant of the subset-sum problem that imposes restrictions on vectors orthogonal to the vector of its weights. While more extensive hardness results for the shortest vector problem in all ℓ_p-norms have already been established under randomized reductions, the results in this paper are fully deterministic.

Citations

• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ_p norms for p>2
• Verification of NP-hardness Reduction Functions for Exact Lattice Problems
• Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ_p Norms
• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
• Improved Hardness of BDD and SVP Under Gap-(S)ETH
• Parameterized Intractability of Even Set and Shortest Vector Problem
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• Factoring polynomials with rational coefficients

Related

• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ_p norms for p>2
• Improved hardness results for unique shortest vector problem
• Improved Hardness of BDD and SVP Under Gap-(S)ETH
• A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices