Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓp Norms for p>2

We establish deterministic hardness of approximation results for the Shortest Vector Problem in ℓp norm (SVPp) and for Unique-SVP (uSVPp)-namely, instances promised to have a unique shortest vector-for all p > 2. Previously, no deterministic hardness results were known, except for ℓ∞.

For every p > 2, we prove constant-ratio hardness: no polynomial-time algorithm approximates SVPp or uSVPp within a ratio of √ 2 -o(1), assuming 3SAT / ∈ DTIME(2 O(n 2/3 log n) ), and, respectively,

We also show that for any ε > 0 there exists pε > 2 such that for every p ≥ pε: no polynomialtime algorithm approximates SVPp within a ratio of 2

, assuming NP ⊈ SUBEXP. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for uSVPp under the assumptions Unambiguous-3SAT ̸ ⊆ DTIME(n (log n) ε

) and Unambiguous-3SAT ̸ ⊆ SUBEXP, improving the previously known 1 + o(1) [Stephens-Davidowitz, Approx 2016].

Strengthening the hardness of uSVP at weaker approximation ratios has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for γ-uSVPp carries over to 1 γ -BDDp (Bounded Distance Decoding). Thus, understanding the hardness of uSVP improves worst-case guarantees for the two core problems that underpin security in lattice-based cryptography.