💻 computer science

Mind the Gap? Not for SVP Hardness under ETH!

This paper establishes new Exponential Time Hypothesis (ETH) hardness results for fundamental lattice problems, proving that approximate Closest Vector Problem ( $\mathsf{CVP}_p$ ) and Shortest Vector Problem ( $\mathsf{SVP}_p$ ) for $p \in (2, \infty)$ cannot be solved in $2^{o(n)}$ time by leveraging a novel geometric property of the integer lattice and a reduction from $\mathsf{3SAT}$ via $\mathsf{MAXLIN}$ .

Original authors: Divesh Aggarwal, Rishav Gupta, Aditya Morolia, Chuanqi Zhang

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Divesh Aggarwal, Rishav Gupta, Aditya Morolia, Chuanqi Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complex puzzle. In the world of computer science, this puzzle is often a Lattice Problem.

To understand what a lattice is, picture a giant, invisible 3D grid made of invisible strings stretching out forever in every direction. The points where the strings cross are called lattice points.

There are two main games you can play on this grid:

The Shortest Vector Game (SVP): Find the shortest string connecting the center of the grid to any other point.
The Closest Vector Game (CVP): You are given a specific spot in the air (a target). Find the lattice point closest to that spot.

For decades, cryptographers (the people who build digital locks) have relied on the fact that these games are incredibly hard to solve, especially as the grid gets bigger. If you can solve them quickly, you can break modern encryption.

The Big Question: "How hard is it really?"

For a long time, we knew these problems were hard if you had infinite time. But we didn't know if they were hard enough to stop a super-fast computer.

The authors of this paper are asking: "Is there a 'magic trick' that lets us solve these puzzles in a time that is just a little bit less than exponential?" (Think of it as finding a shortcut that saves you from climbing a mountain, but you still have to climb most of it).

They want to prove that no such shortcut exists. They want to show that solving these puzzles truly takes an amount of time that explodes exponentially as the grid gets bigger.

The "Gap" in the Theory

Previously, to prove these problems were this hard, researchers had to assume a very strong, somewhat unproven theory called Gap-ETH. It's like saying, "Assuming the universe is perfectly chaotic, these puzzles are hard."

This paper says: "We don't need to assume the universe is perfectly chaotic. We can prove it's hard even with a weaker, more standard assumption called ETH."

They managed to close the "Gap" between what we suspected was true and what we could prove.

How Did They Do It? (The Magic Tricks)

The authors used a clever chain of transformations, like a Rube Goldberg machine, to turn a known hard problem into a lattice problem.

1. The Translator (3SAT to MAXLIN)

First, they took a classic hard problem (3SAT, which is like a logic puzzle with "Yes/No" switches) and translated it into a math problem called MAXLIN.

Analogy: Imagine you have a recipe with many steps. Some steps must be done perfectly, others can be slightly off. MAXLIN asks: "What is the maximum number of steps you can get right?"
A recent breakthrough by other scientists showed that this "Max Steps" problem is already very hard. The authors used this as their starting point.

2. The "Closest Vector" Bridge (MAXLIN to CVP)

Next, they showed how to turn the "Max Steps" problem into the Closest Vector Problem (CVP).

Analogy: Imagine you have a target on a wall. You have a bunch of arrows (lattice points). If you can hit the "Max Steps" goal, your arrow lands very close to the target. If you can't, your arrow lands far away.
They built a specific grid where the distance to the target perfectly mirrors the success of the logic puzzle. This proved that CVP is hard.

3. The "Shortest Vector" Surprise (CVP to SVP)

This is the paper's biggest breakthrough. They needed to turn the "Closest Vector" problem into the "Shortest Vector" problem.

The Problem: Usually, these two games are different. In one, you look for a point near a target; in the other, you look for the shortest point from the center.
The Magic Gadget: The authors discovered a special property of integer grids in certain dimensions. They found a "magic spot" (specifically, the point exactly halfway between grid lines, like 0.5, 0.5, 0.5...) that is surrounded by a massive crowd of lattice points.
The Analogy: Imagine a party.
- The Center: The origin (0,0,0) is a quiet room with very few people (short vectors).
- The Magic Spot: The point (0.5, 0.5, 0.5) is a packed dance floor with exponentially more people (vectors) than the quiet room.
- Because this "dance floor" is so crowded, the authors could use it to trick a computer. They created a scenario where if the answer to the puzzle is "Yes," the computer finds a short vector hidden in the crowd. If the answer is "No," the crowd disappears, and no short vector exists.

