利用中点Hessian矩阵在$2^{0.6039n}$时间内求解最短向量问题

**摘要**  
我们提出了最短向量问题 \(\mathsf{SVP}\) 的随机化算法。对于 \(n\) 维格 \(\mathcal{L}\)，我们的算法在经典情形下以 \(2^{0.6039n+o(n)}\) 时间、在量子情形下以 \(2^{0.5411n+o(n)}\) 时间，以及 \(2^{0.5n+o(n)}\) 空间求解 SVP，改进了 Aggarwal、Dadush、Regev 和 Stephens-Davidowitz [STOC’15] 之前最好的 \(2^{n+o(n)}\) 时间和空间算法。我们的算法大量使用了周期高斯函数在半最短向量处的海森矩阵的性质：对于最短向量 \(v\in\mathcal{L}\)，海森矩阵在 \(v/2\) 处有一个接近 \(v\) 的特征向量，这可用于（预处理）有界距离解码算法来恢复 \(v\)。给定模 \(\mathcal{L}\) 的周期性，候选中点由 \(\mathcal{L}/2\mathcal{L}\) 中的奇偶类索引。我们的算法通过使用离散高斯样本估计相应的海森矩阵来搜索最短向量的类别。我们利用随机子格陪集和各种采样技术优化算法，实现了最终复杂度。这些优化技术可能具有独立的价值。

#### AI 使用声明。  
本文的大部分结果是在 ChatGPT 5.5 Pro 和 ChatGPT 5.6 Sol Ultra 的协助下发现的。虽然作者提出了若干方向和优化，但所有技术细节均由 AI 发现，并由作者验证。手稿由作者基于 AI 生成的初始草稿撰写。作者对内容承担全部责任。手稿中的所有错误可能都源于作者的人为错误。

