Mind the Gap? Not for SVP Hardness under ETH!

这篇论文题为 《Mind the Gap? Not for SVP Hardness under ETH!》（注意差距？在 ETH 下 SVP 的硬度并非如此！），由 Divesh Aggarwal 等人撰写。该研究在指数时间假设（ETH）下，证明了格（Lattice）上几个核心问题的近似版本具有指数级下界，填补了此前仅在更强的Gap-ETH假设下才成立的硬度结果之间的空白。

以下是该论文的详细技术总结：

1. 研究背景与问题定义

背景：
格密码学（如 NIST 后量子密码标准化中的方案）的安全性依赖于格问题的困难性。虽然已知格问题（如 SVP, CVP）在 NP 困难性假设下难以近似，但这并不排除存在次指数时间（sub-exponential time，即 $2^{o(n)}$）算法的可能性。为了排除这种可能性，需要更精细的复杂度假设。

• ETH (Exponential Time Hypothesis): 3SAT 问题无法在 $2^{o(n)}$ 时间内解决。
• Gap-ETH: 区分 3SAT 的完全可满足实例与最多满足 $\eta$ 比例子句的实例，需要 $2^{\Omega(n)}$ 时间。
• 现状： 此前，SVP（最短向量问题）、CVP（最近向量问题）和 BDD（有界距离解码）的近似版本仅在 Gap-ETH 下被证明是 $2^{\Omega(n)}$ 困难的。在较弱的 ETH 假设下，这些问题的硬度是未知的。

核心问题：
能否在较弱的 ETH 假设下，证明近似格问题（SVP, CVP, BDD）不存在 $2^{o(n)}$ 时间的算法？

定义的问题：

• CVP$_{p,\gamma}$: 给定格 $L$ 和目标 $t$，判断是否存在格向量距离 $t$ 小于等于 $r$，或者所有格向量距离 $t$ 都大于 $\gamma r$。
• SVP$_{p,\gamma}$: 给定格 $L$，判断是否存在非零向量长度小于等于 $r$，或者所有非零向量长度都大于 $\gamma r$。
• BDD$_{p,\alpha}$: 承诺目标 $t$ 距离格 $L$ 很近（$\le \alpha \cdot \lambda_1(L)$），寻找最近格向量。

---

2. 主要贡献与结果

论文证明了在 ETH 假设下，以下问题不存在 $2^{o(n)}$ 时间的算法（对于显式的常数 $\gamma > 1$ 或 $\alpha > \alpha^\ddagger_p$）：

1. CVP 的 ETH 硬度 (确定性归约):

   • 对于任意 $p \in [1, \infty)$，存在常数 $\gamma > 1$，使得 CVP$_{p,\gamma}$ 是 ETH 困难的。
   • 方法： 从 (gap) MAXLIN 问题直接进行确定性 Karp 归约。

2. SVP 的 ETH 硬度 (随机化归约):

   • 对于任意 $p \in (2, \infty)$，存在常数 $\gamma > 1$，使得 SVP$_{p,\gamma}$ 是随机化 ETH 困难的。
   • 突破点： 这是该论文的核心贡献。此前 SVP 的 Gap-ETH 硬度已知，但 ETH 硬度未知。
   • 关键性质： 发现整数格 $\mathbb{Z}^n$ 在 $\ell_p$ 范数下（$p>2$）具有独特的几何性质：靠近向量 $\frac{1}{2}\mathbf{1}_n$ 的格向量数量，指数级多于靠近原点（短向量）的格向量数量。

3. BDD 的 ETH 硬度:

   • 对于任意 $p \in [1, \infty)$ 和 $\alpha > \alpha^\ddagger_p$（$\alpha^\ddagger_p$ 是依赖于 $p$ 的显式阈值），BDD$_{p,\alpha}$ 是随机化 ETH 困难的。
   • 改进： 改进了从 3SAT 到 BDD 的归约，将之前的 Gap-ETH 结果提升到了 ETH 结果。

4. 线性码的最小距离问题 (MDP):

   • 作为推论，证明了某些常数近似因子的 MDP 也是 ETH 困难的。

---

3. 核心技术与方法

3.1 从线性方程组到 CVP (MAXLIN $\to$ CVP)

• 基础： 利用 Bitansky 等人 [BHIRW24] 的最新突破，即存在从 3SAT 到 (gap) MAXLIN 的多项式时间归约。MAXLIN 是在有限域上的线性方程组满足最大数量的问题。
• 构造： 作者构造了一个从 MAXLIN 到 CVP$_{p,\gamma}$ 的确定性归约。
  • 给定 MAXLIN 实例 $(M, v)$，构造格生成矩阵 $B = [M | 2I_m]$ 和目标向量 $t = v$。
  • 引入 $2I_m$ 确保距离计算在模 2 意义下进行，从而将线性方程的满足情况映射为格向量到目标的距离。
  • 如果 MAXLIN 是 YES 实例（满足 $5/8$ 方程），则存在距离 $\le r$ 的格向量；如果是 NO 实例，则所有格向量距离 $> \gamma r$。