Why Does This Matter?

Stronger Security: This paper gives us more confidence that the digital locks protecting our bank accounts and private messages (Post-Quantum Cryptography) are actually unbreakable, even by future super-computers.
Mathematical Truth: It proves that the difficulty of these problems isn't just a fluke of a specific assumption; it's a fundamental property of math.
Closing the Gap: They showed that we don't need to rely on the "strongest" possible assumptions to prove these problems are hard. The standard assumptions are enough.

The Bottom Line

The authors looked at the "gap" in our understanding of how hard lattice problems are. They didn't just jump over it; they built a bridge. They proved that finding the shortest path or the closest point on a high-dimensional grid is exponentially difficult, and there are no shortcuts.

So, to the hackers and quantum computers of the future: Mind the gap? No, you can't cross it. The math is too hard.

1. Problem Statement

The paper addresses the fine-grained computational hardness of fundamental lattice problems under the Exponential Time Hypothesis (ETH). Specifically, it investigates whether the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), and the Bounded Distance Decoding (BDD) problem admit sub-exponential time algorithms ( $2^{o(n)}$ ) in the $\ell_p$ norm.

Context: While these problems are known to be NP-hard, the existence of sub-exponential algorithms remains a critical open question with profound implications for post-quantum cryptography.
The Gap: Prior to this work, strong inapproximability results (ruling out $2^{o(n)}$ algorithms) for these problems were established only under the stronger Gap-ETH assumption (which posits that distinguishing satisfiable 3SAT instances from those with a constant fraction of unsatisfied clauses requires $2^{\Omega(n)}$ time).
Goal: The authors aim to prove ETH-hardness (under the standard ETH, which only assumes 3SAT requires $2^{\Omega(n)}$ time) for these lattice problems, effectively bridging the gap between ETH and Gap-ETH in the context of lattice inapproximability.

2. Methodology and Techniques

The paper builds upon a recent breakthrough by Bitansky et al. [BHIRW24], which provided a polynomial-time reduction from 3SAT to the gap-MAXLIN problem (a constraint satisfaction problem involving linear equations over finite fields). The authors chain this reduction with novel geometric and analytic techniques to derive hardness for lattice problems.

A. From MAXLIN to CVP (Deterministic Reduction)

Approach: The authors construct a deterministic Karp reduction from the gap-MAXLIN problem to the approximate Closest Vector Problem (CVP $_{p,\gamma}$ ).
Construction: Given a MAXLIN instance $(M, v)$ over $\mathbb{F}_2$ , they define a lattice generated by the matrix $B = [M \mid 2I_m]$ and a target vector $t = v$ .
Mechanism: The inclusion of $2I_m$ ensures that lattice points $Bx$ approximate the target $t$ modulo 2. If the MAXLIN instance is a "YES" instance (many equations satisfied), there exists a lattice vector close to $t$ . If it is a "NO" instance, all lattice vectors are far from $t$ .
Result: This establishes ETH-hardness for CVP $_{p,\gamma}$ for all $p \in [1, \infty)$ .

B. From CVP to SVP (Randomized Reduction via Geometric Gadgets)

This is the paper's most significant technical contribution. Reducing CVP to SVP is notoriously difficult because SVP requires finding the shortest vector, whereas CVP involves a target vector.