###### 目录  
1. [1 引言](#S1)  
   1.1 [技术概述](#S1.SS1)  
2. [2 预备知识](#S2)  
   2.1 [格与解码](#S2.SS1)  
   2.2 [离散高斯](#S2.SS2)  
   2.3 [有用的不等式](#S2.SS3)  
3. [3 从海森矩阵恢复最短向量](#S3)  
   3.1 [尺度与高斯质量界](#S3.SS1)  
   3.2 [周期高斯与最短奇偶类](#S3.SS2)  
   3.3 [估计海森矩阵并恢复最短向量](#S3.SS3)  
4. [4 批量海森矩阵估计](#S4)  
5. [5 随机子格陪集海森矩阵](#S5)  
   5.1 [高斯和海森矩阵和](#S5.SS1)  
   5.2 [随机陪集海森矩阵](#S5.SS2)  
   5.3 [估计陪集海森矩阵](#S5.SS3)  
   5.4 [陪集海森矩阵与最短向量](#S5.SS4)  
   5.5 [仿射陪集算法](#S5.SS5)  
6. [6 仿射格陪集上的重要性采样](#S6)  
   6.1 [最短奇偶类中的格点](#S6.SS1)  
   6.2 [从仿射格陪集采样（更宽的）离散高斯](#S6.SS2)  
   6.3 [通过重要性采样估计海森矩阵](#S6.SS3)  
   6.4 [恢复最短向量](#S6.SS4)  
   6.5 [重要性采样算法](#S6.SS5)  
   6.6 [通过稀疏化降低空间](#S6.SS6)  
   6.7 [空间高效的实现](#S6.SS7)  
   6.8 [量子算法](#S6.SS8)  
7. [参考文献](#bib)

## 1 引言

一个 \(n\) 维格 \(\mathcal{L}=\mathcal{L}(b_{1},\ldots,b_{n})\) 是线性无关向量 \(b_{1},\ldots,b_{k}\in\mathbb{R}^{n}\) 的所有整数组合构成的集合。为简单起见，我们只考虑满足 \(k=n\) 的满秩格。（搜索）最短向量问题 \(\mathsf{SVP}\) 要求给定 \(\mathcal{L}\) 的一个基，找到一个非零的最小范数向量。格问题（包括 \(\mathsf{SVP}\)）有两个方面。\(\mathsf{SVP}\) 的近似变体长期以来一直充当计算数论、整数规划和密码分析中的算法工具 [25, 21, 26, 39, 24]。另一方面，精确问题及其小近似因子版本已知是困难的 [9, 11, 4, 22, 19]。鉴于格问题与许多近期密码学原语之间的密切联系 [38, 12, 29, 37, 7, 17]，格问题已成为后量子密码学最有前景的基础之一。\(\mathsf{SVP}\) 仍然是我们理解格问题复杂性的基本基准。研究者们发现了各种最坏情况算法 [18, 30, 8, 21, 32, 35, 31, 13] 以及启发式或平均情况算法 [32, 34, 10]。然而，迄今为止，最好的可证明最坏情况运行时间仍然是 \(2^{n+o(n)}\)，且具有相同的空间复杂度 [2]，这使用了新的高效离散高斯采样算法。后来，[1] 给出了若干时间-空间权衡和量子加速，包括 \(2^{1.669n+o(n)}\) 时间和 \(2^{n/2+o(n)}\) 空间的算法，以及分别在没有和具有量子随机存取存储器（QRAM）的情况下的 \(2^{0.950n+o(n)}\) 和 \(2^{0.835n+o(n)}\) 量子时间。我们给出了一类新的 \(\mathsf{SVP}\) 最坏情况算法，显著改进了之前的经典和量子算法 [2, 1]。我们的主要结果总结如下。

###### 定理 1.1。  
存在随机化经典和量子算法，能以至少 \(2/3\) 的概率求解 Search-\(\mathsf{SVP}\)，其经典期望时间为 \(2^{0.603867n+o(n)}\)，量子期望时间为 \(2^{0.541051n+o(n)}\)，空间为 \(2^{0.5n+o(n)}\)，至多相差输入长度的多项式因子。量子算法需要大小为 \(2^{0.36036n+o(n)}\) 的 QRAM。

我们讨论定理 1.1 的一些直接应用。显然，我们的算法以相同的时间和空间复杂度求解近似或唯一 \(\mathsf{SVP}\) 及其间隙版本。我们的算法击败了之前最好的时间记录 [41, 3, 27]：常数因子近似 \(\mathsf{SVP}\) 的 \(2^{0.802n+o(n)}\) 时间和 \(2^{0.401n+o(n)}\) 空间，尽管后者使用更少的空间。这一改进可以方便地用于其他应用。例如，最著名的多项式因子近似 \(\mathsf{SVP}\) [3，定理 5.3] 在较小维度上调用一次常数因子 \(\mathsf{SVP}\) 预言机。最初证明使用来自 [27] 的指数为 \(0.802n\) 的预言机。将其替换为我们后，我们将求解 \(\widetilde{O}(n^{c})\)-\(\mathsf{SVP}\) 的时间复杂度从 \(2^{\frac{n}{2c+1.24}}\) 改进为 \(2^{\frac{n}{2c+1.65}}\)。另一个直接应用是具有距离承诺的 \(\mathsf{BDD}\) 或精确 \(\mathsf{CVP}\)。利用 Kannan 嵌入，具有承诺 \(\operatorname{dist}(t,\mathcal{L})<\sqrt{3}\lambda_{1}(\mathcal{L})/2\) 的 \((t,\mathcal{L})\) 的 \(\mathsf{CVP}\) 可以归约到增加一个维度的 \(\mathsf{SVP}\)（例如参见 [28]）。因此，使用我们的算法可以在相同的时间和空间内解决具有上述承诺的 \(\mathsf{BDD}\) 和 \(\mathsf{CVP}\)。此前，[14, 2] 给出了 \(\alpha<0.422\) 时 \(2^{n/2+o(n)}\) 时间的算法。最后，利用从中心化 \(\mathsf{DGS}\) 到 \(\mathsf{SVP}\) 的保维度归约 [40]，我们可以在相同时间内以任意参数采样一个（或多项式多个）离散高斯样本。这在某种程度上回答了 [2] 中关于平滑之下中心离散高斯采样的开放问题，尽管其时间复杂度比 \(2^{n/2+o(n)}\) 更差。一项并行工作 [23] 给出了任意参数的 \(2^{n/2+o(n)}\) 时间离散高斯采样算法。

### 1.1 技术概述

设 \(\mathcal{L}\) 是一个以 \(B\) 为基的 \(n\) 维满秩格，\(s>0\) 是宽度参数。其对偶格 \(\mathcal{L}^{*}=\{y:\left\langle y,x\right\rangle\in\mathbb{Z}\text{ for every }x\in\mathcal{L}\}\) 以 \(B^{-T}\) 为基。定义 \(\rho_{s}(x):=\exp\!\left(-\pi\frac{\norm{x}^{2}}{s^{2}}\right)\)，并令 \(\rho_{s}(A):=\sum_{x\in A}\rho_{s}(x)\)。我们定义（中心化）离散高斯分布 \(D_{\mathcal{L},s}(x):=\frac{\rho_{s}(x)}{\rho_{s}(\mathcal{L})}\)。周期高斯函数 [6] \(F_{s}:\mathbb{R}^{n}\to\mathbb{R}\) 定义为
\[
F_{s}(z):=\frac{\rho_{s}(\mathcal{L}+z)}{\rho_{s}(\mathcal{L})}
=\mathbb{E}_{X\sim D_{\mathcal{L}^{*},1/s}}\left[e^{2\pi i\langle X,z\rangle}\right]
\]
其中最后一个等式由泊松求和公式得出。显然 \(F_{s}\) 是 \(\mathcal{L}\)-周期的，即对于 \(v\in\mathcal{L}\)，\(F_{s}(z)=F_{s}(z+v)\)。

#### 在中点，海森矩阵指示方向。

我们的算法从研究其海森矩阵 [36, 14] 开始，它也有两种表示。对第一个表示求微分，可得
\[
\nabla^{2}F_{s}(z)+\frac{2\pi}{s^{2}}F_{s}(z)I_{n}
=\frac{4\pi^{2}}{s^{4}\rho_{s}(\mathcal{L})}\sum_{y\in\mathcal{L}}(y-z)(y-z)^{T}e^{-\pi\norm{y-z}^{2}/s^{2}}
\tag{1}
\]
对第二个表示求微分，可得
\[
\nabla^{2}F_{s}(z)=-4\pi^{2}\mathbb{E}_{X\sim D_{\mathcal{L}^{*},1/s}}\left[XX^{T}e^{2\pi i\left\langle X,z\right\rangle}\right].
\tag{2}
\]
从这两种表示中，我们观察到以下两个性质。首先，设 \(v\) 是最短向量，\(\|v\|=\lambda\)，并将 \(\nabla^{2}F_{s}(v/2)\) 代入式 (1)，可以看到
\[
\nabla^{2}F_{s}(v/2)+aI
=\frac{4\pi^{2}}{s^{4}\rho_{s}(\mathcal{L})}\left(\frac{vv^{T}}{2}e^{-\pi\lambda^{2}/4s^{2}}+\sum_{y\in\mathcal{L}\setminus\{0,v\}}(y-v/2)(y-v/2)^{T}e^{-\pi\norm{y-v/2}^{2}/s^{2}}\right)
\]
其中 \(a:=2\pi F_{s}(v/2)/s^{2}\) 在谱分析中不重要。注意到对于 \(y\neq 0,v\)，\(\norm{y-v/2}\) 远大于 \(\norm{v/2}=\lambda/2\)，我们可以预期 \(\nabla^{2}F_{s}(v/2)+aI\) 接近于 \(vv^{T}\) 的倍数。对于适当选择的 \(s\)，这种直觉可以用以下关于 \(\nabla^{2}F_{s}(v/2)\) 的最大特征值对应的归一化特征向量 \(\tilde{v}\) 的陈述加以形式化：\(\tilde{v}\) 与 \(v/\norm{v}\) 有*逆多项式接近*。然后，给定 \(\tilde{v}\)，我们猜测 \(\lambda\)（这只需多项式次迭代），并对目标向量 \(\lambda\tilde{v}\) 求解有界距离解码（\(\mathsf{BDD}\)）问题。这个 \(\mathsf{BDD}\) 步骤可以相对较快，这得益于 [1] 中的预处理 BDD 算法：在 \(2^{0.5n+o(n)}\) 时间预处理之后，该算法能以逆多项式距离在 \(2^{o(n)}\) 时间内求解每个 BDD 实例。

#### 如果我们知道去哪里找，一个海森矩阵就足够了。

这给出了我们的第一个结果（定理 3.7），时间复杂度为 \(2^{1.463n+o(n)}\)，空间复杂度为 \(2^{0.5n+o(n)}\)。假设对于最短向量 \(v\)，我们知道它在陪集 \(v+2\mathcal{L}\) 中的一个代表 \(w\)。我们*计算* \(\nabla^{2}F_{s}(w/2)\) 的特征向量 \(\tilde{w}\)，并使用（预处理）BDD 对 \(\tilde{w}\) 求解 BDD 问题。但是，如何计算 \(\nabla^{2}F_{s}(w/2)\)？这里第二个表示式 (2) 就派上了用场。我们使用 [2] 中的算法，从 \(\mathcal{L}^{*}\) 上的离散高斯分布中采样 \(N=2^{n/2}\) 个元素，例如 \(X_{1},\ldots,X_{N}\)，所需时间为 \(2^{n/2+o(n)}\)。然后，给定 \(w/2\)，我们使用估计器
\[
\widehat{\nabla^{2}F_{s}}(w/2)=\frac{-4\pi^{2}}{N}\sum_{i=1}^{N}X_{i}X_{i}^{T}e^{2\pi i\left\langle X_{i},w/2\right\rangle}.
\]
集中不等式和格论文献中的结果表明，大约 \(2^{2t_{0}n+o(n)}\) 个样本（其中 \(t_{0}=2^{0.802}/4e\ln 2=0.2314\)）就足以精确估计实际的 \(\nabla^{2}F_{s}(w/2)\) 及其特征向量。这导致