3.2 从 CVP 到 SVP 的随机化归约 (核心创新)

这是解决 $p > 2$ 时 SVP 硬度的关键。

• 挑战： 之前的归约（如 Aggarwal & Stephens-Davidowitz [AS18]）依赖 ExactSetCover 问题，利用了一个“局部稠密”的格器件（gadget），使得 YES 实例下短向量数量爆炸式增长。但在 MAXLIN 归约中，由于目标向量的倍数（如 $2\ell t$）可能直接落在格中，导致无法直接复用旧技巧。
• 新几何性质： 作者证明了对于 $p > 2$，整数格 $\mathbb{Z}^d$ 配合目标 $t^\dagger = \frac{1}{2}\mathbf{1}_d$ 是一个更强的“局部稠密”器件。
  • 性质： 在 $\ell_p$ 范数下，靠近 $\frac{1}{2}\mathbf{1}_d$ 的格向量数量，指数级多于靠近 $0$或任何偶数倍$2\ell \cdot \frac{1}{2}\mathbf{1}_d$ 的格向量数量。
• 数学工具 (Theta 函数不等式)：
  • 利用 Theta 函数 $\Theta_p(\tau, t) = \sum_{z \in \mathbb{Z}} e^{-\tau |z-t|^p}$ 来估算格点数量。
  • 定理 4.1： 证明了对于任意 $p > 2$，存在 $\tau > 0$ 使得 $\Theta_p(\tau, 1/2) > \Theta_p(\tau, 0)$。
  • 证明技巧： 使用傅里叶分析和泊松求和公式（Poisson summation formula）。对于 $p$ 接近 2 的情况，通过分析超高斯函数（super-Gaussian）傅里叶变换的渐近展开，证明了差值序列 $f_p(\tau)$ 在某个 $\tau$ 下为正。
• 归约流程：
  1. 利用上述 CVP 归约得到 CVP 实例。
  2. 构造包含 CVP 实例和上述“局部稠密”器件的混合格。
  3. 使用**格稀疏化（Lattice Sparsification）**技术（Khot [Kho05]），随机采样一个子格。
  4. 利用几何性质：在 YES 情况下，靠近目标的向量（对应短向量）大量保留；在 NO 情况下，短向量几乎全部被剔除。从而将 CVP 归约到 SVP。

3.3 从 CVP 到 BDD

• 利用类似的构造，将 CVP 归约到 BDD。
• 通过控制参数 $\alpha$，确保在 YES 实例下，最近向量距离满足 BDD 的承诺（$\le \alpha \lambda_1$），而在 NO 实例下不满足。
• 证明了对于 $\alpha > \alpha^\ddagger_p$，BDD 是 ETH 困难的。

---

4. 结果总结表

问题	范数 $p$	假设	结果	备注
CVP$_{p,\gamma}$	$1 \le p < \infty$	ETH	$2^{\Omega(n)}$	确定性归约，新结果
SVP$_{p,\gamma}$	$2 < p < \infty$	随机化 ETH	$2^{\Omega(n)}$	随机化归约，核心新结果
SVP$_{p,\gamma}$	$p = \infty$	ETH	$2^{\Omega(n)}$	此前已知 (BGS17)
BDD$_{p,\alpha}$	$1 \le p < \infty$	随机化 ETH	$2^{\Omega(n)}$	改进阈值 $\alpha > \alpha^\ddagger_p$

注：对于 $p \in [1, 2]$ 的 SVP 硬度，目前仍是一个开放问题（Open Problem 1）。

---

5. 意义与影响

1. 理论突破： 该工作显著推进了格问题精细复杂度（Fine-grained Complexity）的研究。它表明，对于许多格问题，ETH 假设本身已经足够强，无需依赖更强的 Gap-ETH 假设即可证明次指数时间算法的不存在性。这为 ETH 与 Gap-ETH 之间的等价性提供了新的证据。
2. 密码学启示： 这些硬度结果直接支持了基于格的密码方案（如 LWE, NIST 后量子标准）的安全性。如果 ETH 成立，那么攻击这些方案所需的计算时间确实是指数级的，排除了存在高效（次指数）攻击算法的可能性。
3. 技术贡献：
   • 提出了新的几何性质（$\mathbb{Z}^n$ 在 $p>2$ 时靠近 $\frac{1}{2}\mathbf{1}$ 的稠密性）。
   • 发展了利用 Theta 函数和傅里叶分析处理 $p$-范数格点计数的新工具。
   • 简化了从 3SAT 到格问题的归约路径，使其在更弱的假设下成立。

总结： 这篇论文通过巧妙的几何构造和精细的数学分析，成功地在较弱的 ETH 假设下建立了 SVP、CVP 和 BDD 问题的指数级下界，填补了格密码学理论基础的重要空白。