The Challenge: Previous reductions (e.g., Aggarwal & Stephens-Davidowitz [AS18]) relied on Exact Set Cover and a "locally dense gadget" where the number of vectors close to a target $t$ is exponentially larger than the number of short vectors (near the origin). However, this property did not hold for the specific structure of the CVP instances derived from MAXLIN.
Novel Geometric Property: The authors prove a new property of the integer lattice $\mathbb{Z}^n$ $Z^{n}$ in the $\ell_p$ $ℓ_{p}$ norm for $p > 2$ $p > 2$ :
- For the target vector $t = \frac{1}{2}\mathbf{1}_n$ (the all-half vector), the number of lattice vectors close to $t$ is exponentially larger than the number of short vectors (close to the origin).
- Crucially, they show this density gap holds even when considering even multiples of the target ( $2\ell t$ ), which is necessary because the CVP construction from MAXLIN involves even integer shifts.
Analytic Tool (Theta Functions): To prove this density gap, the authors analyze the Theta function $\Theta_p(\tau, t) = \sum_{z \in \mathbb{Z}} e^{-\tau |z-t|^p}$ $Θ_{p} (τ, t) = \sum_{z \in Z} e^{- τ ∣ z - t ∣^{p}}$ .
- They define the difference function $f_p(\tau) = \Theta_p(\tau, 1/2) - \Theta_p(\tau, 0)$ .
- Using Fourier analysis and the Poisson summation formula, they prove that for any $p > 2$ , there exists a $\tau > 0$ such that $f_p(\tau) > 0$ . This implies $\Theta_p(\tau, 1/2) > \Theta_p(\tau, 0)$ , confirming the existence of the locally dense gadget.
- Note: They explicitly note that this property fails for $p=2$ , leaving $p \in [1, 2]$ as an open problem.
Reduction Chain: They combine the CVP instance with this new gadget and apply lattice sparsification (a randomized technique to sample a sub-lattice) to convert the CVP instance into an SVP instance. If the original CVP was a YES instance, the sparse sub-lattice retains a short vector; if NO, it does not.

C. Reduction to BDD

The authors extend their techniques to the Bounded Distance Decoding (BDD) problem.
They provide a decision-to-search reduction from CVP to BDD, improving upon prior results by removing the need for specific "binary" CVP instances and working with general integer lattice CVP instances.
This yields ETH-hardness for BDD $_{p,\alpha}$ for any $\alpha > \alpha^\ddagger_p$ , where $\alpha^\ddagger_p$ is an explicit threshold depending on $p$ .

3. Key Contributions and Results

The paper establishes the following main theorems (summarized in Table 1 of the paper):

ETH Hardness of CVP $_{p,\gamma}$ :
- For any $p \in [1, \infty)$ , there exists a constant $\gamma > 1$ such that CVP $_{p,\gamma}$ cannot be solved in $2^{o(n)}$ time unless ETH is false.
- Significance: This is the first ETH-based hardness result for CVP in general $\ell_p$ norms.
Randomized ETH Hardness of SVP $_{p,\gamma}$ :
- For any $p \in (2, \infty)$ , there exists a constant $\gamma > 1$ such that SVP $_{p,\gamma}$ cannot be solved in $2^{o(n)}$ time unless the Randomized ETH is false.
- Significance: This resolves the open problem of SVP hardness under ETH for $p > 2$ . It relies on the novel geometric property of $\mathbb{Z}^n$ and the Theta function analysis.
- Open Problem: The case $p \in [1, 2]$ remains open.
ETH Hardness of BDD $_{p,\alpha}$ :
- For any $p \in [1, \infty)$ and $\alpha > \alpha^\ddagger_p$ , BDD $_{p,\alpha}$ has no $2^{o(n)}$ time algorithm unless Randomized ETH is false.
- Significance: This improves the threshold $\alpha$ compared to previous Gap-ETH results and establishes the result under the weaker ETH assumption.
Hardness for Linear Codes:
- As a corollary, the authors derive ETH hardness for the Minimum Distance Problem (MDP) for linear codes, as MAXLIN is essentially the Nearest Codeword Problem (NCP).

4. Significance

Bridging ETH and Gap-ETH: The work demonstrates that the powerful inapproximability results previously known only under the strong Gap-ETH assumption can be derived under the standard ETH. This strengthens the theoretical foundation for the hardness of lattice problems.
Cryptographic Implications: Post-quantum cryptographic schemes (like those in the NIST standardization process) rely on the worst-case hardness of lattice problems. Proving that no sub-exponential algorithms exist under ETH provides stronger security guarantees than assuming only NP-hardness.
New Analytic Techniques: The use of Fourier analysis and Theta functions to establish geometric properties of integer lattices in $\ell_p$ norms ( $p>2$ ) is a novel contribution that may have applications in other areas of discrete geometry and complexity theory.
Open Directions: The paper identifies the case $p \in [1, 2]$ for SVP as a major open problem, suggesting that the geometric intuition used for $p > 2$ (specifically the behavior of the Theta function) does not directly extend to the Euclidean norm ( $p=2$ ) or $p < 2$ .

In summary, this paper significantly advances the fine-grained complexity landscape of lattice problems by proving that fundamental problems like SVP and CVP are likely hard to approximate in sub-exponential time, relying only on the standard Exponential Time Hypothesis.