定义 1.1 (格)#

给定 \(k\) 个线性无关的向量 \(\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_k \in \mathbb{R}^n\)，由这些向量生成的格 \(\mathcal{L}\) 定义为： \(\mathcal{L} = \left\{ \sum_{i=1}^{k} c_i \mathbf{b}_i \mid c_i \in \mathbb{Z} \right\}\) 这组线性无关的向量 \(\{\mathbf{b}_1, \dots, \mathbf{b}_k\}\) 称为格 \(\mathcal{L}\) 的一组 基 (Basis)。向量 \(\mathbf{b}_i\) 称为 基向量 (Basis vectors)。

关键点：

• 离散性 (Discreteness): 格点在空间中是离散分布的，任意两个不同的格点之间存在一个最小距离。这是因为基向量线性无关，且系数 \(c_i\) 只能取整数。
• 加法子群 (Additive Subgroup): 格 \(\mathcal{L}\) 是 \(\mathbb{R}^n\) 的一个加法子群。这意味着：
  • 零向量 \(\mathbf{0} \in \mathcal{L}\) (取所有 \(c_i = 0\))。
  • 如果 \(\mathbf{x}, \mathbf{y} \in \mathcal{L}\)，那么 \(\mathbf{x} + \mathbf{y} \in \mathcal{L}\)。
  • 如果 \(\mathbf{x} \in \mathcal{L}\)，那么 \(-\mathbf{x} \in \mathcal{L}\)。
• 维度 (Dimension/Rank): 生成格的线性无关基向量的个数 \(k\) 称为格的 维度 (Dimension) 或 秩 (Rank)。我们通常称 \(n\) 为格的 嵌入维度 (Embedding dimension)。如果 \(k=n\)，则称该格为 满秩格 (Full-rank lattice)。在本报告中，除非特别说明，我们通常考虑满秩格，即 \(k=n\)。

格的表示：基矩阵#

我们可以将格的基向量 \(\mathbf{b}_1, \dots, \mathbf{b}_n\) (假设为满秩格) 排列成一个 \(n \times n\) 的矩阵 \(\mathbf{B}\)，其中每一列（或每一行，取决于约定，本书约定为列向量）是基向量： \(\mathbf{B} = [\mathbf{b}_1 | \mathbf{b}_2 | \dots | \mathbf{b}_n]\) 这个矩阵 \(\mathbf{B}\) 称为格 \(\mathcal{L}\) 的 基矩阵 (Basis matrix)。那么，格 \(\mathcal{L}\) 可以表示为： \(\mathcal{L} = \{ \mathbf{B} \mathbf{c} \mid \mathbf{c} \in \mathbb{Z}^n \}\) 其中 \(\mathbf{c} = (c_1, \dots, c_n)^T\) 是整数系数向量。

示例 (二维格):#

考虑 \(\mathbb{R}^2\) 中的两个向量 \(\mathbf{b}_1 = (2, 0)^T\) 和 \(\mathbf{b}_2 = (1, 1)^T\)。它们是线性无关的。它们生成的格 \(\mathcal{L}\) 包含所有形如 \(c_1(2, 0)^T + c_2(1, 1)^T = (2c_1 + c_2, c_2)^T\) 的点，其中 \(c_1, c_2 \in \mathbb{Z}\)。 这个格的基矩阵是 \(\mathbf{B} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}\)。 一些格点包括：\((0,0), (2,0), (1,1), (3,1), (-2,0), (-1,-1), \dots\)

不同的基表示同一个格#

同一个格可以由不同的基来表示。例如，在上面的二维例子中，向量组 \(\mathbf{b}'_1 = \mathbf{b}_1 = (2, 0)^T\) 和 \(\mathbf{b}'_2 = \mathbf{b}_1 + \mathbf{b}_2 = (3, 1)^T\) 也是该格的一组基。基矩阵变为 \(\mathbf{B}' = \begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix}\)。

那么，两组基 \(\{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 和 \(\{\mathbf{b}'_1, \dots, \mathbf{b}'_n\}\) 生成同一个格 \(\mathcal{L}\) 的充要条件是什么？ 设 \(\mathbf{B}\) 和 \(\mathbf{B}'\) 是对应的基矩阵。如果它们生成同一个格，那么每个 \(\mathbf{b}'_j\) 必须是 \(\{\mathbf{b}_i\}\) 的整数线性组合，同时每个 \(\mathbf{b}_i\) 也必须是 \(\{\mathbf{b}'_j\}\) 的整数线性组合。这意味着存在一个整数矩阵 \(\mathbf{U}\) 使得 \(\mathbf{B}' = \mathbf{B} \mathbf{U}\)，并且存在一个整数矩阵 \(\mathbf{V}\) 使得 \(\mathbf{B} = \mathbf{B}' \mathbf{V}\)。 将第二个式子代入第一个，得到 \(\mathbf{B}' = \mathbf{B}' \mathbf{V} \mathbf{U}\)。由于 \(\mathbf{B}'\) 的列向量是线性无关的（满秩），这意味着 \(\mathbf{V} \mathbf{U} = \mathbf{I}\) (单位矩阵)。 同样地，\(\mathbf{U} \mathbf{V} = \mathbf{I}\)。 这表明 \(\mathbf{U}\) 和 \(\mathbf{V}\) 互为逆矩阵，并且它们都是整数矩阵。一个整数矩阵，其逆矩阵也是整数矩阵，这样的矩阵称为 幺模矩阵 (Unimodular matrix)。

定理 1.1 (基变换)#

两组基 \(\mathbf{B}\) 和 \(\mathbf{B}'\) 生成同一个格 \(\mathcal{L}\)，当且仅当存在一个幺模矩阵 \(\mathbf{U}\) (即 \(\mathbf{U}\) 是整数矩阵且 \(\det(\mathbf{U}) = \pm 1\)) 使得 \(\mathbf{B}' = \mathbf{B} \mathbf{U}\)。

这个性质非常重要，它说明格是比特定基更基本的对象。格算法的核心目标之一（格基约化）就是找到一个“好”的基 \(\mathbf{B}'\)，它通过幺模变换 \(\mathbf{U}\) 从一个可能“坏”的基 \(\mathbf{B}\) 得到。

基本区域 (Fundamental Domain / Parallelepiped)#

给定格 \(\mathcal{L}\) 的一组基 \(\{\mathbf{b}_1, \dots, \mathbf{b}_n\}\)，由这组基定义的 基本平行多面体 (Fundamental Parallelepiped) (在 \(\mathbb{R}^n\) 中) 是集合： \(\mathcal{P}(\mathbf{B}) = \left\{ \sum_{i=1}^{n} \alpha_i \mathbf{b}_i \mid 0 \le \alpha_i < 1 \right\}\) 这是一个半开半闭的区域。

基本平行多面体具有重要的性质：\(\mathbb{R}^n\) 空间可以被格点 \(\mathbf{v} \in \mathcal{L}\) 对基本平行多面体 \(\mathcal{P}(\mathbf{B})\) 的平移副本 \(\mathcal{P}(\mathbf{B}) + \mathbf{v}\) 无重叠地完全覆盖。即： \(\mathbb{R}^n = \bigcup_{\mathbf{v} \in \mathcal{L}} (\mathcal{P}(\mathbf{B}) + \mathbf{v})\) 并且对于不同的 \(\mathbf{v}_1, \mathbf{v}_2 \in \mathcal{L}\)，\((\mathcal{P}(\mathbf{B}) + \mathbf{v}_1)\) 和 \((\mathcal{P}(\mathbf{B}) + \mathbf{v}_2)\) 的内部是不相交的。

直观地说，基本平行多面体代表了格点在空间中的“势力范围”或“单元格”。它的体积在格理论中扮演着核心角色。

格的行列式 (Determinant / Volume)#

格 \(\mathcal{L}\) 的 行列式 (Determinant)，记作 \(\det(\mathcal{L})\) 或 \(\text{vol}(\mathcal{L})\)，定义为由任意一组基 \(\mathbf{B} = [\mathbf{b}_1, \dots, \mathbf{b}_n]\) 生成的基本平行多面体 \(\mathcal{P}(\mathbf{B})\) 的 \(n\) 维体积 (Volume)。 \(\det(\mathcal{L}) = \text{vol}(\mathcal{P}(\mathbf{B}))\) 如何计算这个体积？如果基向量存储为 \(n \times n\) 矩阵 \(\mathbf{B}\) 的列，那么体积是： \(\det(\mathcal{L}) = |\det(\mathbf{B})|\) 如果基向量存储为矩阵的行，体积也是 \(|\det(\mathbf{B})|\)。 一个关键性质是，格的行列式不依赖于基的选择。如果我们用另一个基 \(\mathbf{B}' = \mathbf{B} \mathbf{U}\) (其中 \(\mathbf{U}\) 是幺模矩阵) 来计算，则： \(|\det(\mathbf{B}')| = |\det(\mathbf{B} \mathbf{U})| = |\det(\mathbf{B})| |\det(\mathbf{U})| = |\det(\mathbf{B})| \times |\pm 1| = |\det(\mathbf{B})|\) 因此，\(\det(\mathcal{L})\) 是格 \(\mathcal{L}\) 的一个内在不变量。

几何意义： 格的行列式代表了基本单元的体积。它反映了格点的“密度”。行列式越小，格点越密集；行列式越大，格点越稀疏。在二维情况下，它就是基本平行四边形的面积。

另一种计算方式：Gram 矩阵#

有时通过 Gram 矩阵计算行列式更方便。给定基 \(\mathbf{B} = [\mathbf{b}_1, \dots, \mathbf{b}_n]\)，其 Gram 矩阵 \(\mathbf{G}\) 定义为： \(\mathbf{G} = \mathbf{B}^T \mathbf{B}\) 矩阵 \(\mathbf{G}\) 的第 \((i, j)\) 个元素是内积 \(\langle \mathbf{b}_i, \mathbf{b}_j \rangle = \mathbf{b}_i^T \mathbf{b}_j\)。那么， \(\det(\mathbf{G}) = \det(\mathbf{B}^T \mathbf{B}) = \det(\mathbf{B}^T) \det(\mathbf{B}) = (\det(\mathbf{B}))^2\) 因此， \(\det(\mathcal{L}) = \sqrt{\det(\mathbf{G})} = \sqrt{\det(\mathbf{B}^T \mathbf{B})}\)

定义 1.2 (对偶格)#

给定 \(\mathbb{R}^n\) 中的格 \(\mathcal{L}\)，其 对偶格 (Dual Lattice) \(\mathcal{L}^*\) 定义为： \(\mathcal{L}^* = \{ \mathbf{y} \in \text{span}(\mathcal{L}) \mid \forall \mathbf{x} \in \mathcal{L}, \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z} \}\) 其中 \(\text{span}(\mathcal{L})\) 是由格 \(\mathcal{L}\) 中向量张成的子空间（对于满秩格，即 \(\mathbb{R}^n\)），\(\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^T \mathbf{y}\) 是标准内积。 对偶格包含所有与原格中所有向量的内积均为整数的向量。

性质：

1. 对偶格也是一个格: 如果 \(\mathcal{L}\) 是一个格，那么 \(\mathcal{L}^*\) 也是一个格。
2. 对偶格的基: 如果 \(\mathbf{B}\) 是格 \(\mathcal{L}\) 的一组基（基矩阵），那么 \(\mathcal{L}^*\) 的一组基由矩阵 \((\mathbf{B}^T)^{-1}\) 的列向量给出。（注意：这里假设 \(\mathbf{B}\) 是方阵，即满秩格。如果不是满秩，需要使用伪逆）。 更准确地说，如果 \(\mathbf{B} = [\mathbf{b}_1, \dots, \mathbf{b}_n]\)，设 \(\mathbf{B}^* = (\mathbf{B}^T)^{-1} = [\mathbf{b}^*_1, \dots, \mathbf{b}^*_n]\)，则 \(\{\mathbf{b}^*_1, \dots, \mathbf{b}^*_n\}\) 是 \(\mathcal{L}^*\) 的一组基，且满足 \(\langle \mathbf{b}_i, \mathbf{b}^*_j \rangle = \delta_{ij}\) (Kronecker delta)。这组基有时被称为 对偶基 (Dual basis) (注意与 Gram-Schmidt 正交化中的向量符号区别，上下文会明确)。
3. 行列式关系: 对偶格的行列式与原格的行列式互为倒数： \(\det(\mathcal{L}^*) = \frac{1}{\det(\mathcal{L})}\) 这是因为 \(\det(\mathbf{B}^*) = \det((\mathbf{B}^T)^{-1}) = (\det(\mathbf{B}^T))^{-1} = (\det(\mathbf{B}))^{-1}\)。
4. 对偶的对偶: 对偶格的对偶是原格：\((\mathcal{L}^*)^* = \mathcal{L}\)。
5. 包含关系: 整数格 \(\mathbb{Z}^n\) 是自对偶的，即 \((\mathbb{Z}^n)^* = \mathbb{Z}^n\)。

示例:#

回到之前的二维格 \(\mathcal{L}\)，基矩阵 \(\mathbf{B} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}\)。 \(\mathbf{B}^T = \begin{pmatrix} 2 & 0 \\ 1 & 1 \end{pmatrix}\)。 \((\mathbf{B}^T)^{-1} = \frac{1}{2 \times 1 - 0 \times 1} \begin{pmatrix} 1 & 0 \\ -1 & 2 \end{pmatrix} = \begin{pmatrix} 1/2 & 0 \\ -1/2 & 1 \end{pmatrix}\)。 所以，对偶格 \(\mathcal{L}^*\) 的一组基是 \(\mathbf{b}^*_1 = (1/2, -1/2)^T\) 和 \(\mathbf{b}^*_2 = (0, 1)^T\)。 \(\det(\mathcal{L}) = |\det(\mathbf{B})| = |2 \times 1 - 1 \times 0| = 2\)。 \(\det(\mathcal{L}^*) = |\det((\mathbf{B}^T)^{-1})| = |(1/2) \times 1 - 0 \times (-1/2)| = 1/2\)。验证了 \(\det(\mathcal{L}^*) = 1/\det(\mathcal{L})\)。

定理 1.2 (Minkowski 第一定理 / 凸体定理)#

令 \(\mathcal{L}\) 为 \(\mathbb{R}^n\) 中的一个满秩格，其行列式为 \(\det(\mathcal{L})\)。令 \(S \subset \mathbb{R}^n\) 是一个 中心对称、凸 的集合。如果 \(S\) 的体积满足： \(\text{vol}(S) > 2^n \det(\mathcal{L})\) 那么 \(S\) 必定包含至少一个 非零 的格点 \(\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}\)。

如果 \(S\) 是紧集（有界闭集），则条件可以放宽为 \(\text{vol}(S) \ge 2^n \det(\mathcal{L})\)。

几何直观： 这个定理说，如果一个中心对称的凸体“足够大”（体积超过 \(2^n\) 倍的基本单元体积），那么它必然会“抓住”除了原点之外的至少一个格点。想象一下，把这个凸体放在原点，如果它太大，就无法避免碰到周围的某个格点。

证明思路 (Blichfeldt 定理):#

Minkowski 定理的一个常见证明依赖于 Blichfeldt 定理：

• Blichfeldt 定理: 令 \(\mathcal{L}\) 为 \(\mathbb{R}^n\) 中的满秩格。令 \(M \subset \mathbb{R}^n\) 是任意可测集。如果 \(\text{vol}(M) > \det(\mathcal{L})\)，则存在两个不同的点 \(\mathbf{x}, \mathbf{y} \in M\) 使得 \(\mathbf{x} - \mathbf{y} \in \mathcal{L}\)。
• 从 Blichfeldt 到 Minkowski: 考虑集合 \(S' = \frac{1}{2} S = \{ \mathbf{x}/2 \mid \mathbf{x} \in S \}\)。由于 \(S\) 是中心对称凸集，如果 \(\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}\) 且 \(\mathbf{v} \in S\)，那么 \(\mathbf{v}/2 \in S'\) 且 \(-\mathbf{v}/2 \in S'\)。 \(\text{vol}(S') = \text{vol}(S) / 2^n\)。如果 \(\text{vol}(S) > 2^n \det(\mathcal{L})\)，则 \(\text{vol}(S') > \det(\mathcal{L})\)。根据 Blichfeldt 定理，存在两个不同的点 \(\mathbf{x}', \mathbf{y}' \in S'\) 使得 \(\mathbf{v} = \mathbf{x}' - \mathbf{y}' \in \mathcal{L}\)，且 \(\mathbf{v} \neq \mathbf{0}\)。 因为 \(\mathbf{x}', \mathbf{y}' \in S' = \frac{1}{2} S\)，所以 \(2\mathbf{x}', 2\mathbf{y}' \in S\)。由于 \(S\) 是凸集，且中心对称（所以 \(-\mathbf{y}' = (-1)\mathbf{y}' \in S'\)，即 \(-(2\mathbf{y}') \in S\)），那么 \(\mathbf{v} = \mathbf{x}' - \mathbf{y}' = \frac{1}{2} (2\mathbf{x}') + \frac{1}{2} (-2\mathbf{y}')\)。因为 \(2\mathbf{x}' \in S\) 且 \(-2\mathbf{y}' \in S\)，并且 \(S\) 是凸集，所以 \(\mathbf{v} = \frac{1}{2} (2\mathbf{x}') + \frac{1}{2} (-2\mathbf{y}')\) 也必须在 \(S\) 中。 因此，我们找到了一个非零格点 \(\mathbf{v} \in S\)。

Minkowski 定理的应用：最短向量长度的上界#

Minkowski 定理的一个重要推论是，它为格中最短非零向量的长度提供了一个上界。考虑一个以原点为中心的 \(n\) 维球 \(B_r = \{ \mathbf{x} \in \mathbb{R}^n \mid ||\mathbf{x}|| \le r \}\)，其半径为 \(r\)。这是一个中心对称的凸集。其体积为 \(\text{vol}(B_r) = V_n r^n\)，其中 \(V_n = \frac{\pi^{n/2}}{\Gamma(n/2 + 1)}\) 是 \(n\) 维单位球的体积（\(\Gamma\) 是 Gamma 函数）。

根据 Minkowski 定理，如果 \(\text{vol}(B_r) \ge 2^n \det(\mathcal{L})\)，则球 \(B_r\) 内必然包含一个非零格点。我们想找到满足这个条件的最小半径 \(r\)。 令 \(\lambda_1(\mathcal{L})\) 表示格 \(\mathcal{L}\) 中最短非零向量的长度： \(\lambda_1(\mathcal{L}) = \min \{ ||\mathbf{v}|| \mid \mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\} \}\) 那么，存在一个非零格点 \(\mathbf{v}\) 使得 \(||\mathbf{v}|| \le r\)，只要 \(V_n r^n \ge 2^n \det(\mathcal{L})\)。 这给出了 \(\lambda_1(\mathcal{L})\) 的一个上界： \(\lambda_1(\mathcal{L}) \le \left( \frac{2^n \det(\mathcal{L})}{V_n} \right)^{1/n}\) 使用 Stirling 公式近似 \(\Gamma\) 函数，可以得到 \(V_n^{1/n} \approx \sqrt{\frac{2\pi e}{n}}\) 当 \(n\) 较大时。代入可得： \(\lambda_1(\mathcal{L}) \lesssim \sqrt{\frac{n}{2\pi e}} \cdot 2 \cdot (\det(\mathcal{L}))^{1/n}\) 更简洁（但常数稍差）的界是 Hermite 常数 \(\gamma_n\)： Minkowski 定理保证了 \(\lambda_1(\mathcal{L}) \le \sqrt{\gamma_n} (\det(\mathcal{L}))^{1/n}\)，其中 \(\gamma_n\) 是 Hermite 常数。已知 \(\gamma_n \le n\) (一个简单的界)，并且有更紧的界如 \(\gamma_n \approx n / (\pi e)\)。 这通常被简化为： \(\lambda_1(\mathcal{L}) \le \sqrt{n} (\det(\mathcal{L}))^{1/n}\) 这个结果至关重要：它保证了任何 \(n\) 维格中都存在一个长度不超过 \(\sqrt{n} (\det(\mathcal{L}))^{1/n}\) 的非零向量。虽然这个界不一定是紧的，但它确立了最短向量长度与格的维度和行列式之间的基本关系。寻找这个最短向量（或近似短的向量）正是格理论核心问题之一。

Minkowski 第二定理 (逐次最小)#

Minkowski 还证明了关于格中线性无关向量长度的更强的结果。定义 逐次最小 (Successive Minima) \(\lambda_1, \lambda_2, \dots, \lambda_n\) 如下：

• \(\lambda_1 = \min \{ ||\mathbf{v}|| \mid \mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\} \}\)
• \(\lambda_k = \min \{ r \mid \exists \mathbf{v}_1, \dots, \mathbf{v}_k \in \mathcal{L} \text{ linearly independent s.t. } ||\mathbf{v}_i|| \le r \text{ for } i=1,\dots,k \}\) 即 \(\lambda_k\) 是最小的半径 \(r\)，使得以原点为中心、半径为 \(r\) 的闭球包含 \(k\) 个线性无关的格向量。显然 \(\lambda_1 \le \lambda_2 \le \dots \le \lambda_n\)。

定理 1.3 (Minkowski 第二定理)#

对于 \(\mathbb{R}^n\) 中的满秩格 \(\mathcal{L}\) 及其逐次最小 \(\lambda_1, \dots, \lambda_n\)，有： \(\left( \prod_{i=1}^n \lambda_i \right)^{1/n} \le \sqrt{\gamma_n} (\det(\mathcal{L}))^{1/n}\) 并且 \(\frac{2^n \det(\mathcal{L})}{V_n} \le \prod_{i=1}^n \lambda_i \le \frac{(2^n n!) \det(\mathcal{L})}{V_n^n}\) 一个更常用的形式是（结合 \(\lambda_1\) 的界）： \(\frac{(\det(\mathcal{L}))^{1/n}}{\sqrt{n}} \lesssim \lambda_1 \quad \text{and} \quad \prod_{i=1}^n \lambda_i \approx (\det(\mathcal{L}))\) (这里的 \(\approx\) 忽略了 \(n\) 的次指数因子)。 这个定理更深刻地揭示了格的几何结构与行列式之间的关系，它表明 \(n\) 个线性无关的“短”向量的长度乘积与格的行列式密切相关。

本章介绍了格的基本概念，为后续讨论格上的困难问题和解决这些问题的算法奠定了基础。理解格的定义、基、行列式、对偶格以及 Minkowski 定理提供的最短向量存在性保证，是掌握格算法的关键第一步。

定义 2.1 (最短向量问题 SVP - 精确版)#

给定格 \(\mathcal{L}\) 的一组基 \(\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}\)，找到一个非零向量 \(\mathbf{v} \in \mathcal{L}\)，使得对于所有其他非零向量 \(\mathbf{w} \in \mathcal{L} \setminus \{\mathbf{0}\}\)，都有 \(||\mathbf{v}|| \le ||\mathbf{w}||\)。 这个向量 \(\mathbf{v}\) 的长度 \(||\mathbf{v}||\) 就是第一逐次最小 \(\lambda_1(\mathcal{L})\)。

几何直观： 在由格点构成的离散点阵中，找到离原点最近的那个点（除了原点自身）。

计算复杂性：

• NP-hard: Ajtai 在 1998 年证明了精确 SVP 在随机归约下是 NP-hard 的 [Ajtai98]。这意味着在标准计算复杂性假设下（如 P ≠ NP），不存在多项式时间的算法能保证解决任意格的精确 SVP 问题。
• 近似版本 (Approximate SVP, \(\gamma\)-SVP): 由于精确 SVP 的困难性，研究者们也关注其近似版本。

定义 2.2 (\(\gamma\)-SVP)#

给定格 \(\mathcal{L}\) 的基 \(\mathbf{B}\) 和一个近似因子 \(\gamma \ge 1\) (可以是关于维度 \(n\) 的函数)，找到一个非零向量 \(\mathbf{v} \in \mathcal{L}\) 使得： \(||\mathbf{v}|| \le \gamma \cdot \lambda_1(\mathcal{L})\) 其中 \(\lambda_1(\mathcal{L})\) 是格 \(\mathcal{L}\) 中最短非零向量的真实长度。

• 近似 SVP 的复杂性：
  • NP-hard for small \(\gamma\): 对于某些小的常数近似因子 \(\gamma\)（例如 \(\gamma < \sqrt{2}\)），\(\gamma\)-SVP 仍然是 NP-hard 的 [Micciancio01]。
  • Hardness for larger \(\gamma\): Micciancio (1998) 证明了对于任何常数 \(\gamma\)，\(\gamma\)-SVP 都是 NP-hard 的。进一步地，Khôt (2005) 证明了除非 NP \(\subseteq\) coAM，否则 \(\gamma\)-SVP 对于 \(\gamma = 2^{(\log n)^{1/2-\epsilon}}\) 也是困难的，这里 \(\epsilon > 0\)。这表明即使是近似因子接近多项式的 SVP 也是困难的。
  • GapSVP: 区分“\(\lambda_1 \le 1\)”和“\(\lambda_1 \ge \gamma\)”的判定问题（称为 GapSVP\(_\gamma\)）被认为与 \(\gamma\)-SVP 的搜索版本难度相当。GapSVP 的困难性是许多格密码安全证明的基础。
  • 多项式时间可解 for large \(\gamma\): 另一方面，当近似因子 \(\gamma\) 非常大时，\(\gamma\)-SVP 问题可以在多项式时间内解决。例如，LLL 算法（将在下一章详细介绍）可以在多项式时间内找到一个向量 \(\mathbf{v}\) 满足 \(||\mathbf{v}|| \le 2^{(n-1)/2} \lambda_1(\mathcal{L})\)。这里的近似因子 \(\gamma = 2^{O(n)}\) 是指数级的。改进的算法如 BKZ 可以达到次指数级或更小的指数级近似因子，但时间复杂度会相应增加。

SVP 的重要性： SVP 不仅是格理论的自然基础问题，其困难性假设也是许多格密码体制（尤其是基于 LWE 问题的体制的安全归约）的基石。同时，求解 SVP（即使是近似版本）的能力直接关系到格基约化算法的质量。

定义 2.3 (最近向量问题 CVP - 精确版)#

给定格 \(\mathcal{L}\) 的一组基 \(\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 和一个目标向量 \(\mathbf{t} \in \mathbb{R}^n\) (通常 \(\mathbf{t}\) 不在格 \(\mathcal{L}\) 中)，找到一个格向量 \(\mathbf{v} \in \mathcal{L}\)，使得对于所有其他格向量 \(\mathbf{w} \in \mathcal{L}\)，都有 \(||\mathbf{t} - \mathbf{v}|| \le ||\mathbf{t} - \mathbf{w}||\)。 这个最小距离 \(\min_{\mathbf{w} \in \mathcal{L}} ||\mathbf{t} - \mathbf{w}||\) 称为 \(\mathbf{t}\) 到格 \(\mathcal{L}\) 的距离，记作 \(\text{dist}(\mathbf{t}, \mathcal{L})\)。

几何直观： 在空间中给定一个点 \(\mathbf{t}\)，在由格点构成的离散点阵中，找到离 \(\mathbf{t}\) 最近的那个格点。

计算复杂性：

• NP-hard: CVP 被证明是 NP-hard 的 [vanEmdeBoas81]。事实上，CVP 被认为是比 SVP 更难的问题。许多 SVP 的困难性结果都是通过归约到 CVP 来证明的。
• 近似版本 (Approximate CVP, \(\gamma\)-CVP):

定义 2.4 (\(\gamma\)-CVP)#

给定格 \(\mathcal{L}\) 的基 \(\mathbf{B}\)，目标向量 \(\mathbf{t}\)，以及近似因子 \(\gamma \ge 1\)，找到一个格向量 \(\mathbf{v} \in \mathcal{L}\) 使得： \(||\mathbf{t} - \mathbf{v}|| \le \gamma \cdot \text{dist}(\mathbf{t}, \mathcal{L})\) 其中 \(\text{dist}(\mathbf{t}, \mathcal{L}) = \min_{\mathbf{w} \in \mathcal{L}} ||\mathbf{t} - \mathbf{w}||\) 是 \(\mathbf{t}\) 到格 \(\mathcal{L}\) 的真实最小距离。

• 近似 CVP 的复杂性:
  • NP-hard for any constant \(\gamma\): \(\gamma\)-CVP 对于任何常数 \(\gamma \ge 1\) 都是 NP-hard 的 [AroraEtAl97]。
  • Hardness for polynomial \(\gamma\): Dinur et al. (1998) 证明了除非 P = NP，否则 CVP 不能在多项式时间内以 \(n^{c/\log\log n}\) 的因子近似 (对于某个常数 \(c>0\))。这表明即使是多项式因子的近似 CVP 也非常困难。
  • 多项式时间可解 for large \(\gamma\): 类似于 SVP，当近似因子 \(\gamma\) 足够大时（例如指数级 \(\gamma = 2^{O(n)}\)），\(\gamma\)-CVP 问题可以在多项式时间内解决。Babai 的最近顶点算法 (Nearest Plane algorithm) [Babai86] 就是一个例子，它利用 LLL 约化基可以在多项式时间内找到一个近似解。

SVP 与 CVP 的关系：

• CVP 至少和 SVP 一样难: Kannan (1987) 展示了如何通过一个 CVP 预言机 (oracle) 来解决 SVP。这意味着如果 CVP 能被高效解决，SVP 也能。其基本思想是，对于一个格 \(\mathcal{L}\)，考虑目标向量 \(\mathbf{t} = \mathbf{v}/2\)，其中 \(\mathbf{v}\) 是 \(\mathcal{L}\) 中的一个非零向量。如果能找到离 \(\mathbf{t}\) 最近的格向量 \(\mathbf{w}\)，那么 \(\mathbf{w}\) 可能是 \(\mathbf{0}\) 或 \(\mathbf{v}\)。通过对格中足够多的向量重复这个过程，可以找到最短向量。
• 嵌入技术: 另一种常见的联系是将 SVP 归约为 CVP。可以在 \(n+1\) 维空间中构造一个新格 \(\mathcal{L}'\)，使得 \(\mathcal{L}'\) 上的 CVP 解能够给出原格 \(\mathcal{L}\) 的 SVP 解。例如，Goldreich et al. [GGH97] 展示了这种归约。

CVP 的应用： CVP 在许多领域都有应用，包括：

• 编码理论: 寻找给定接收信号最接近的码字（最大似然解码）。
• 整数规划: 某些整数规划问题可以转化为 CVP。
• 密码学:
  • 分析某些密码系统，例如 GGH 公钥密码系统直接基于 CVP 的困难性（尽管该系统已被证明不安全）。
  • 在 LWE 问题的解决中，如果知道错误向量足够小，LWE 可以看作是一个 CVP 问题（寻找离带噪测量值最近的格点）。

定义 2.5 (最短独立向量问题 SIVP)#

给定格 \(\mathcal{L}\) 的一组基 \(\mathbf{B}\) (维度为 \(n\))，找到 \(n\) 个线性无关的格向量 \(\mathbf{v}_1, \dots, \mathbf{v}_n \in \mathcal{L}\)，使得它们的最大长度 \(\max_{i=1}^n ||\mathbf{v}_i||\) 尽可能小。这个最小值等于第 \(n\) 逐次最小 \(\lambda_n(\mathcal{L})\)。

近似版本 (\(\gamma\)-SIVP): 找到 \(n\) 个线性无关的格向量 \(\mathbf{v}_1, \dots, \mathbf{v}_n\)，使得 \(\max_i ||\mathbf{v}_i|| \le \gamma \cdot \lambda_n(\mathcal{L})\)。

复杂性：

• SIVP 至少和 SVP 一样难，因为最短向量 \(\mathbf{v}_1\) (对应 \(\lambda_1\)) 是 \(n\) 个最短独立向量中的一个（或者可以替换其中一个而不增加最大长度，因为 \(\lambda_1 \le \lambda_n\))。
• 精确 SIVP 也是 NP-hard 的。
• 近似 SIVP 的困难性与 SVP 类似，但有时安全证明更倾向于基于 SIVP 假设，因为它考虑了整个格的几何结构（由 \(n\) 个独立方向决定），而不仅仅是最短的那个方向。基于 SIS (Short Integer Solution) 问题的密码系统安全性通常与 SIVP 相关。

与 SVP 的关系： 由 Minkowski 第二定理，我们知道 \(\lambda_1 \le \lambda_n\)。Blichfeldt 和 van der Waerden 证明了 \(\lambda_n / \lambda_1 \le n\)。这表明 \(\lambda_n\) 最多比 \(\lambda_1\) 大 \(n\) 倍。因此，SVP 和 SIVP 的近似因子在多项式级别上是相关的。然而，在精确或小因子近似的情况下，它们可能有不同的难度。

定义 2.6 (有界距离解码问题 BDD\(_{d}\))#

给定格 \(\mathcal{L}\) 的基 \(\mathbf{B}\)，一个目标向量 \(\mathbf{t} \in \mathbb{R}^n\)，以及一个距离界限 \(d\)。如果 保证 \(\text{dist}(\mathbf{t}, \mathcal{L}) \le d\)，则找到唯一的格向量 \(\mathbf{v} \in \mathcal{L}\) 使得 \(||\mathbf{t} - \mathbf{v}|| \le d\)。

通常，这个距离界限 \(d\) 会取得比较小，例如 \(d < \lambda_1(\mathcal{L}) / 2\)。在这种情况下，如果存在一个格点 \(\mathbf{v}\) 使得 \(||\mathbf{t} - \mathbf{v}|| \le d\)，那么这个格点是唯一的。因为如果存在另一个格点 \(\mathbf{w} \neq \mathbf{v}\) 也满足 \(||\mathbf{t} - \mathbf{w}|| \le d\)，则根据三角不等式： \(||\mathbf{v} - \mathbf{w}|| = ||(\mathbf{v} - \mathbf{t}) + (\mathbf{t} - \mathbf{w})|| \le ||\mathbf{v} - \mathbf{t}|| + ||\mathbf{t} - \mathbf{w}|| \le d + d = 2d\) 由于 \(\mathbf{v}, \mathbf{w} \in \mathcal{L}\) 且 \(\mathbf{v} \neq \mathbf{w}\)，所以 \(\mathbf{v} - \mathbf{w}\) 是一个非零格向量。因此 \(||\mathbf{v} - \mathbf{w}|| \ge \lambda_1(\mathcal{L})\)。 结合起来，我们得到 \(\lambda_1(\mathcal{L}) \le 2d\)。这与我们选择的 \(d < \lambda_1(\mathcal{L}) / 2\) 矛盾。因此，满足条件的格点 \(\mathbf{v}\) 是唯一的。

复杂性：

• BDD 通常被认为比一般 CVP 简单，但也依赖于距离界限 \(d\) 的大小。
• 如果 \(d\) 非常小（例如 \(d\) 是关于 \(n\) 的某个负指数函数），BDD 可能相对容易。Babai 的最近顶点算法可以在多项式时间内解决 BDD 问题，只要 \(d\) 相对于 LLL 算法能找到的向量长度足够小。
• BDD 问题与 LWE (Learning With Errors) 问题密切相关。在 LWE 中，目标是找到一个秘密向量 \(\mathbf{s}\)，给定形如 \(\mathbf{a}_i^T \mathbf{s} + e_i \approx b_i \pmod q\) 的样本。这可以转化为一个格上的 CVP/BDD 问题，其中错误项 \(e_i\) 构成的向量 \(\mathbf{e}\) 使得目标向量 \((\mathbf{b} - \mathbf{A}\mathbf{s})\) （在某个格中）非常接近零向量，或者说 \(\mathbf{b}\) 接近格点 \(\mathbf{A}\mathbf{s}\)，且距离（由 \(\mathbf{e}\) 决定）有界。如果错误分布足够集中（即距离界限 \(d\) 足够小），则可能通过解决 BDD 来恢复秘密 \(\mathbf{s}\)。

格基约化 (Lattice Basis Reduction) 的目标#

回顾第一章，我们知道同一个格可以由无穷多组不同的基来表示。然而，不同的基在计算上可能有天壤之别。考虑一个二维格，由以下两个基生成：

• 基 1: \(\mathbf{b}_1 = (1, 0)^T, \mathbf{b}_2 = (0, 1)^T\)。这是 \(\mathbb{Z}^2\) 格的标准基。基向量短，且相互正交。
• 基 2: \(\mathbf{b}'_1 = (1, 0)^T, \mathbf{b}'_2 = (N, 1)^T\)，其中 \(N\) 是一个非常大的整数。这个基生成的格与基 1 相同（因为 \(\begin{pmatrix} 1 & N \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & N \\ 0 & 1 \end{pmatrix}\)，且变换矩阵 \(\begin{pmatrix} 1 & N \\ 0 & 1 \end{pmatrix}\) 是幺模矩阵，行列式为 1）。但是，基 2 中的向量 \(\mathbf{b}'_2\) 非常长，而且 \(\mathbf{b}'_1\) 和 \(\mathbf{b}'_2\) 之间的夹角非常小（接近线性相关）。

使用像基 2 这样的“坏”基，可能会给计算带来麻烦：

• 基向量本身可能非常长，难以处理。
• 基向量之间近似线性相关，使得数值计算不稳定。
• 基于这样的基进行搜索（例如搜索短向量或最近向量）可能会非常低效。

格基约化的目标 就是要找到一个给定格 \(\mathcal{L}\) 的“好”的基 \(\mathbf{B}' = \{\mathbf{b}'_1, \dots, \mathbf{b}'_n\}\)。什么样的基算是“好”的呢？通常我们希望基满足以下性质：

1. 向量长度较短 (Shortness): 基向量本身的长度 \(||\mathbf{b}'_i||\) 应该相对较小。特别是，第一个基向量 \(\mathbf{b}'_1\) 应该接近格中最短的非零向量。
2. 近似正交 (Near Orthogonality): 基向量之间应该尽可能地接近正交。完全正交的基只在某些特殊格中存在，但我们希望基向量之间的“倾斜程度”不要太大。

一个满足这些条件的基称为 约化基 (Reduced Basis)。LLL 算法就是一种寻找约化基的算法，它定义的“好”基具有明确的数学性质（即 LLL 约化条件），并且该算法能在多项式时间内完成。

在 LLL 算法之前，也存在其他的格基约化方法，例如 Lagrange 算法（二维）和 Hermite-Korkine-Zolotarev (HKZ) 约化，但它们要么只适用于低维，要么计算复杂度很高（指数级）。LLL 算法的突破在于它在 任意维度 上实现了 多项式时间 的约化，尽管其输出的基的质量（向量长度和正交性）可能不如 HKZ 约化。

1. 尺寸约化条件 (Size Reduction Condition):#

对于所有的 \(1 \le j < i \le n\)，要求 GSO 系数满足： \(|\mu_{ij}| = \left| \frac{\langle \mathbf{b}_i, \mathbf{b}^*_j \rangle}{||\mathbf{b}^*_j||^2} \right| \le \frac{1}{2}\) 几何意义： 回忆 \(\mathbf{b}_i = \mathbf{b}^*_i + \sum_{j=1}^{i-1} \mu_{ij} \mathbf{b}^*_j\)。这个条件要求 \(\mathbf{b}_i\) 在每个 \(\mathbf{b}^*_j\) (\(j<i\)) 方向上的投影系数绝对值不超过 1/2。这意味着 \(\mathbf{b}_i\) 相对其 GSO 分量 \(\mathbf{b}^*_i\) 而言，在与 \(\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})\) 平行的方向上没有“过长”的分量。如果某个 \(|\mu_{ij}| > 1/2\)，我们可以通过从 \(\mathbf{b}_i\) 中减去 \(\mathbf{b}_j\) 的整数倍来减小这个系数，而不改变格本身。具体操作是：令 \(r = \text{round}(\mu_{ij})\)（取最接近 \(\mu_{ij}\) 的整数），然后更新 \(\mathbf{b}_i \leftarrow \mathbf{b}_i - r \mathbf{b}_j\)。这个操作会改变 \(\mu_{ik}\) (其中 \(k<j\)) 的值，但会使得新的 \(\mu_{ij}\) 满足 \(|\mu_{ij}| \le 1/2\)，并且不影响 \(\mathbf{b}^*_1, \dots, \mathbf{b}^*_i\)（因为 \(\mathbf{b}_j\) 在 \(\text{span}(\mathbf{b}^*_1, \dots, \mathbf{b}^*_{j})\) 内，而 \(\mathbf{b}^*_i\) 与这个子空间正交）。

2. Lovász 条件 (Lovász Condition):#

引入一个参数 \(\delta\)，通常取 \(1/4 < \delta \le 1\)。最常用的值是 \(\delta = 3/4\)。Lovász 条件要求对于所有的 \(i = 2, \dots, n\)： \(||\mathbf{b}^*_i||^2 \ge \left(\delta - \mu_{i, i-1}^2\right) ||\mathbf{b}^*_{i-1}||^2\) 几何意义： 这个条件限制了相邻 GSO 向量长度的下降速度。考虑 \(\mathbf{b}_i\) 在 \(\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})\) 上的投影。它的主要分量是 \(\mu_{i, i-1} \mathbf{b}^*_{i-1}\)（如果尺寸约化已完成，其他 \(\mu_{ij}\) 较小）。\(\mathbf{b}_i\) 可以近似看作 \(\mathbf{b}^*_i + \mu_{i, i-1} \mathbf{b}^*_{i-1}\)（加上其他方向的小分量）。Lovász 条件实际上是在比较 \(\mathbf{b}_i\) 投影到 \(\text{span}(\mathbf{b}^*_1, \dots, \mathbf{b}^*_i)\) 后与 \(\mathbf{b}_{i-1}\) 投影到 \(\text{span}(\mathbf{b}^*_1, \dots, \mathbf{b}^*_{i-1})\) 后的长度关系。 将 \(\mathbf{b}_i\) 在 \(\text{span}(\mathbf{b}_{i-1}, \mathbf{b}^*_i)\) 子空间中的投影记为 \(\text{proj}_{i-1}(\mathbf{b}_i) = \mu_{i,i-1}\mathbf{b}^*_{i-1} + \mathbf{b}^*_i\)。它的长度平方是 \(||\mu_{i,i-1}\mathbf{b}^*_{i-1} + \mathbf{b}^*_i||^2 = \mu_{i,i-1}^2 ||\mathbf{b}^*_{i-1}||^2 + ||\mathbf{b}^*_i||^2\) (因为 \(\mathbf{b}^*_{i-1}\) 和 \(\mathbf{b}^*_i\) 正交)。 Lovász 条件 \(\delta ||\mathbf{b}^*_{i-1}||^2 \le \mu_{i, i-1}^2 ||\mathbf{b}^*_{i-1}||^2 + ||\mathbf{b}^*_i||^2\) (使用书中原始形式 \(\delta ||\mathbf{b}^*_{i-1}||^2 \le ||\mathbf{b}^*_i + \mu_{i,i-1} \mathbf{b}^*_{i-1}||^2\)) 可以重新写作： \(||\mathbf{b}^*_i||^2 \ge (\delta - \mu_{i, i-1}^2) ||\mathbf{b}^*_{i-1}||^2\) 如果这个条件 不满足，意味着 \(\mathbf{b}^*_i\) 相对于 \(\mathbf{b}^*_{i-1}\) 来说“太短”了。直观上，这意味着 \(\mathbf{b}_i\) 比 \(\mathbf{b}_{i-1}\) 更能提供一个“更短”的正交方向。在这种情况下，LLL 算法会 交换 (swap) \(\mathbf{b}_{i-1}\) 和 \(\mathbf{b}_i\)。这个交换操作会改变 GSO 向量 \(\mathbf{b}^*_{i-1}\) 和 \(\mathbf{b}^*_i\) 以及相关的 \(\mu\) 系数，但目的是让 GSO 向量的长度更平稳地下降（或不下降）。 当 \(\delta=3/4\) 且尺寸约化条件满足 (\(|\mu_{i,i-1}| \le 1/2\)) 时，\(\delta - \mu_{i,i-1}^2 \ge 3/4 - (1/2)^2 = 3/4 - 1/4 = 1/2\)。所以 Lovász 条件隐含了 \(||\mathbf{b}^*_i||^2 \ge \frac{1}{2} ||\mathbf{b}^*_{i-1}||^2\)。这防止了 GSO 向量长度的急剧下降。

总结： 一个基是 LLL 约化的（对于参数 \(\delta\)），如果它满足尺寸约化条件，并且满足 Lovász 条件。LLL 算法就是通过不断执行尺寸约化和（在违反 Lovász 条件时）向量交换来最终达到这个状态的过程。

伪代码 (简化版):#

Algorithm LLL(B, delta)
Input: Basis B = {b1, ..., bn}, parameter delta in (1/4, 1]
Output: LLL-reduced basis B'

Compute initial GSO B* = {b1*, ..., bn*} and mu_ij for B
k = 2
while k <= n:
    // Step 2a: Size reduction for b_k
    for j from k-1 down to 1:
        mu_kj = <b_k, b_j*> / ||b_j*||^2  // (or get stored value)
        r = round(mu_kj)
        if r != 0:
            b_k = b_k - r * b_j
            // Update mu_kl for l < j if necessary (efficient updates exist)
            // Recompute mu_kj or update based on r

    // Step 2b: Check Lovász condition
    // Compute/update ||b_k*||^2, ||b_{k-1}*||^2, mu_{k, k-1}
    if delta * ||b_{k-1}*||^2 > ||b_k*||^2 + mu_{k, k-1}^2 * ||b_{k-1}*||^2 :
        // Swap b_{k-1} and b_k
        swap(b_{k-1}, b_k)
        // Update GSO information for indices k-1 and k (and relevant mu_ij)
        k = max(2, k - 1) // Go back to check the modified pair
    else:
        // Lovász condition holds, proceed to next vector
        k = k + 1

return B // The modified basis B is LLL-reduced

实现细节:

• GSO 计算与更新: 高效实现 LLL 的关键在于如何快速计算和更新 GSO 信息 (\(\mathbf{b}^*_i\) 的长度平方和 \(\mu_{ij}\) 系数)。完全重新计算 GSO 是低效的。存在 \(O(n)\) 或 \(O(n^2)\) 的更新步骤来处理尺寸约化和交换操作对 GSO 信息的影响。
• 数值精度: LLL 算法可以用浮点数实现，速度快但可能受精度问题影响。也可以用精确算术（有理数或大整数）实现，保证结果精确但速度较慢，且需要处理系数大小的增长。

一个低维 (n=2) 的手动计算示例:#

(此处省略手动计算过程，与原始文本相同) … 输出的 LLL 约化基: \(\mathbf{B}'' = \{\mathbf{b}''_1 = (0, 1)^T, \mathbf{b}''_2 = (1, 0)^T\}\)。 在这个例子中，LLL 算法找到了 \(\mathbb{Z}^2\) 的标准正交基。这是因为原格就是 \(\mathbb{Z}^2\)，而 LLL 算法倾向于找到短且近似正交的基。

1. 终止性 (Termination):#

LLL 算法保证在有限步内终止。证明的关键是构造一个“势函数”(potential function) \(D = \prod_{i=1}^n ||\mathbf{b}^*_i||^{2(n-i+1)} = ||\mathbf{b}^*_1||^{2n} ||\mathbf{b}^*_2||^{2(n-1)} \cdots ||\mathbf{b}^*_n||^2\)。可以证明：

• 尺寸约化 不改变 GSO 向量 \(\mathbf{b}^*_i\)，因此不改变 \(D\)。
• 交换操作 (当 Lovász 条件 \(\delta ||\mathbf{b}^*_{k-1}||^2 > ||\mathbf{b}^*_k||^2 + \mu_{k, k-1}^2 ||\mathbf{b}^*_{k-1}||^2\) 触发时) 会导致 \(D\) 的值 至少乘以一个因子 \(\delta\)。因为交换 \(\mathbf{b}_{k-1}, \mathbf{b}_k\) 后，新的 GSO 向量 \(\mathbf{b'}^*_{k-1}\) (它是 \(\mathbf{b}_k\) 在 \(\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_{k-2})\) 上的正交分量) 会等于 \(\mathbf{b}^*_k + \mu_{k, k-1} \mathbf{b}^*_{k-1}\)。而新的 \(\mathbf{b'}^*_k\) (它是 \(\mathbf{b}_{k-1}\) 在 \(\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_{k-2}, \mathbf{b'}^*_{k-1})\) 上的正交分量) 的长度平方是 \(||\mathbf{b'}^*_k||^2 = \frac{||\mathbf{b}^*_{k-1}||^2 ||\mathbf{b}^*_k||^2}{||\mathbf{b'}^*_{k-1}||^2}\)。 在交换前，势函数中涉及 \(k-1, k\) 的因子是 \(P_{old} = ||\mathbf{b}^*_{k-1}||^{2(n-k+2)} ||\mathbf{b}^*_k||^{2(n-k+1)}\)。 在交换后，对应因子是 \(P_{new} = ||\mathbf{b'}^*_{k-1}||^{2(n-k+2)} ||\mathbf{b'}^*_k||^{2(n-k+1)}\)。 使用 Lovász 条件和 GSO 向量变换关系，可以证明 \(P_{new} / P_{old} = ( ||\mathbf{b}^*_k||^2 + \mu_{k,k-1}^2 ||\mathbf{b}^*_{k-1}||^2 ) / ||\mathbf{b}^*_{k-1}||^2 < \delta\)。
• 由于 \(D\) 是正的，并且每次交换都使其至少乘以 \(\delta < 1\)，而格中的向量长度存在下界（例如，所有非零向量长度至少为 \(\lambda_1 > 0\)），这意味着 \(D\) 的值不能无限减小。因此，交换操作的次数是有限的。尺寸约化操作本身也是有限的（或者可以包含在交换的分析中）。所以整个算法必定终止。

2. 输出基的性质:#

LLL 算法产生的约化基 \(\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 具有以下重要性质 (设 \(\delta = 3/4\))：

• 第一个向量 \(\mathbf{b}_1\) 的长度上界 (与 SVP 的关系): 这是 LLL 最著名的成果之一。对于 LLL 约化基的第一个向量 \(\mathbf{b}_1\) (它也是 \(\mathbf{b}^*_1\))，有： \(||\mathbf{b}_1|| \le \alpha^{(n-1)/2} \lambda_1(\mathcal{L})\) 其中 \(\alpha = 1 / (\delta - 1/4)\)。当 \(\delta = 3/4\) 时，\(\alpha = 1 / (3/4 - 1/4) = 1 / (1/2) = 2\)。所以： \(||\mathbf{b}_1|| \le 2^{(n-1)/2} \lambda_1(\mathcal{L})\) 意义: LLL 算法在多项式时间内找到了一个非零格向量 \(\mathbf{b}_1\)，其长度与格中最短非零向量 \(\lambda_1(\mathcal{L})\) 的长度只差一个因子 \(2^{(n-1)/2}\)。这为 \(\gamma\)-SVP 问题提供了一个多项式时间的解，其中近似因子 \(\gamma = 2^{(n-1)/2}\) 是指数级的。虽然因子是指数的，但这在 LLL 之前是无法在多项式时间内保证的。这个结果表明 SVP 在指数因子近似下是“容易”的。

• 所有基向量的长度界: \(||\mathbf{b}_i|| \le 2^{(n-1)/2} \lambda_n(\mathcal{L}) \quad \text{for } i=1, \dots, n\) 这表明所有基向量的长度都受到最短独立向量组中最大长度 \(\lambda_n\) 的控制（带有指数因子）。

• 与行列式的关系: \(||\mathbf{b}_1|| \le 2^{(n-1)/4} (\det(\mathcal{L}))^{1/n}\) 这个界将找到的短向量长度与格的基本不变量——行列式和维度联系起来。它比 Minkowski 定理给出的界 \(\lambda_1 \le \sqrt{n} (\det(\mathcal{L}))^{1/n}\) 要弱（因为 \(2^{(n-1)/4}\) 通常比 \(\sqrt{n}\) 大），但 LLL 的优势在于它是 构造性 的（给出了找到 \(\mathbf{b}_1\) 的算法），而 Minkowski 定理只是存在性证明。

• 基向量乘积与行列式: \(\prod_{i=1}^n ||\mathbf{b}_i|| \le 2^{n(n-1)/4} \det(\mathcal{L})\) 这表明 LLL 约化基的向量长度乘积与格的行列式之间也存在关系，反映了基向量的“体积”不会比基本单元体积大太多（同样带有指数因子）。

• 近似正交性: LLL 约化基的 GSO 向量长度不会下降太快：\(||\mathbf{b}^*_i||^2 \ge \frac{1}{2} ||\mathbf{b}^*_{i-1}||^2\) (对于 \(\delta=3/4\) 且尺寸约化后)。这保证了基向量不会“几乎平行”。一个衡量基 \(\mathbf{B}\) 正交程度的指标是 Hadamard 比率： \(H(\mathbf{B}) = \left( \frac{\det(\mathcal{L})}{\prod_{i=1}^n ||\mathbf{b}_i||} \right)^{1/n}\) \(H(\mathbf{B})\) 的值在 0 和 1 之间，越接近 1 表示基越接近正交。对于 LLL 约化基，由上面的乘积界可知 \(H(\mathbf{B}) \ge (2^{-n(n-1)/4})^{1/n} = 2^{-(n-1)/4}\)。这提供了一个（指数级的）正交性下界。

3. 计算复杂性:#

LLL 算法的计算复杂性（使用经典整数算术）是 多项式时间 的。如果输入基向量 \(\mathbf{b}_i\) 的分量大小有界（例如，最大绝对值 \(M\)），则 LLL 算法的时间复杂度可以界定为： \(O(n^5 d \log^3 M)\) 其中 \(n\) 是格的维度，\(d\) 是嵌入维度 (通常 \(d=n\))，\(M\) 是输入基向量系数的最大绝对值的上界。 这个复杂度分析考虑了执行尺寸约化、交换操作的次数以及每次操作中涉及的算术运算（如内积、整数运算）的成本。使用浮点数可以更快，但分析更复杂且涉及精度问题。使用快速矩阵乘法等技术理论上可以降低复杂度的指数，但实际实现中上述界限比较常见。

关键点: 复杂性是关于 输入规模 (n, d, log M) 的多项式，这是 LLL 算法的核心理论贡献。

定义 4.1 (HKZ 约化基)#

一个格基 \(\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 称为 HKZ 约化基 (HKZ-reduced basis)，如果它满足以下条件：

1. 尺寸约化: \(|\mu_{ij}| \le 1/2\) 对所有 \(1 \le j < i \le n\)。
2. 递归最短向量条件: 对于每个 \(i = 1, \dots, n\)，令 \(\pi_i: \mathbb{R}^n \to \text{span}(\mathbf{b}^*_i, \dots, \mathbf{b}^*_n)\) 表示到 GSO 向量 \(\mathbf{b}^*_i, \dots, \mathbf{b}^*_n\) 张成的子空间的正交投影。要求 \(\pi_i(\mathbf{b}_i) = \mathbf{b}^*_i\) 是由格 \(\mathcal{L}_i = \pi_i(\mathcal{L})\) （即原格 \(\mathcal{L}\) 在该子空间上的投影格）中的最短非零向量。即，\(\mathbf{b}^*_i\) 是投影格 \(\mathcal{L}_i\) 的 \(\lambda_1\)。

HKZ 约化的性质：

• 第一个向量是最短的: HKZ 约化基的第一个向量 \(\mathbf{b}_1 = \mathbf{b}^*_1\) 就是原格 \(\mathcal{L}\) 中最短的非零向量，即 \(||\mathbf{b}_1|| = \lambda_1(\mathcal{L})\)。
• 非常好的性质: HKZ 基具有非常好的长度和正交性，比 LLL 基强得多。例如，可以证明 HKZ 基满足 \(\lambda_1(\mathcal{L})^2 \le \frac{4}{i+3} ||\mathbf{b}^*_i||^2\)。
• 计算困难: 找到一个 HKZ 约化基被认为是非常困难的，至少与解决精确 SVP 一样难。目前没有已知的多项式时间算法可以计算 HKZ 基。

既然完全的 HKZ 约化太难，人们自然想到一个折中的方法：不要求整个投影格都满足最短向量条件，而是只要求一个较小“块”内的投影格满足该条件。 这就是 BKZ 算法的核心思想。

定义 4.2 (BKZ-\(\beta\) 约化基)#

一个格基 \(\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 称为 BKZ-\(\beta\) 约化基 (BKZ-\(\beta\)-reduced basis) (对于参数 \(\delta\), 通常 \(\delta=1\) 或接近 1)，如果它满足：

1. 尺寸约化: \(|\mu_{ij}| \le 1/2\) 对所有 \(1 \le j < i \le n\)。
2. 块状 HKZ 条件: 对于所有的块索引 \(k = 1, \dots, n-\beta+1\)，考虑由基向量 \(\mathbf{b}_k, \dots, \mathbf{b}_{k+\beta-1}\) 相关的投影格。令 \(\mathcal{L}_{k, \beta} = \pi_k(\mathcal{L})\) 是格 \(\mathcal{L}\) 在由 GSO 基 \(\mathbf{b}^*_k, \dots, \mathbf{b}^*_n\) 张成的子空间上的投影格。要求 \(\mathbf{b}^*_k\) 是子格 \(\mathcal{L}'_{k, \beta}\) 中的最短非零向量（或近似最短，取决于 \(\delta\) 的选择），其中 \(\mathcal{L}'_{k, \beta}\) 是由 \(\pi_k(\mathbf{b}_k), \pi_k(\mathbf{b}_{k+1}), \dots, \pi_k(\mathbf{b}_{k+\beta-1})\) 生成的 秩为 \(\beta\) 的投影格。（这里 \(\pi_k\) 是到 \(\text{span}(\mathbf{b}_k^*, \dots, \mathbf{b}_n^*)\) 的投影）。 更具体地说，要求 GSO 向量 \(\mathbf{b}_k^*\) 的长度 \(||\mathbf{b}_k^*||\) 等于（或约等于，如果用 \(\delta < 1\)）投影格 \(\mathcal{L}_{k..k+\beta-1} = \text{span}_{\mathbb{Z}}\{\pi_k(\mathbf{b}_k), ..., \pi_k(\mathbf{b}_{k+\beta-1})\}\) 的第一逐次最小 \(\lambda_1(\mathcal{L}_{k..k+\beta-1})\)。

直观理解：

• BKZ-\(\beta\) 约化介于 LLL 约化和 HKZ 约化之间。
• 当 \(\beta=2\) 时，BKZ-2 约化等价于 LLL 约化（因为块状条件只涉及相邻的 \(\mathbf{b}^*_k, \mathbf{b}^*_{k+1}\)，这与 Lovász 条件相关）。
• 当 \(\beta=n\) 时，BKZ-\(n\) 约化等价于 HKZ 约化。
• 随着块大小 \(\beta\) 的增加，BKZ 约化基的质量（向量长度和正交性）期望越高，但计算成本也急剧增加。

BKZ 算法的目标 就是找到一个近似满足 BKZ-\(\beta\) 约化条件的基。它通过迭代处理不同的块，并利用一个 SVP 预言机 (SVP oracle) 来找到块内投影格的最短向量，然后用这个短向量来改进当前的基。

核心步骤：SVP 预言机#

BKZ 算法的性能和复杂度很大程度上取决于其内部使用的 SVP 预言机。

• 枚举 (Enumeration, Enum): 如 Kannan-Fincke-Pohst 算法。它在 \(\beta'\) 维空间中搜索一个椭球内的格点。其复杂度大致是 \(\beta'^{O(\beta')}\)（或 \(2^{O(\beta'^2)}\)，取决于变种和分析）。对于较小的 \(\beta\) (如 \(\beta \le 40-50\))，这是可行的。
• 筛法 (Sieving): 如 AKS 筛法、NV 筛法、Gauss Sieve 等。它们通过生成大量格点并两两相减来寻找短向量。其（启发式）时间复杂度大约是 \(2^{O(\beta')}\)，空间复杂度也很高。对于更大的 \(\beta\) (如 \(\beta \ge 50-60\))，筛法通常比枚举更快。

BKZ 的变种和实现策略:#

• BKZ 2.0: [CN11] 提出了 BKZ 2.0，通过更精细的分析和更强的 SVP 预言机（结合剪枝的枚举）改进了理论性能保证和实际效率。
• 启发式 BKZ: 许多实现采用启发式策略，例如：
  • 只在找到足够短的向量时才进行插入。
  • 不完全求解 SVP，而是找到足够多的短向量进行处理。
  • 动态调整块大小或 SVP 算法。
  • 使用“极值剪枝”(extreme pruning) 加速枚举。
• 与筛法结合: 现代高性能 BKZ 实现通常依赖于高效的筛法作为 SVP 预言机。

Kannan 算法 / Fincke-Pohst 算法 (用于 SVP):#

这些算法的核心思想基于以下观察：如果 \(\mathbf{v} = \sum_{i=1}^n c_i \mathbf{b}_i\) 是格 \(\mathcal{L}\) 中的一个向量（其中 \(\mathbf{B}=\{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) 是一个基，通常是经过 LLL 或 BKZ 预处理的），那么它的长度平方可以表示为关于系数 \(c_i\) 的二次型： \(||\mathbf{v}||^2 = ||\sum_{i=1}^n c_i \mathbf{b}_i||^2 = \mathbf{c}^T \mathbf{B}^T \mathbf{B} \mathbf{c} = \mathbf{c}^T \mathbf{G} \mathbf{c}\) 其中 \(\mathbf{c} = (c_1, \dots, c_n)^T\) 是整数系数向量，\(\mathbf{G}\) 是 Gram 矩阵。

如果我们使用 GSO 向量 \(\mathbf{b}^*_i\) 来表示 \(\mathbf{v}\)，可以得到更方便的形式。回忆 \(\mathbf{b}_i = \mathbf{b}^*_i + \sum_{j=1}^{i-1} \mu_{ij} \mathbf{b}^*_j\)。那么 \(\mathbf{v} = \sum_{i=1}^n c_i \mathbf{b}_i\) 可以重写为关于 GSO 基的线性组合（但系数不再是整数 \(c_i\))。 Kannan 的方法利用了 GSO 基的正交性。一个格向量 \(\mathbf{v} = \sum_{i=1}^n c_i \mathbf{b}_i\) 可以表示为 \(\mathbf{v} = \sum_{i=1}^n x_i \mathbf{b}^*_i\)，其中 \(x_i\) 是实数。可以证明 \(x_n = c_n\)，\(x_{n-1} = c_{n-1} + c_n \mu_{n, n-1}\)，依此类推，\(x_i = c_i + \sum_{j=i+1}^n c_j \mu_{j, i}\)。这是一个上三角关系，可以反解出整数 \(c_i\)。 \(||\mathbf{v}||^2 = ||\sum_{i=1}^n x_i \mathbf{b}^*_i||^2 = \sum_{i=1}^n x_i^2 ||\mathbf{b}^*_i||^2\) Kannan 的算法 (以及 Fincke-Pohst 的类似方法) 通过 递归地 枚举整数系数 \(c_n, c_{n-1}, \dots, c_1\) 来寻找满足 \(||\mathbf{v}||^2 \le R^2\) 的向量（\(R^2\) 是当前找到的最短向量长度平方的上界，初始可以设为 \(||\mathbf{b}_1||^2\) 或 Minkowski 界）。

枚举过程的核心思想 (以 Fincke-Pohst 为例):#

目标是找到整数 \(c_1, \dots, c_n\) 使得 \(\sum_{i=1}^n (c_i + \sum_{j=i+1}^n c_j \mu_{j, i})^2 ||\mathbf{b}^*_i||^2 \le R^2\)。 这是一个关于 \(c_n, \dots, c_1\) 的不等式。

1. 确定 \(c_n\) 的范围: 不等式可以写成 \(c_n^2 ||\mathbf{b}^*_n||^2 + \sum_{i=1}^{n-1} x_i^2 ||\mathbf{b}^*_i||^2 \le R^2\)。这意味着 \(c_n^2 ||\mathbf{b}^*_n||^2 \le R^2\)，所以 \(c_n\) 必须在区间 \([-\lfloor R / ||\mathbf{b}^*_n|| \rfloor, \lfloor R / ||\mathbf{b}^*_n|| \rfloor]\) 内。
2. 递归确定 \(c_{n-1}, \dots, c_1\): 对于每个可能的整数 \(c_n\)，将不等式重写为关于 \(c_{n-1}, \dots, c_1\) 的不等式：\(\sum_{i=1}^{n-1} (c_i + \sum_{j=i+1}^{n-1} c_j \mu_{j, i} + c_n \mu_{n, i})^2 ||\mathbf{b}^*_i||^2 \le R^2 - c_n^2 ||\mathbf{b}^*_n||^2\)。这可以看作是在 \(n-1\) 维空间中的一个类似问题，目标值变为 \(R_{new}^2 = R^2 - c_n^2 ||\mathbf{b}^*_n||^2\)。递归地枚举 \(c_{n-1}\) 的可能范围，然后是 \(c_{n-2}\)，依此类推，直到 \(c_1\)。
3. 搜索树: 这个过程可以看作是在一个搜索树上进行深度优先搜索。树的第 \(k\) 层对应于确定系数 \(c_{n-k+1}\)。

剪枝策略 (Pruning):#

枚举算法的效率关键在于 剪枝。在递归的每一步，我们可以根据当前已确定的系数 \(c_n, \dots, c_k\) 来计算部分长度平方 \(L_k = \sum_{i=k}^n x_i^2 ||\mathbf{b}^*_i||^2\)。如果 \(L_k > R^2\)，那么以当前系数开头的任何完整向量都不可能比当前最短向量更短，因此可以剪掉这个分支，不再继续搜索 \(c_{k-1}, \dots, c_1\)。 更强的剪枝技术（如 Gama-Nguyen-Regev 剪枝）利用了几何性质来更早地排除不可能的分支，显著提高了效率。

复杂度：

• 枚举算法的运行时间大致与搜索树中未被剪枝的节点数量成正比。
• 在最坏情况下，复杂度可能是指数级的，例如 \(n^{O(n)}\) 或 \(2^{O(n^2)}\)，取决于具体的算法变种和分析。
• 然而，如果输入基经过了高质量的预处理（如强 BKZ 约化），GSO 向量长度 \(||\mathbf{b}^*_i||\) 会比较均匀，使得搜索空间（系数 \(c_i\) 的范围）相对较小，剪枝效果也更好。
• 在实践中，对于经过强 BKZ 约化（例如 \(\beta \ge 50-70\)）的基，枚举算法可以在中等维度（如 \(n\) 达到 80-100 甚至更高，取决于具体问题和可用计算资源）内找到精确 SVP 解或非常高质量的近似解。
• 枚举算法通常被用作 BKZ 算法中求解块内 SVP 的预言机（对于中等块大小 \(\beta\)）。

枚举用于 CVP:#

枚举思想也可以用于解决 CVP。给定目标向量 \(\mathbf{t}\)，我们想找到格点 \(\mathbf{v} = \sum c_i \mathbf{b}_i\) 最小化 \(||\mathbf{t} - \mathbf{v}||^2\)。将 \(\mathbf{t}\) 用 GSO 基展开 \(\mathbf{t} = \sum t_i \mathbf{b}^*_i\)。那么 \(||\mathbf{t} - \mathbf{v}||^2 = ||\sum (t_i - x_i) \mathbf{b}^*_i||^2 = \sum (t_i - x_i)^2 ||\mathbf{b}^*_i||^2\)。这同样可以转化为关于整数系数 \(c_n, \dots, c_1\) 的二次型优化问题，并使用类似的递归枚举和剪枝策略来求解。Babai 的最近顶点算法 (Nearest Plane algorithm) 可以看作是 CVP 枚举的一个简化（贪心）版本，它只考虑一个解（通过舍入系数得到），但可以在多项式时间内完成，给出近似解。

基本思想 (以 NV Sieve [NV08] 为例):#

1. 生成样本点: 随机生成大量的格点。一种方法是选取随机的整数系数向量 \(\mathbf{c}\)，计算 \(\mathbf{v} = \mathbf{B} \mathbf{c}\)。为了使生成的点不至于太长，通常会限制系数 \(\mathbf{c}\) 的范围，或者使用某种随机游走 (random walk) 的方法在格上生成点。目标是生成一个包含许多“相对较短”的向量的列表 \(L\)。
2. 中心化: 将列表 \(L\) 中的所有向量都减半（这可能不再是格点），即 \(L' = \{ \mathbf{v}/2 \mid \mathbf{v} \in L \}\)。
3. 寻找碰撞 (或接近碰撞): 在列表 \(L'\) 中寻找两个向量 \(\mathbf{v}'_1, \mathbf{v}'_2 \in L'\)，它们彼此非常接近。可以使用某种最近邻搜索 (Nearest Neighbor Search, NNS) 的数据结构（如 Locality Sensitive Hashing, LSH）来加速这个过程。
4. 构造更短向量: 如果找到了两个足够近的向量 \(\mathbf{v}'_1 = \mathbf{v}_1 / 2\) 和 \(\mathbf{v}'_2 = \mathbf{v}_2 / 2\)（其中 \(\mathbf{v}_1, \mathbf{v}_2 \in L\) 且 \(\mathbf{v}_1 \neq \mathbf{v}_2\)），那么它们的差 \(\mathbf{v}'_1 - \mathbf{v}'_2 = (\mathbf{v}_1 - \mathbf{v}_2) / 2\) 应该是一个长度较短的向量。由于 \(\mathbf{v}_1, \mathbf{v}_2\) 是格点，\(\mathbf{v}_1 - \mathbf{v}_2\) 也是一个格点。如果 \(\mathbf{v}_1 - \mathbf{v}_2\) 的所有分量都是偶数，那么 \((\mathbf{v}_1 - \mathbf{v}_2) / 2\) 也是一个格点（属于原格或某个子格）。即使不是这样，\(\mathbf{v}_1 - \mathbf{v}_2\) 本身也是一个格点，并且由于 \(\mathbf{v}'_1, \mathbf{v}'_2\) 很近，\(\mathbf{v}_1 - \mathbf{v}_2\) 的长度大约是 \(||\mathbf{v}'_1 - \mathbf{v}'_2||\) 的两倍，可能比原来列表 \(L\) 中的向量更短。
5. 迭代: 将新找到的更短向量（如 \(\mathbf{v}_1 - \mathbf{v}_2\)）加入列表 \(L\)，并重复步骤 3-4。通过不断地将列表中的向量两两组合（相减），期望能够逐步“筛”出越来越短的向量，最终找到接近 \(\lambda_1\) 的向量。

不同的筛法变种:#

• AKS 筛法 [AKS01]: 最早提出的基于筛法的 SVP 算法，理论上证明了存在一个（非均匀的）量子算法可以在 \(2^{O(n)}\) 时间内解决 SVP。其经典版本也是指数时间。
• Nguyen-Vidick (NV) Sieve [NV08]: 上述描述的基本思想来源于此。它是一个启发式算法，但实践中非常有效。
• Gauss Sieve [MV10]: Micciancio 和 Voulgaris 提出的一种变种。它维护一个列表，列表中的向量满足某种约化条件（类似于二维的 Lagrange-Gauss 约化）。当插入新向量时，会检查是否可以用它来约化列表中的其他向量（通过加减整数倍）。Gauss Sieve 及其变种（如 List Sieve）在实践中表现非常好。
• 其他: 还存在许多其他的筛法变种和优化，例如基于球解码 (Sphere Decoding) 的筛法、使用不同 NNS 技术等。

复杂度：

• 启发式: 大多数实用的筛法算法都是启发式的，它们的运行时间分析依赖于一些未经证明的假设（例如，随机生成的格点分布足够好，NNS 能有效找到近邻等）。
• 时间复杂度: 启发式分析表明，许多筛法变种的时间复杂度大约是 \(2^{O(n)}\)，例如 \(2^{cn}\) 对于某个常数 \(c\) (如 \(c \approx 0.292\) for SVP in \(l_2\) norm in recent works)。这通常优于枚举算法在较高维度下的 \(2^{O(n^2)}\) 或 \(n^{O(n)}\) 复杂度。
• 空间复杂度: 筛法通常需要存储大量的格点列表，因此空间复杂度也很高，通常也是 \(2^{O(n)}\)。这是筛法的一个主要瓶颈。
• 当前最优: 对于求解 SVP 问题（尤其是在较高维度），筛法是当前已知最优的经典算法（在启发式意义下）。

筛法 vs 枚举:

• 维度: 筛法在高维（例如 \(n \ge 60-80\)）通常比枚举更快。枚举在低维和中维（\(n \le 50-70\)）由于其更可控的复杂性和精确性保证（如果需要）可能更受青睐。
• 精确性: 枚举可以保证找到精确解（如果运行足够长时间且不使用过多剪枝）。筛法通常是启发式的，找到的向量可能只是非常接近 \(\lambda_1\)。
• 实现: 筛法的实现通常比枚举更复杂，需要高效的 NNS 数据结构和内存管理。
• 应用: 两者都被用作 BKZ 中的 SVP 预言机。枚举更常用于需要保证找到块内精确最短向量的情况（如 BKZ 2.0 的某些分析），而筛法由于其速度优势在高维 BKZ 挑战中被广泛使用。

定义 5.1 (Voronoi 单元)#

给定格 \(\mathcal{L}\)，其 Voronoi 单元 \(\mathcal{V}(\mathcal{L})\) 定义为空间中所有离原点 \(\mathbf{0}\) 比离任何其他非零格点 \(\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}\) 都更近（或同样近）的点的集合： \(\mathcal{V}(\mathcal{L}) = \{ \mathbf{x} \in \mathbb{R}^n \mid ||\mathbf{x}|| \le ||\mathbf{x} - \mathbf{v}|| \text{ for all } \mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\} \}\) Voronoi 单元是一个以原点为中心的凸多面体。它的边界由那些与原点和某个（或某些）非零格点等距的点的集合构成（这些是垂直平分线段 \([0, \mathbf{v}]\) 的超平面的一部分）。 格 \(\mathcal{L}\) 的所有 Voronoi 单元的平移副本 \(\mathcal{V}(\mathcal{L}) + \mathbf{v}\)（其中 \(\mathbf{v} \in \mathcal{L}\)）会无重叠地铺满整个空间 \(\mathbb{R}^n\)。

基于 Voronoi 单元的 CVP 算法 (理论上):#

1. 计算 Voronoi 单元: 首先，计算出格 \(\mathcal{L}\) 的 Voronoi 单元 \(\mathcal{V}(\mathcal{L})\) 的描述（例如，定义它的所有面对应的超平面）。
2. 定位目标向量: 给定目标向量 \(\mathbf{t}\)，找到包含 \(\mathbf{t}\) 的那个 Voronoi 单元平移副本 \(\mathcal{V}(\mathcal{L}) + \mathbf{v}\)。
3. 最近邻: 那么，这个平移副本的中心 \(\mathbf{v}\) 就是离 \(\mathbf{t}\) 最近的格点。

困难性： 这个算法在理论上很优雅，但面临巨大的计算挑战：

• 计算 Voronoi 单元非常困难: Voronoi 单元的面数量可能随着维度 \(n\) 指数级增长（可以达到 \(2^{O(n^2)}\)）。显式地计算和存储 Voronoi 单元的完整描述在维度稍高时就变得不可行。
• 定位目标向量也困难: 即使有了 Voronoi 单元的描述，在指数级的面中快速定位包含 \(\mathbf{t}\) 的单元也是一个难题。

相关工作:#

尽管完全计算 Voronoi 单元很困难，但 Micciancio 和 Voulgaris [MV10] 提出了一个名为 “Voronoi Cell Algorithm” 的 CVP 算法，它并不显式计算整个单元。该算法利用了 Voronoi 单元的一些性质，并结合了类似于筛法的技术。它被证明对于 CVP 问题可以在 \(2^{O(n)}\) 时间和空间内找到解，这是第一个达到 \(2^{O(n)}\) 复杂度的 CVP 确定性算法（之前的枚举算法通常被认为是 \(n^{O(n)}\) 或 \(2^{O(n^2)}\)）。

总结: 求解 SVP 和 CVP 的精确或高质量近似解是格理论中的核心计算任务。

• 枚举算法 通过在有界区域内系统搜索格点，提供了求解这些问题的可靠方法，尤其适用于中低维度或作为 BKZ 的预言机。其效率依赖于预处理质量和剪枝策略。
• 筛法算法 通过迭代地组合格点来寻找短向量，是当前在高维度下求解 SVP 最快的（启发式）方法，但需要大量的计算时间和空间。
• 基于 Voronoi 单元的方法 为 CVP 提供了理论上的最优复杂度界 (\(2^{O(n)}\))，但实际应用仍具挑战。

这些算法构成了我们理解和处理格上困难问题的武器库。它们不仅在理论上重要，也在实践中（特别是在密码分析领域）发挥着关键作用。下一章我们将重点讨论格算法在密码学中的各种应用。

背景：量子计算的威胁#

现代公钥密码学严重依赖于某些被认为对经典计算机是困难的数论问题：

• RSA: 基于大整数因子分解的困难性。
• 椭圆曲线密码 (ECC): 基于椭圆曲线上离散对数问题的困难性。
• Diffie-Hellman 密钥交换: 基于有限域或椭圆曲线上离散对数问题的困难性。

然而，彼得·秀尔 (Peter Shor) 在 1994 年提出了 Shor 算法 [Shor94]，证明了量子计算机可以在多项式时间内解决大整数因子分解和离散对数问题。一旦足够强大的量子计算机建成，目前广泛使用的公钥密码体系将变得不再安全。这激发了研究者寻找能够抵抗量子计算机攻击的新的密码学基础，即 后量子密码学 (PQC)。

格问题的抗量子特性#

格上的困难问题（如 SVP, CVP, LWE, SIS）目前被认为能够抵抗已知的量子算法攻击。虽然量子计算机可能对某些格问题提供一定的加速（例如，可能有量子算法能以 \(2^{O(\sqrt{n})}\) 的复杂度解决 SVP，相比经典的 \(2^{O(n)}\)），但这种加速通常被认为是次指数级或指数级的，与 Shor 算法对因子分解和离散对数的指数级到多项式级的颠覆性加速不同。因此，基于格问题的困难性假设构建的密码系统被认为是 抗量子 (quantum-resistant) 或 后量子 (post-quantum) 的。

格密码的优势#

除了抗量子攻击的潜力外，格密码还具有其他吸引人的特性：

1. 安全性证明: 许多格密码方案（尤其是基于 LWE/SIS 的方案）具有较强的 安全性归约 (Security Reduction)。它们可以将密码方案的安全性归约到某个被认为是困难的 最坏情况 (worst-case) 格问题（如 SVP 或 GapSVP）的困难性上。这意味着如果存在一个攻击者能破解该密码方案（即使是对于随机选择的密钥），那么利用这个攻击者就可以构建一个算法来解决所有实例的某个困难格问题。这种最坏情况到平均情况 (worst-case to average-case) 的归约提供了很强的理论安全保证。
2. 效率: 基于格的方案（特别是基于 Ring-LWE/Module-LWE 和 Ring-SIS/Module-SIS 的方案）可以实现相当高的效率，其密钥大小、签名大小和计算速度可以与传统的 RSA/ECC 相媲美，甚至在某些方面更优。
3. 高级功能: 格结构特别适合实现一些高级的密码学功能，最引人注目的是 全同态加密 (Fully Homomorphic Encryption, FHE)，它允许在不知道明文的情况下对密文进行任意计算。目前几乎所有实用的 FHE 方案都是基于格的。此外，格也被用于构造零知识证明、属性基加密 (ABE)、函数加密等高级密码原语。
4. 并行性: 许多格运算（如向量-矩阵乘法、多项式运算）具有良好的并行性，适合硬件实现和加速。

早期尝试：GGH 密码体制 (Goldreich-Goldwasser-Halevi, 1997)#

• 思想: 基于 CVP 问题。私钥是一个“好”的格基 \(\mathbf{B}_{priv}\)（向量短且近似正交）。公钥是通过一个随机的幺模变换 \(\mathbf{U}\) 得到的“坏”基 \(\mathbf{B}_{pub} = \mathbf{B}_{priv} \mathbf{U}\)（向量长且非正交）。
• 加密: 将消息 \(m\) 编码为一个短的扰动向量 \(\mathbf{e}\)。密文 \(\mathbf{c}\) 是格点 \(\mathbf{v} = \mathbf{B}_{pub} \mathbf{m}\) (其中 \(\mathbf{m}\) 是明文对应的整数向量，可以简单认为 \(m\) 就是 \(\mathbf{e}\) 本身，或者 \(\mathbf{v} = \mathbf{B}_{pub}\mathbf{i} + \mathbf{e}\) 对于某个随机 \(\mathbf{i}\)) 加上扰动 \(\mathbf{e}\)，即 \(\mathbf{c} = \mathbf{v} + \mathbf{e}\) (这里简化了描述，实际方案更复杂)。\(\mathbf{c}\) 看起来就像是目标向量，它接近某个由 \(\mathbf{B}_{pub}\) 生成的格点。
• 解密: 拥有私钥 \(\mathbf{B}_{priv}\) 的接收者，由于 \(\mathbf{B}_{priv}\) 是好基，可以高效地利用它来解决 CVP 问题：找到离密文 \(\mathbf{c}\) 最近的格点 \(\mathbf{v}'\)（使用 Babai 算法等）。如果扰动 \(\mathbf{e}\) 足够小，那么 \(\mathbf{v}'\) 很可能就是原始的格点 \(\mathbf{v}\)。然后从 \(\mathbf{v}\) 中恢复出消息 \(\mathbf{m}\) (或 \(\mathbf{e}\))。
• 安全性问题: GGH 方案后来被 Nguyen (1999) 等人使用格基约化算法 (如 LLL) 攻击。攻击者可以从公钥 \(\mathbf{B}_{pub}\) 中恢复出足够好的基，从而也能解决相关的 CVP 问题，导致方案不安全。这表明直接基于 CVP 的构造需要非常小心。

NTRUEncrypt / NTRUSign (Hoffstein, Pipher, Silverman, 1996/1998)#

• 基础: 在 多项式环 \(\mathbb{Z}_q[x] / (x^N - 1)\) 上进行运算（\(N\) 通常是素数，\(q\) 是一个整数模数）。运算涉及多项式的加法、乘法。
• 密钥生成: 私钥通常是两个“小”的多项式 \((f, g)\)（系数小）。公钥 \(h = g * f^{-1} \pmod q\) (在环上计算逆)。
• 加密 (NTRUEncrypt - KEM):
  1. 选择一个随机的“小”多项式 \(r\) (临时密钥)。
  2. 计算密文 \(e = r * h + m \pmod q\)，其中 \(m\) 是要加密的消息（通常是对称密钥），也被编码为一个小多项式。
  3. 发送密文 \(e\)。对称密钥是 \(m\) (或从 \(m, r\) 导出的)。
• 解密:
  1. 接收者计算 \(a = f * e \pmod q = f * (r * g * f^{-1} + m) \pmod q = r * g + f * m \pmod q\)。
  2. 由于 \(f, g, r, m\) 都是小多项式， \(a = r*g + f*m\) 在模 \(q\) 之前也是一个小多项式（其系数在某个小范围内）。接收者可以将 \(a\) 的系数调整回这个小范围，得到 \(a'\)。
  3. 如果知道 \(a'\) 和私钥 \(f\), 可以尝试恢复 \(m\)。（实际 KEM 中是恢复 \(r\)，然后用 \(r,e\) 恢复 \(m\)）。
• 安全性: NTRU 的安全性与在特定多项式环格 (ideal lattice 或 polynomial ring lattice) 中寻找短向量（一种 SVP 变种）有关。攻击者可以尝试从公钥 \(h\) 中恢复私钥 \((f, g)\)，这通常涉及到在一个维度为 \(2N\) 的相关格上使用 LLL/BKZ 算法寻找短向量。
• NTRUSign: 类似地，利用环结构和短向量构造数字签名。
• 效率与标准化: NTRU 通常效率较高，密钥和签名尺寸相对较小。它经历了多年的发展和标准化尝试，也是 NIST PQC 标准化过程中的候选者之一 (NTRU, NTRU Prime)。

基于 LWE (Learning With Errors) 的密码学#

LWE 问题由 Oded Regev 在 2005 年提出 [Reg05]，已成为现代格密码学的基石之一。

• LWE 问题定义:#

  给定一个模数 \(q\)，一个秘密向量 \(\mathbf{s} \in \mathbb{Z}_q^n\)，以及一系列样本 \((\mathbf{a}_i, b_i)\)，其中 \(\mathbf{a}_i \in \mathbb{Z}_q^n\) 是随机向量，而 \(b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod q\)。这里的 \(e_i\) 是从某个固定的、中心在 0 的“小”错误分布 \(\chi\) (通常是离散高斯分布) 中抽取的噪声。LWE 问题要求从这些样本 \((\mathbf{a}_i, b_i)\) 中恢复出秘密向量 \(\mathbf{s}\)。 判定版本 (Decision-LWE): 区分 LWE 样本 \((\mathbf{a}_i, b_i)\) 和完全随机均匀的样本 \((\mathbf{a}_i, u_i)\) (其中 \(u_i \in \mathbb{Z}_q\) 均匀随机)。

• 困难性假设:#

  Regev 证明了，如果存在一个量子算法能解决 LWE 问题（对于某些参数设置），那么就存在一个量子算法能解决某些标准格问题（如 GapSVP 和 SIVP）的 最坏情况 实例（近似因子是 \(poly(n)\)）。后来也有经典归约证明（但通常需要更强的假设或得到稍弱的结论）。这使得 LWE 假设成为一个非常有吸引力的密码学基础。

• Regev 公钥加密方案 (简化版 KEM):#

  1. 参数: \(n, q\), 错误分布 \(\chi\)。
  2. 密钥生成:
     • 私钥: \(\mathbf{s} \in \mathbb{Z}_q^n\) (随机选取)。
     • 公钥: 选择 \(m\) (足够多, e.g., \(m > n \log q\)) 个随机向量 \(\mathbf{a}_i \in \mathbb{Z}_q^n\) 和错误 \(e_i \leftarrow \chi\)。计算 \(b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod q\)。公钥是 \((\mathbf{A}, \mathbf{b})\)，其中 \(\mathbf{A}\) 是行向量为 \(\mathbf{a}_i^T\) 的矩阵，\(\mathbf{b} = (b_1, \dots, b_m)^T\)。
  3. 加密 (封装):
     • 选择一个随机的二元向量 \(\mathbf{r} \in \{0, 1\}^m\)。
     • 计算密文 \(\mathbf{u} = \mathbf{A}^T \mathbf{r} \pmod q\) 和 \(v = \mathbf{b}^T \mathbf{r} + \lfloor q/2 \rfloor \cdot \mu \pmod q\)。其中 \(\mu \in \{0, 1\}\) 是要封装的密钥位。
     • 发送密文 \((\mathbf{u}, v)\)。
  4. 解密 (解封装):
     • 计算 \(v' = v - \langle \mathbf{u}, \mathbf{s} \rangle \pmod q\)。
     • \(v' = (\mathbf{b}^T \mathbf{r} + \lfloor q/2 \rfloor \mu) - (\mathbf{A}^T \mathbf{r})^T \mathbf{s} \pmod q\)
     • \(v' = ((\mathbf{A}\mathbf{s} + \mathbf{e})^T \mathbf{r} + \lfloor q/2 \rfloor \mu) - \mathbf{r}^T \mathbf{A} \mathbf{s} \pmod q\)
     • \(v' = (\mathbf{s}^T \mathbf{A}^T \mathbf{r} + \mathbf{e}^T \mathbf{r} + \lfloor q/2 \rfloor \mu) - \mathbf{r}^T \mathbf{A} \mathbf{s} \pmod q\)
     • \(v' = \mathbf{e}^T \mathbf{r} + \lfloor q/2 \rfloor \mu \pmod q\)。
     • 由于 \(\mathbf{r}\) 是二元向量，\(\mathbf{e}\) 是小错误向量，\(\mathbf{e}^T \mathbf{r} = \sum_{i \in S} e_i\) (其中 \(S\) 是 \(\mathbf{r}\) 中 1 的位置集合) 是一个相对较小的和。
     • 如果 \(| \mathbf{e}^T \mathbf{r} | < q/4\)，那么：
       • 如果 \(\mu = 0\), \(v'\) 接近 0 (模 q)。
       • 如果 \(\mu = 1\), \(v'\) 接近 \(\lfloor q/2 \rfloor\) (模 q)。
     • 接收者检查 \(v'\) 是更接近 0 还是 \(\lfloor q/2 \rfloor\) 来恢复 \(\mu\)。

• Ring-LWE / Module-LWE:#

  为了提高效率（减少公钥大小和计算量），Lyubashevsky, Peikert, Regev 等人引入了 Ring-LWE (RLWE)。它将 LWE 问题从向量空间 \(\mathbb{Z}_q^n\) 移到了多项式环 \(R_q = \mathbb{Z}_q[x] / (\Phi(x))\) 上（\(\Phi(x)\) 通常是 \(x^N+1\) 等分圆多项式）。秘密 \(\mathbf{s}\) 和向量 \(\mathbf{a}_i\) 都变成环 \(R_q\) 中的元素（多项式），内积变成多项式乘法。一个 RLWE 样本 \((\mathbf{a}, b = \mathbf{a} \cdot \mathbf{s} + e)\) 可以紧凑地表示 \(N\) 个 LWE 样本，大大提高了效率。Module-LWE (MLWE) 是介于 LWE 和 RLWE 之间的推广，在 \(R_q^k\) 模上工作。

• NIST PQC 标准化中的 LWE/RLWE/MLWE 方案:#

  LWE 及其变种是 NIST PQC 标准化中最成功的类别之一。

  • Kyber (KEM): 基于 Module-LWE。已被 NIST 选为 KEM 的主要标准。
  • Dilithium (签名): 基于 Module-LWE 和 Module-SIS。已被 NIST 选为数字签名的新标准之一。
  • 其他候选方案如 Saber (MLWE), FrodoKEM (LWE) 等也基于 LWE 相关假设。

基于 SIS (Short Integer Solution) 的密码学#

SIS 问题与 LWE 密切相关，也是由 Ajtai 提出并被 Regev 等人发展的。

• SIS 问题定义:#

  给定一个模数 \(q\)，一个随机矩阵 \(\mathbf{A} \in \mathbb{Z}_q^{m \times n}\) (\(m\) 通常小于 \(n\))，以及一个界限 \(\beta\)。找到一个 非零 的整数向量 \(\mathbf{z} \in \mathbb{Z}^n\) 使得：

  1. \(\mathbf{A} \mathbf{z} = \mathbf{0} \pmod q\)
  2. \(||\mathbf{z}||_\infty \le \beta\) (或 \(||\mathbf{z}||_2 \le \beta\)) 即，找到一个属于格 \(\mathcal{L}^\perp(\mathbf{A}) = \{ \mathbf{x} \in \mathbb{Z}^n \mid \mathbf{A} \mathbf{x} = \mathbf{0} \pmod q \}\) (称为 A 的正交格或核格) 的“短”非零向量 \(\mathbf{z}\)。

• 困难性假设:#

  SIS 问题也被认为是非常困难的。存在从最坏情况格问题（如 SIVP）到 SIS 问题的归约。SIS 的困难性是许多基于格的哈希函数和数字签名的基础。

• 构造抗碰撞哈希函数:#

  Micciancio 等人展示了如何基于 SIS 构造抗碰撞哈希函数。一个简单的想法是：哈希函数的输入 \(x\) (比如一个位串) 被映射到一个短向量 \(\mathbf{z}_x\) (满足 \(||\mathbf{z}_x|| \le \beta\))。哈希值定义为 \(H(x) = \mathbf{A} \mathbf{z}_x \pmod q\)。如果能找到两个不同的输入 \(x \neq y\) 使得 \(H(x) = H(y)\)，那么 \(\mathbf{A} \mathbf{z}_x = \mathbf{A} \mathbf{z}_y \pmod q\)，即 \(\mathbf{A} (\mathbf{z}_x - \mathbf{z}_y) = \mathbf{0} \pmod q\)。由于 \(x \neq y\), \(\mathbf{z}_x \neq \mathbf{z}_y\)。并且如果 \(\mathbf{z}_x, \mathbf{z}_y\) 都足够短，那么它们的差 \(\mathbf{z} = \mathbf{z}_x - \mathbf{z}_y\) 也是一个相对短的非零向量（例如 \(||\mathbf{z}|| \le 2\beta\)）。因此，找到哈希碰撞就意味着解决了一个 SIS 问题实例。

• 构造数字签名方案:#

  基于 SIS 可以构造安全的数字签名方案。一个重要的框架是 Fiat-Shamir with Aborts [Lyu09]，结合 “Hash-and-Sign” 范式。

  1. 密钥生成: 私钥是一个短的基 \(\mathbf{S} \in \mathbb{Z}^{n \times k}\) (列向量短)。公钥是 \(\mathbf{A}\) 使得 \(\mathbf{A} \mathbf{S} = \mathbf{0} \pmod q\) (例如，随机选 \(\mathbf{A}\)，然后找到其核格的一个短基 \(\mathbf{S}\)，或者反之)。
  2. 签名: 要签名消息 \(m\)：
     • 选择一个随机的“掩码”向量 \(\mathbf{y}\) (通常从某个分布如均匀离散高斯中选取)。
     • 计算承诺 \(w = \mathbf{A} \mathbf{y} \pmod q\)。
     • 计算挑战 \(c = H(w, m)\) ( \(H\) 是一个抗碰撞哈希函数，输出一个小整数或多项式)。
     • 计算响应 \(\mathbf{z} = \mathbf{y} + \mathbf{S} c\)。
     • 拒绝采样 (Rejection Sampling): 检查响应 \(\mathbf{z}\) 是否“足够短”（例如，其范数是否小于某个界限 \(\beta\)，或者其系数分布是否接近目标分布）。如果不够短，则重新从第一步开始选择新的 \(\mathbf{y}\)。如果足够短，则 \((\mathbf{z}, c)\) 就是签名。
  3. 验证: 给定消息 \(m\) 和签名 \((\mathbf{z}, c)\)：
     • 计算 \(w' = \mathbf{A} \mathbf{z} - c \cdot (\mathbf{A} \mathbf{S} \pmod q)\)。由于 \(\mathbf{A} \mathbf{S} = \mathbf{0} \pmod q\) (公钥验证的一部分，这里假设 \(\mathbf{A}\) 是公钥)，所以 \(w' = \mathbf{A} \mathbf{z} \pmod q\)。
     • 检查 \(c \stackrel{?}{=} H(w', m)\)。
     • 检查 \(\mathbf{z}\) 是否满足长度界限 \(||\mathbf{z}|| \le \beta\) (或分布检查)。
     • 如果都通过，则签名有效。
  • 安全性: 伪造签名需要找到一个短向量 \(\mathbf{z}\) 使得 \(\mathbf{A} \mathbf{z} = c \cdot \mathbf{0} = \mathbf{0} \pmod q\) (对于某个 \(c\))，这与 SIS 问题相关。拒绝采样确保了签名 \(\mathbf{z}\) 的分布不依赖于私钥 \(\mathbf{S}\)，从而防止了信息泄露。
  • GPV 框架 [GPV08]: Gentry, Peikert, Vaikuntanathan 提出了一个基于格的签名通用框架，利用了格原像采样 (Preimage Sampling) 技术。
  • Falcon (签名): NIST PQC 标准之一，基于 NTRU 格上的 SIS 问题，并利用快速傅里叶变换 (FFT) 进行高效计算。其安全性依赖于 NTRU 格上的标准短向量问题。