2026-09-08T01:21:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26397 2026-09-05T19:42:00Z ddc:004 open_access

Mind the Gap? Not for SVP Hardness Under ETH! Aggarwal, Divesh Gupta, Rishav Morolia, Aditya Zhang, Chuanqi Lattices Fine-Grained Complexity Exponential Time Hypothesis Post-Quantum Cryptography We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [BHIRW24], who gave a polynomial-time reduction from 3SAT to the (gap) MAXLIN problem - a class of CSPs with linear equations over finite fields - we derive ETH hardness for several lattice problems. First, we show that for any p ∈ [1, ∞), there exists an explicit constant γ > 1 such that CVP _{p,γ} (the 𝓁_p-norm approximate Closest Vector Problem) does not admit a 2^o(n)-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) MAXLIN to CVP _{p,γ}. Our main contribution is a randomized ETH hardness result for SVP _{p,γ} (the 𝓁_p-norm approximate Shortest Vector Problem) for all p ∈ (2, ∞). This result relies on a novel geometric property of the integer lattice ℤⁿ in the 𝓁_p norm, which says that for any p ∈ (2, ∞), the number of lattice vectors close to 1/2 1_n (in the 𝓁_p norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from CVP _{p,γ} to SVP _{p,γ'}. Finally, we also use our ideas to give some minor improvements over prior reductions from 3SAT to BDD _{p, α} (the Bounded Distance Decoding Problem), yielding better ETH hardness results for BDD _{p, α} for any p ∈ [1, ∞) and α > α_p^{‡}, where α_p^{‡} is an explicit threshold depending on p. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Divesh Aggarwal and Rishav Gupta and Aditya Morolia and Chuanqi Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.8 urn:nbn:de:0030-drops-263979 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode