格算法：理论、应用与实践

2025-03-30

/

/

/

/

前言#

格 (Lattice) 是数学中一个基础而重要的概念，它在纯粹数学的多个分支，如数论（尤其是数的几何）、群论、表示论中扮演着核心角色。然而，在过去的几十年里，格理论及其相关算法的研究经历了一次引人注目的复兴，其影响力远远超出了纯数学的范畴，在理论计算机科学、密码学、优化、信号处理等应用领域展现出强大的生命力。

特别是在密码学领域，格算法正处于一场革命的中心。随着量子计算对现有公钥密码体制（如RSA、ECC）构成潜在威胁，基于格的密码学 (Lattice-based Cryptography) 作为最有前途的后量子密码 (Post-Quantum Cryptography, PQC) 候选方案之一，受到了学术界和工业界的极大关注。其安全性基于被认为是“困难”的格问题（如最短向量问题 SVP、最近向量问题 CVP），这些问题目前被认为即使对量子计算机也难以有效解决。此外，格密码不仅提供了抗量子攻击的潜力，还催生了全同态加密 (Fully Homomorphic Encryption, FHE) 等前沿密码学技术的突破，为数据隐私和安全计算开辟了新的可能性。

理解格密码及其安全性的基础，离不开对格算法的深入研究。算法如 LLL (Lenstra–Lenstra–Lovász) 及其改进（如 BKZ）不仅是许多格密码体制分析（攻击）的关键工具，也是一些格密码方案构造本身的基础。这些算法致力于解决格中的基本计算问题，其核心在于“格基约化”(Lattice Basis Reduction)——寻找一个格的“更好”的表示（基），使得基向量更短、更接近正交。

本报告旨在为对格理论、格算法及其应用感兴趣的读者提供一份全面而深入的指南。我们将从格的基本数学概念出发，系统介绍相关的计算困难问题，详细剖析经典的 LLL 算法和更高级的 BKZ 算法，探讨解决这些困难问题的精确算法和启发式算法，并广泛讨论格算法在现代密码学（构造与分析）以及其他科学与工程领域中的重要应用。我们力求在保证数学严谨性的同时，注重概念的直观解释和算法的清晰阐述，并结合实例与最新进展，希望能为读者构建一个关于格算法的坚实知识框架。

本报告的结构安排如下：

第一章：格的数学基础 - 介绍格的定义、性质、基本区域、行列式、对偶格以及 Minkowski 定理。
第二章：格上的困难问题 - 阐述核心的计算问题，如 SVP, CVP, SIVP 等及其计算复杂性。
第三章：核心格算法：LLL 算法及其影响 - 深入剖析 LLL 算法的原理、流程、性质、分析及其重要意义。
第四章：高级格约化算法：BKZ 算法 - 介绍 BKZ 算法的动机、原理、流程及其与 LLL 的比较。
第五章：求解 SVP 和 CVP 的精确与启发式算法 - 讨论枚举、筛法等更专门化的算法。
第六章：格算法在密码学中的应用 - 重点介绍格在后量子密码、全同态加密构造及密码分析中的角色。
第七章：格算法在其他领域的应用 - 简述格在编码理论、整数规划等其他领域的应用。
第八章：总结与未来展望 - 总结格算法的现状、挑战与未来发展方向。

希望通过这份报告，读者能够对格算法这一充满活力和潜力的领域有一个系统性的认识。

第一章：格的数学基础#

在深入探讨格算法之前，我们必须首先建立对“格”本身及其相关数学概念的清晰理解。本章将介绍格的定义、基本性质、表示方法以及一些关键的几何和代数工具。

1.1 什么是格 (Lattice)？#

在欧几里得空间 $\mathbb{R}^n$ 中，一个格 $\mathcal{L}$ 是由一组线性无关向量 $\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_k \in \mathbb{R}^n$ (其中 $k \le n$ ) 的所有整数线性组合构成的点集。形式化定义如下：

定义 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}$ $L$ 是 $\mathbb{R}^n$ $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$

1.2 格的基本性质#

不同的基表示同一个格#

同一个格可以由不同的基来表示。例如，在上面的二维例子中，向量组 $\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.3 对偶格 (Dual Lattice)#

对偶格是与原格密切相关的一个重要概念，在理论分析和某些应用（如编码理论、密码学中的 SIS 问题）中很有用。

定义 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}$ 是标准内积。对偶格包含所有与原格中所有向量的内积均为整数的向量。

性质：

对偶格也是一个格: 如果 $\mathcal{L}$ 是一个格，那么 $\mathcal{L}^*$ 也是一个格。
对偶格的基: 如果 $\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 正交化中的向量符号区别，上下文会明确)。
行列式关系: 对偶格的行列式与原格的行列式互为倒数： $\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}$ 。
对偶的对偶: 对偶格的对偶是原格： $(\mathcal{L}^*)^* = \mathcal{L}$ 。
包含关系: 整数格 $\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.4 格中的向量范数与距离#

在格的研究中，衡量向量的“长度”或“大小”至关重要。最常用的范数是欧几里得范数（ $l_2$ 范数）。

欧几里得范数 ( $l_2$ ): 对于向量 $\mathbf{x} = (x_1, \dots, x_n)^T \in \mathbb{R}^n$ ，其欧几里得范数定义为： $||\mathbf{x}|| = ||\mathbf{x}||_2 = \sqrt{\sum_{i=1}^n x_i^2} = \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle}$ 两个向量 $\mathbf{x}, \mathbf{y}$ 之间的欧几里得距离是 $||\mathbf{x} - \mathbf{y}||_2$ 。
$l_p$ 范数: 更一般地，可以定义 $l_p$ 范数 ( $p \ge 1$ )： $||\mathbf{x}||_p = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}$
无穷范数 ( $l_\infty$ ): 当 $p \to \infty$ 时，极限为无穷范数： $||\mathbf{x}||_\infty = \max_{i=1}^n |x_i|$

在本报告中，当我们提到向量的“长度”或范数而没有指定时，通常指的是 欧几里得范数 ( $l_2$ )。格中的许多核心问题，如 SVP 和 CVP，都是基于欧几里得范数定义的。

1.5 Minkowski 定理#

Minkowski 定理是“数的几何”领域的基石，它在格理论中扮演着极其重要的角色，因为它保证了在任何格中都存在一个“不太长”的非零向量。

在陈述定理之前，需要几个概念：

中心对称集 (Centrally Symmetric Set): $\mathbb{R}^n$ 中的集合 $S$ 是中心对称的，如果对于任意 $\mathbf{x} \in S$ ，都有 $-\mathbf{x} \in S$ 。
凸集 (Convex Set): $\mathbb{R}^n$ 中的集合 $S$ 是凸集，如果对于任意 $\mathbf{x}, \mathbf{y} \in S$ 和任意 $0 \le \lambda \le 1$ ，都有 $\lambda \mathbf{x} + (1-\lambda) \mathbf{y} \in S$ 。几何上讲，连接集合中任意两点的线段完全包含在集合内。
体积 (Volume): 对于 $\mathbb{R}^n$ 中的集合 $S$ ， $\text{vol}(S)$ 表示其 $n$ 维体积（勒贝格测度）。

定理 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 定理提供的最短向量存在性保证，是掌握格算法的关键第一步。

第二章：格上的困难问题#

格理论的计算方面主要围绕着几个被认为是“困难”的核心问题展开。这些问题的困难性不仅构成了许多现代密码系统的安全基础，也驱动了格算法（如 LLL、BKZ）的发展。本章将详细介绍其中最主要的几个问题：最短向量问题 (SVP)、最近向量问题 (CVP)，以及相关的变种。

2.1 最短向量问题 (Shortest Vector Problem, SVP)#

SVP 是格理论中最核心、研究最深入的问题之一。顾名思义，它要求在一个给定的格中找到一个最短的非零向量。

定义 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.2 最近向量问题 (Closest Vector Problem, CVP)#

CVP 是另一个核心的格问题，它与 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.3 最短独立向量问题 (Shortest Independent Vectors Problem, SIVP)#

SIVP 是对 SVP 的一个推广，它要求找到 $n$ 个线性无关的、且长度尽可能小的格向量。

定义 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.4 有界距离解码问题 (Bounded Distance Decoding, BDD)#

BDD 可以看作是 CVP 的一个特殊承诺版本 (promise problem)。它假设目标向量 $\mathbf{t}$ 离格 $\mathcal{L}$ 足够近。

定义 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}$ 。

2.5 其他相关问题简介#

最短基问题 (Shortest Basis Problem, SBP): 找到一个格基 $\mathbf{B}' = \{\mathbf{b}'_1, \dots, \mathbf{b}'_n\}$ ，使得基向量的总长度或最大长度（或其他衡量标准）最小化。这个问题通常比 SVP 或 SIVP 更难。LLL 和 BKZ 算法可以看作是 SBP 的近似算法。
覆盖半径问题 (Covering Radius Problem): 找到最小的半径 $R$ (称为覆盖半径 $\mu(\mathcal{L})$ )，使得空间中任意一点 $\mathbf{t} \in \mathbb{R}^n$ 到格 $\mathcal{L}$ 的距离都不超过 $R$ 。即 $\mu(\mathcal{L}) = \max_{\mathbf{t} \in \mathbb{R}^n} \text{dist}(\mathbf{t}, \mathcal{L})$ 。几何上，这是能覆盖整个空间的、以格点为中心的相同闭球的最小半径。计算覆盖半径也是一个困难问题。
子集和问题 (Subset Sum Problem) 与格问题的联系: 子集和问题（给定一组整数 $a_1, \dots, a_n$ 和一个目标值 $T$ ，是否存在一个子集 $S \subseteq \{1, \dots, n\}$ 使得 $\sum_{i \in S} a_i = T$ ？）是一个经典的 NP-完全问题。它可以被转化为一个特定结构格上的 CVP 问题。例如，考虑 $n+1$ 维格，其基由以下向量构成： $\mathbf{b}_1 = (1, 0, \dots, 0, M a_1)^T$ $\mathbf{b}_2 = (0, 1, \dots, 0, M a_2)^T$ $\vdots$ $\mathbf{b}_n = (0, 0, \dots, 1, M a_n)^T$ $\mathbf{b}_{n+1} = (0, 0, \dots, 0, M T)^T$ 其中 $M$ 是一个足够大的数。目标向量设为 $\mathbf{t} = (0, \dots, 0)^T$ 。那么，寻找这个格中一个特定的短向量（或接近 $\mathbf{t}$ 的向量）可以揭示子集和问题的解。LLL 算法最初就是为了解决一个与因子分解相关的背包问题（子集和问题的变种）而提出的，这显示了格算法在数论和组合优化问题中的威力。

本章概述了格上最重要的几个计算困难问题。它们的精确版本通常是 NP-hard 的，而近似版本的困难性则依赖于近似因子 $\gamma$ 。这些问题的困难性不仅是理论研究的对象，更是构建安全密码系统的基础。下一章我们将开始探讨第一个能够有效解决这些问题（近似版本）的多项式时间算法——LLL 算法。

第三章：核心格算法：LLL 算法及其影响#

在认识到格上存在诸如 SVP 和 CVP 这样的困难问题之后，自然的问题是：我们能做些什么？虽然精确求解这些问题通常是困难的，但在 1982 年，Arjen Lenstra、Hendrik Lenstra, Jr. 和 László Lovász 合作发表了一篇里程碑式的论文 [LLL82]，提出了第一个可以在多项式时间内找到格中“相当短”的向量的算法。这个算法被称为 LLL 算法，它彻底改变了格理论的计算方面，并在密码学、数论、优化等领域产生了深远影响。本章将深入探讨 LLL 算法的原理、流程、性质及其意义。

3.1 算法背景与动机#

格基约化 (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\}$ 。什么样的基算是“好”的呢？通常我们希望基满足以下性质：

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

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

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

3.2 Gram-Schmidt 正交化 (GSO)#

LLL 算法的核心是利用 Gram-Schmidt 正交化过程来衡量和改进基的正交性。让我们回顾一下 Gram-Schmidt 正交化 (GSO)。

给定一组线性无关的向量（格的基） $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ ，GSO 过程构造一组正交向量 $\mathbf{B}^* = \{\mathbf{b}^*_1, \dots, \mathbf{b}^*_n\}$ ，并且对于每个 $k = 1, \dots, n$ ，由 $\{\mathbf{b}_1, \dots, \mathbf{b}_k\}$ 张成的子空间与由 $\{\mathbf{b}^*_1, \dots, \mathbf{b}^*_k\}$ 张成的子空间相同。

GSO 向量 $\mathbf{b}^*_i$ 和相关的系数 $\mu_{ij}$ 定义如下：

初始化: $\mathbf{b}^*_1 = \mathbf{b}_1$
迭代: 对于 $i = 2, \dots, n$ : $\mathbf{b}^*_i = \mathbf{b}_i - \sum_{j=1}^{i-1} \mu_{ij} \mathbf{b}^*_j$ 其中，投影系数 $\mu_{ij}$ 定义为： $\mu_{ij} = \frac{\langle \mathbf{b}_i, \mathbf{b}^*_j \rangle}{\langle \mathbf{b}^*_j, \mathbf{b}^*_j \rangle} = \frac{\mathbf{b}_i^T \mathbf{b}^*_j}{||\mathbf{b}^*_j||^2} \quad \text{for } 1 \le j < i$

关键性质：

正交性: GSO 向量两两正交： $\langle \mathbf{b}^*_i, \mathbf{b}^*_j \rangle = 0$ 对所有 $i \neq j$ 。
子空间不变性: $\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_k) = \text{span}(\mathbf{b}^*_1, \dots, \mathbf{b}^*_k)$ 对所有 $k$ 。
向量关系: $\mathbf{b}_i = \mathbf{b}^*_i + \sum_{j=1}^{i-1} \mu_{ij} \mathbf{b}^*_j$ 。这表示 $\mathbf{b}_i$ 是其在由 $\mathbf{b}^*_1, \dots, \mathbf{b}^*_{i-1}$ 张成的子空间上的投影 ( $\sum_{j=1}^{i-1} \mu_{ij} \mathbf{b}^*_j$ ) 与垂直于该子空间的分量 ( $\mathbf{b}^*_i$ ) 的和。
长度关系: $||\mathbf{b}^*_i||$ 代表了 $\mathbf{b}_i$ 在正交于 $\text{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})$ 方向上的“新”分量的长度。因此，总有 $||\mathbf{b}^*_i|| \le ||\mathbf{b}_i||$ 。
行列式关系: 格的行列式可以用 GSO 向量的长度计算： $\det(\mathcal{L}) = |\det(\mathbf{B})| = \prod_{i=1}^n ||\mathbf{b}^*_i||$ 这可以从 $\mathbf{B} = \mathbf{B}^* \mathbf{M}$ 看出，其中 $\mathbf{M}$ 是一个上三角矩阵，对角线元素为 1， $(j, i)$ 处的元素为 $\mu_{ij}$ ( $j<i$ )。由于 $\mathbf{B}^*$ 的列是正交的， $|\det(\mathbf{B}^*)| = ||\mathbf{b}^*_1|| \cdots ||\mathbf{b}^*_n||$ (如果 $\mathbf{B}^*$ 列组成矩阵， $\det((\mathbf{B}^*)^T \mathbf{B}^*) = \prod ||\mathbf{b}_i^*||^2$ )。 $\det(\mathbf{M})=1$ 。所以 $|\det(\mathbf{B})| = |\det(\mathbf{B}^*)| = \prod ||\mathbf{b}^*_i||$ 。

GSO 在 LLL 中的作用： LLL 算法并不直接使用 GSO 向量 $\mathbf{b}^*_i$ 作为新的基（因为 $\mathbf{b}^*_i$ 通常不是格向量，除非它们恰好是正交基）。相反，LLL 算法利用 GSO 向量和 $\mu_{ij}$ 系数来衡量当前基 $\mathbf{B}$ 的“质量”，并指导如何通过基变换来改进这个质量。

3.3 LLL 约化基的定义#

LLL 算法的目标是找到一个满足以下两个条件的基 $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ 。这样的基称为 LLL 约化基 (LLL-reduced basis)。设 $\mathbf{B}^* = \{\mathbf{b}^*_1, \dots, \mathbf{b}^*_n\}$ 是对应的 GSO 向量， $\mu_{ij}$ 是 GSO 系数。

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 条件时）向量交换来最终达到这个状态的过程。

3.4 LLL 算法流程#

LLL 算法是一个迭代过程，它通过修改基向量（同时保持格不变）来逐步满足 LLL 约化条件。

输入： 格 $\mathcal{L}$ 的一组基 $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ ，参数 $\delta$ (通常 $\delta=3/4$ )。 输出： 格 $\mathcal{L}$ 的一个 LLL 约化基 $\mathbf{B}' = \{\mathbf{b}'_1, \dots, \mathbf{b}'_n\}$ 。

算法步骤：

初始化: 计算初始基 $\mathbf{B}$ 的 GSO 向量 $\mathbf{B}^* = \{\mathbf{b}^*_1, \dots, \mathbf{b}^*_n\}$ 和系数 $\mu_{ij} = \langle \mathbf{b}_i, \mathbf{b}^*_j \rangle / ||\mathbf{b}^*_j||^2$ (for $1 \le j < i \le n$ )。设置一个索引 $k = 2$ 。
主循环: 当 $k \le n$ 时，执行以下步骤： a. 尺寸约化 (Size Reduce) $\mathbf{b}_k$ : i. 对于 $j = k-1, k-2, \dots, 1$ (从右到左)： * 计算（或获取） $\mu_{kj} = \langle \mathbf{b}_k, \mathbf{b}^*_j \rangle / ||\mathbf{b}^*_j||^2$ 。 * 如果 $|\mu_{kj}| > 1/2$ ，令 $r = \text{round}(\mu_{kj})$ (最接近 $\mu_{kj}$ 的整数)。 * 更新 $\mathbf{b}_k \leftarrow \mathbf{b}_k - r \mathbf{b}_j$ 。 * 注意: 更新 $\mathbf{b}_k$ 后，需要更新相关的 GSO 系数 $\mu_{kl}$ (对于 $l < j$ ) 和 GSO 向量（如果需要精确计算）。在实际实现中，通常会直接更新 $\mu_{kl} \leftarrow \mu_{kl} - r \mu_{jl}$ (for $l<j$ ) 而不重新计算内积，并且 GSO 向量 $\mathbf{b}^*_1, \dots, \mathbf{b}^*_k$ 不会因为这个操作而改变。 ii. 执行完对所有 $j$ 的检查和可能的更新后， $\mathbf{b}_k$ 相对于 $\mathbf{b}_1, \dots, \mathbf{b}_{k-1}$ 是尺寸约化的。
b. 检查 Lovász 条件: i. 计算（或获取）当前的 $\mu_{k, k-1}$ 和 GSO 向量长度平方 $||\mathbf{b}^*_k||^2$ 和 $||\mathbf{b}^*_{k-1}||^2$ 。 ii. 如果 $\delta ||\mathbf{b}^*_{k-1}||^2 > ||\mathbf{b}^*_k||^2 + \mu_{k, k-1}^2 ||\mathbf{b}^*_{k-1}||^2$ （即违反 Lovász 条件，使用原始形式更稳定）: * 交换 (Swap): 交换 $\mathbf{b}_{k-1}$ 和 $\mathbf{b}_k$ 。 * 更新 GSO: 由于基向量交换，GSO 向量 $\mathbf{b}^*_{k-1}, \mathbf{b}^*_k$ 和相关系数 $\mu$ (如 $\mu_{k, k-1}$ , $\mu_{i, k-1}$ , $\mu_{i, k}$ for $i>k$ ) 需要重新计算或更新。（有高效的更新公式，避免完全重新计算 GSO）。 * 递减 $k$ : 将 $k$ 更新为 $\max(2, k-1)$ 。然后返回到步骤 2 的开头 (继续处理当前 $k$ 或 $k=2$ )。 iii. 如果 Lovász 条件满足： * 递增 $k$ : 将 $k$ 更新为 $k+1$ 。然后返回到步骤 2 的开头 (处理下一个向量)。
终止: 当 $k > n$ 时，算法终止。当前的基 $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ 就是 LLL 约化基。

伪代码 (简化版):#

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 算法倾向于找到短且近似正交的基。

3.5 LLL 算法的性质与分析#

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 算法的核心理论贡献。

3.6 LLL 算法的变种与改进#

原始 LLL 算法自提出以来，已被广泛研究和改进：

不同 $\delta$ 参数的选择: $\delta$ 越接近 1，Lovász 条件越严格，期望输出的基质量越高（ $\mathbf{b}_1$ 可能更短），但算法运行时间可能增加。 $\delta$ 必须大于 1/4 以保证理论性质。 $\delta=3/4$ 是常用平衡点。 $\delta=1$ 附近的选择通常用于启发式或与其他算法结合。
浮点数 LLL (Floating-point LLL): 使用浮点数进行 GSO 计算和系数处理，速度快，是许多实际应用中的首选。但需要仔细处理精度误差，否则可能导致算法不终止或输出不正确的基。有研究工作分析和控制浮点 LLL 的稳定性。
精确整数算术 LLL (Exact Arithmetic LLL): 使用有理数或大整数算术，避免精度问题，保证结果的正确性和算法的终止性。但计算成本较高，特别是当系数变大时。常用于需要严格保证结果的场合（如密码分析）。
Deep Insertion: LLL 原始版本只在相邻向量 $\mathbf{b}_{k-1}, \mathbf{b}_k$ 之间进行交换。Deep Insertion 是一种变体，允许将向量 $\mathbf{b}_k$ 插入到基中更靠前的位置 (例如，与 $\mathbf{b}_j$ , $j<k-1$ 交换)，如果这样能更好地满足约化条件。这可能产生质量更高的基，但算法分析更复杂。
LLL with Sieving/Enumeration: LLL 可以作为更强算法（如 BKZ）的预处理步骤或子程序。也可以结合枚举 (enumeration) 或筛法 (sieving) 来进一步改进 LLL 输出的第一个向量 $\mathbf{b}_1$ 的长度。

3.7 LLL 算法的影响与局限性#

影响：

理论突破: LLL 是第一个在任意维度上均具有多项式时间复杂度的格基约化算法，它证明了近似 SVP 和近似 CVP 在指数因子下是“容易”的。
密码分析工具: LLL 算法及其变种是攻击许多密码系统的强大工具，包括：
- 背包密码系统: LLL 被用于破解 Merkle-Hellman 等早期背包公钥密码。
- 低指数 RSA: Coppersmith 方法利用 LLL 寻找模 $N$ 的小根，可以攻击某些配置下的 RSA（如公钥指数 $e$ 较小，或部分消息已知）。
- NTRU 和其他格密码: LLL/BKZ 用于评估 NTRU 等格密码方案的实际安全性，通过尝试找到短向量来恢复密钥。
- 旁道攻击: LLL 可用于分析旁道泄露信息（如功耗、时间），例如在差分功耗分析 (DPA) 中恢复密钥。
数论与代数: LLL 在数论中有广泛应用，例如：
- 寻找整数关系: 给定一组实数 $x_1, \dots, x_n$ ，找到一组不全为零的整数 $c_1, \dots, c_n$ 使得 $\sum c_i x_i = 0$ (或非常接近 0)。这可以通过构造一个特定格并应用 LLL 实现（例如 PSLQ 算法就与此相关）。
- 多项式因子分解: LLL 算法最初就是为解决有理数上多项式因子分解问题而提出的。
其他领域: LLL 在整数规划、编码理论（解码）、通信（信号处理）等领域也有应用。

局限性:

近似因子: LLL 提供的近似因子 $\gamma = 2^{O(n)}$ 是指数级的。对于许多应用（尤其是需要高质量解的密码分析或优化问题），这个因子太大了。例如，要破解许多现代格密码参数，需要比 LLL 好得多的近似因子（通常需要次指数级或更小）。
最短向量不保证是第一个: LLL 保证第一个输出向量 $\mathbf{b}_1$ 相对较短，但不保证它就是格中最短的向量 $\lambda_1(\mathcal{L})$ 。最短向量可能隐藏在基中其他向量的线性组合中。
基的质量依赖于输入: LLL 输出的基的质量也可能受到输入基的初始状态和向量顺序的影响。

尽管存在局限性，LLL 算法仍然是格算法领域最基础和最重要的工具之一。它是理解更高级算法（如 BKZ）的基础，并且在许多实际场景中，它提供的近似解已经足够有用。LLL 的提出标志着计算格理论一个新时代的开始。下一章我们将探讨旨在克服 LLL 局限性、获得更好约化质量的 BKZ 算法。

第四章：高级格约化算法：BKZ 算法#

LLL 算法在多项式时间内提供了一个有用的格基约化结果，但其输出基的质量（以近似因子衡量）随着维度 $n$ 指数级增长，这在许多应用场景（特别是密码分析）中是不够的。为了获得更高质量的约化基（即基向量更短、更接近正交），研究者们发展了更强大的算法，其中最著名和最常用的是 BKZ 算法 (Block Korkine-Zolotarev Algorithm)。本章将介绍 BKZ 算法的动机、原理、流程及其性质。

4.1 BKZ 算法的动机：超越 LLL 的约化质量#

LLL 算法的 Lovász 条件本质上是一个“局部”条件，它只比较了相邻 GSO 向量 $\mathbf{b}^*_i$ 和 $\mathbf{b}^*_{i-1}$ 的长度（或相关的投影长度）。这种局部性是 LLL 能够在多项式时间内完成的原因，但也限制了它发现全局最优结构（如最短向量或非常正交的基）的能力。

为了获得更好的约化效果，需要引入更强的“全局”或至少是“半全局”的约化概念。一个自然的想法是考虑 HKZ 约化 (Hermite-Korkine-Zolotarev reduction)。

定义 4.1 (HKZ 约化基)#

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

尺寸约化: $|\mu_{ij}| \le 1/2$ 对所有 $1 \le j < i \le n$ 。
递归最短向量条件: 对于每个 $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 块 (Block) 的概念与块状 Korkine-Zolotarev (BKZ) 约化#

BKZ 算法引入了一个关键参数：块大小 (Blocksize)，通常记作 $\beta$ (一个整数，通常 $2 \le \beta \le n$ )。BKZ 算法的目标是找到一个基，使得该基在所有维度为 $\beta$ 的“块”上都近似满足 HKZ 条件。

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

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

尺寸约化: $|\mu_{ij}| \le 1/2$ 对所有 $1 \le j < i \le n$ 。
块状 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) 来找到块内投影格的最短向量，然后用这个短向量来改进当前的基。

4.3 BKZ 算法流程#

BKZ 算法是一个迭代过程，通常包含一个外层循环（遍历块）和一个内层核心步骤（调用 SVP 预言机并更新基）。LLL 算法通常作为 BKZ 的子程序或预处理步骤。

输入： 格 $\mathcal{L}$ 的一组基 $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ ，块大小 $\beta$ ( $2 \le \beta \le n$ )，（可选）参数 $\delta$ (通常接近 1 或 1)，（可选）停止条件（如最大迭代次数或质量改进阈值）。 输出： 一个近似 BKZ- $\beta$ 约化的基 $\mathbf{B}'$ 。

算法概述：

预处理 (可选): 对输入基 $\mathbf{B}$ 执行 LLL 约化（例如，使用 $\delta=0.99$ ）。
主循环 (迭代): 重复执行以下步骤直到满足停止条件： a. 设置一个标志 progress = false。 b. 遍历块: 对于块起始索引 $k = 1, \dots, n-1$ （有时是 $n-\beta+1$ ，或随机选择块）： i. 构造投影子格: 考虑当前基 $\mathbf{B}$ 和对应的 GSO $\mathbf{B}^*$ 。定义投影 $\pi_k: \mathbb{R}^n \to \text{span}(\mathbf{b}^*_k, \dots, \mathbf{b}^*_n)$ 。构造一个秩最多为 $\beta' = \min(\beta, n-k+1)$ 的投影格 $\mathcal{L}'_{k, \beta'}$ ，它由向量 $\pi_k(\mathbf{b}_k), \dots, \pi_k(\mathbf{b}_{k+\beta'-1})$ 生成。这个格实际上位于 $\text{span}(\mathbf{b}^*_k, \dots, \mathbf{b}^*_{k+\beta'-1})$ 中。 ii. 调用 SVP 预言机: 在这个 $\beta'$ 维的投影格 $\mathcal{L}'_{k, \beta'}$ 上调用一个 SVP 算法（精确或近似的，如枚举 Enum 或筛法 Sieve），找到其最短非零向量 $\mathbf{v}^*$ 。（注意： $\mathbf{v}^*$ 是在 $\text{span}(\mathbf{b}^*_k, \dots, \mathbf{b}^*_{k+\beta'-1})$ 中的向量）。 iii. 检查改进: 比较找到的短向量长度 $||\mathbf{v}^*||$ 与当前 GSO 向量长度 $||\mathbf{b}^*_k||$ 。如果 $||\mathbf{v}^*||^2 < (\delta - \epsilon) ||\mathbf{b}^*_k||^2$ （其中 $\delta$ 是目标参数， $\epsilon$ 是一个小的容差或 0），则认为找到了一个显著更短的向量。 iv. 插入短向量并更新基: 如果找到了更短的向量 $\mathbf{v}^*$ ： * 将 $\mathbf{v}^*$ 提升 (lift) 回 $\mathbb{R}^n$ 中的一个格向量 $\mathbf{v} \in \mathcal{L}$ ，使得 $\pi_k(\mathbf{v}) = \mathbf{v}^*$ 。这个 $\mathbf{v}$ 可以表示为 $\mathbf{b}_k, \dots, \mathbf{b}_{k+\beta'-1}$ 的整数线性组合。 * 将向量 $\mathbf{v}$ 插入到基 $\mathbf{B}$ 中的位置 $k$ 处（或附近），并将原有的某个向量（通常是 $\mathbf{b}_k$ 或块中其他向量）移除或调整，以保持基的性质。这通常涉及复杂的基变换操作。一种常见方法是将 $\mathbf{v}$ 插入到 $k$ 位置，然后将原来的 $\mathbf{b}_k, \dots, \mathbf{b}_{k+\beta'-1}$ 调整到 $k+1, \dots$ 位置，并可能需要重新约化这个块。 * 更新 GSO 信息。 * 设置 progress = true。 v. LLL 子调用 (重要): 在每次块处理（无论是否插入新向量）之后，通常会对整个基 $\mathbf{B}$ （或至少是受影响的部分）执行一次 LLL 约化（可能使用较大的 $\delta$ 值，如 0.99）。这有助于维持基的整体约化性质，并传播局部改进。
c. 检查停止条件: 如果在一整轮遍历所有块后 progress == false（或者达到最大迭代次数），则算法终止。

核心步骤：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 预言机。

4.4 BKZ 算法的性质与分析#

约化质量:

BKZ- $\beta$ 算法输出的基的质量显著优于 LLL。第一个基向量 $\mathbf{b}_1$ 的长度 $||\mathbf{b}_1||$ 与 $\lambda_1(\mathcal{L})$ 的关系可以用 Hermite 常数 $\gamma_\beta$ 来界定。理论上，BKZ- $\beta$ 可以达到近似因子 $\gamma \approx (\gamma_\beta)^{\frac{n-1}{\beta-1}}$ 。由于 $\gamma_\beta \approx \beta / (2\pi e)$ （渐进行为），当 $\beta$ 增大时，这个近似因子会减小。
渐进正交性 (Geometric Series Assumption, GSA): 实践中观察到，对于高质量的 BKZ 约化基，GSO 向量长度 $||\mathbf{b}^*_i||$ 倾向于形成一个几何级数，即 $||\mathbf{b}^*_i|| \approx r^{i-1} ||\mathbf{b}^*_1||$ 对于某个公比 $r$ （ $r$ 与 $\delta$ 和 $\beta$ 相关）。GSA 是一个启发式假设，但它有助于估计 BKZ 算法能达到的最短向量长度。根据 GSA，可以估计 BKZ- $\beta$ 找到的第一个向量长度约为 $||\mathbf{b}_1|| \approx (\delta_\beta)^{(n-1)/2} \det(\mathcal{L})^{1/n}$ ，其中 $\delta_\beta$ 是与块大小 $\beta$ 相关的“根 Hermite 因子”， $\delta_\beta = (\gamma_\beta)^{1/\beta}$ 。当 $\beta$ 增加时， $\delta_\beta$ 趋近于 1，表明基向量长度接近 Minkowski 界限。

计算复杂性:

BKZ 算法的复杂性主要由 SVP 预言机决定。如果使用枚举，每次调用 SVP 预言机需要 $\beta^{O(\beta)}$ 或 $2^{O(\beta^2)}$ 时间。如果使用筛法，需要大约 $2^{O(\beta)}$ 时间和空间。
算法需要执行多少次 SVP 调用？外层循环的次数难以精确界定，但通常认为它关于 $n$ 是多项式的（或者在实践中收敛很快）。
因此，BKZ- $\beta$ 算法的总时间复杂度大致是 $poly(n) \times T_{SVP}(\beta)$ ，其中 $T_{SVP}(\beta)$ 是求解 $\beta$ 维 SVP 的时间。这通常是 关于 $\beta$ 指数级增长 的，而关于 $n$ 是多项式增长。
结论： BKZ 算法通常 不是多项式时间算法（除非 $\beta$ 是常数或 $O(\log n)$ ）。块大小 $\beta$ 提供了一个时间和质量之间的权衡。选择更大的 $\beta$ 可以获得更高质量的约化基（更接近 SVP 解），但需要指数级增加的计算时间。

4.5 BKZ 2.0 及其他现代进展#

BKZ 2.0 [CN11]: Chen 和 Nguyen 提出的 BKZ 2.0 对原始 BKZ 进行了改进。它在块处理中不仅寻找最短向量，而是试图使块内的基向量更接近 HKZ 约化状态。他们提供了更严格的分析，表明 BKZ 2.0 在某些假设下可以达到更好的理论保证，并且在实践中也表现出良好的性能。
渐进 BKZ (Progressive BKZ): 一种策略是逐渐增加块大小 $\beta$ 。从较小的 $\beta$ (如 $\beta=20$ ) 开始运行 BKZ，得到一个初步约化的基，然后增加 $\beta$ (如 $\beta=30$ ) 继续运行，以此类推。这可以在总时间可控的情况下逐步提高基的质量。
自适应 BKZ: 根据当前基的状态或找到的短向量情况，动态调整 SVP 预言机的参数（如剪枝系数）或块的选择策略。
与 Pruning 结合: 为了加速 SVP 预言机（特别是枚举），可以使用各种剪枝 (pruning) 技术，牺牲找到最优解的概率来换取速度。这使得在实践中可以使用更大的有效块大小。

总结: BKZ 算法是当前格基约化的主力算法，特别是在需要高质量解的应用（如密码分析）中。它通过在局部块上求解 SVP 问题来逐步改进整个基的质量。块大小 $\beta$ 是控制算法性能和输出质量的关键参数，提供了在计算时间和约化程度之间的灵活权衡。虽然其复杂度通常是指数级的（在 $\beta$ 上），但它显著优于 LLL，并且是许多现代格密码安全性评估和攻击的基础。了解 BKZ 的原理和权衡对于理解格密码的实际安全性至关重要。

第五章：求解 SVP 和 CVP 的精确与启发式算法#

前面的章节介绍了 LLL 和 BKZ 等格基约化算法，它们旨在找到格的“好”基，并能给出 SVP 和 CVP 的近似解。然而，在某些情况下，我们需要找到这些问题的 精确解，或者至少是比 LLL/BKZ 能保证的更好的近似解。例如：

BKZ 算法本身就需要一个（近似或精确的）SVP 预言机 来处理其核心的块约化步骤。
在密码分析中，有时需要找到格中的精确最短向量或非常接近的向量来破解密码系统。
理论研究需要理解 SVP/CVP 精确解的复杂性极限。

本章将介绍几类用于解决 SVP 和 CVP 的更专门化的算法，包括精确算法（如枚举）和当前最优的启发式算法（如筛法）。

5.1 枚举算法 (Enumeration)#

枚举算法是最早被提出的解决 SVP 和 CVP 的精确（或高质量近似）算法之一。其基本思想是在一个有界的空间区域内系统地搜索所有相关的格点。

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$ 的不等式。

确定 $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]$ 内。
递归确定 $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$ 。
搜索树: 这个过程可以看作是在一个搜索树上进行深度优先搜索。树的第 $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 枚举的一个简化（贪心）版本，它只考虑一个解（通过舍入系数得到），但可以在多项式时间内完成，给出近似解。

5.2 筛法 (Sieving)#

筛法是另一类解决 SVP（主要是 SVP）的算法，尤其在较高维度下，它们通常比枚举算法更快（尽管是启发式的）。筛法的基本思想是通过生成大量的格点，然后利用格的加法群结构（两格点之差仍是格点）来找到短向量。

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

生成样本点: 随机生成大量的格点。一种方法是选取随机的整数系数向量 $\mathbf{c}$ ，计算 $\mathbf{v} = \mathbf{B} \mathbf{c}$ 。为了使生成的点不至于太长，通常会限制系数 $\mathbf{c}$ 的范围，或者使用某种随机游走 (random walk) 的方法在格上生成点。目标是生成一个包含许多“相对较短”的向量的列表 $L$ 。
中心化: 将列表 $L$ 中的所有向量都减半（这可能不再是格点），即 $L' = \{ \mathbf{v}/2 \mid \mathbf{v} \in L \}$ 。
寻找碰撞 (或接近碰撞): 在列表 $L'$ 中寻找两个向量 $\mathbf{v}'_1, \mathbf{v}'_2 \in L'$ ，它们彼此非常接近。可以使用某种最近邻搜索 (Nearest Neighbor Search, NNS) 的数据结构（如 Locality Sensitive Hashing, LSH）来加速这个过程。
构造更短向量: 如果找到了两个足够近的向量 $\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$ 中的向量更短。
迭代: 将新找到的更短向量（如 $\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.3 Voronoi 单元与 CVP 求解#

对于 CVP 问题，除了枚举之外，还有一个理论上重要的方法涉及到 Voronoi 单元 (Voronoi Cell)。

定义 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 算法 (理论上):#

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

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

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

第六章：格算法在密码学中的应用#

格理论与算法在密码学领域扮演着越来越重要的角色，无论是在构造新的密码系统方面，还是在分析现有密码系统的安全性方面。尤其在后量子密码学 (PQC) 的浪潮下，基于格的密码学 (Lattice-based Cryptography, LBC) 已成为最有希望抵御量子计算机攻击的主流方向之一。本章将探讨格算法在密码学中的广泛应用。

6.1 格密码学的兴起#

背景：量子计算的威胁#

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

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) 的。

格密码的优势#

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

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

6.2 基于格的密码体制构造#

基于格的困难问题，研究者们设计了多种密码体制，包括公钥加密、密钥封装机制 (KEM)、数字签名等。

早期尝试：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$ $∣ e^{T} 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$ $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$ $m$ 和签名 $(\mathbf{z}, c)$ $(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 格上的标准短向量问题。

6.3 全同态加密 (Fully Homomorphic Encryption, FHE)#

FHE 是密码学的一个“圣杯”，它允许第三方在不知道私钥的情况下，对加密的数据执行任意计算（例如，加法和乘法），得到的结果解密后与在原始明文上执行相同计算的结果一致。

概念: $Enc(m_1) \oplus Enc(m_2) \to Enc(m_1 + m_2)$ ， $Enc(m_1) \otimes Enc(m_2) \to Enc(m_1 \times m_2)$ 。
挑战: 主要挑战在于，每次对密文进行运算（尤其是乘法）时，密文中嵌入的“噪声”或“错误”会增长。如果噪声增长过大，解密就会失败。
Gentry 的突破 (2009) [Gen09]: Craig Gentry 提出了第一个可行的 FHE 方案。其核心思想是：
1. 构造一个“有点同态”的加密方案 (Somewhat Homomorphic Encryption, SHE): 这个方案可以支持有限次数（例如 $d$ 次）的乘法运算，噪声不会增长到无法解密的程度。Gentry 最初使用了基于 理想格 (Ideal Lattices) 的方案。
2. 引入“解密引导” (Bootstrapping): 当噪声快要变得太大时，使用一个巧妙的技术：同态地执行解密电路。假设有一个密文 $c = Enc_{pk}(m)$ ，其噪声很大。接收者将用于解密的私钥 $sk$ 也用公钥 $pk$ 加密，得到 $Enc_{pk}(sk)$ 。然后，同态地计算解密函数 $Dec(\cdot, \cdot)$ ： $c' = Eval_{pk}(Dec, Enc_{pk}(sk), c)$ 。由于 $Dec(sk, c) = m$ ，并且 $Eval$ 是同态的， $c'$ 理论上应该是 $Enc_{pk}(m)$ 的一个新密文。关键在于，如果解密电路本身的复杂度（乘法深度）小于 SHE 方案能支持的深度 $d$ ，那么新密文 $c'$ 的噪声会被“重置”到一个较低的水平。
3. 循环安全性 (Circular Security): Bootstrapping 需要假设用公钥加密私钥是安全的，这称为循环安全性假设。
基于 LWE/RLWE 的 FHE 方案: Gentry 的原始方案效率较低。后续的研究利用 LWE/RLWE 构造了更高效的 SHE 方案，并改进了 Bootstrapping 技术。主要的 FHE 方案流派包括：
- BGV (Brakerski-Gentry-Vaikuntanathan, 2011): 基于 RLWE，引入了 模数切换 (Modulus Switching) 和 密钥切换 (Key Switching) 技术来控制噪声增长，显著提高了效率。
- BFV (Brakerski/Fan-Vercauteren, 2012): 也是基于 RLWE，采用了不同的噪声管理技术（尺度不变性），通常在整数或二进制运算上表现较好。
- CKKS (Cheon-Kim-Kim-Song, 2017): 基于 RLWE，但设计用于对 近似数 (浮点数或实数) 进行同态计算。它允许一定的计算误差以换取更高的效率和处理实数数据的能力。非常适用于隐私保护机器学习等场景。
格在 FHE 中的核心作用: LWE/RLWE 问题的代数结构（线性性和允许加入可控噪声）天然地适合构造 (S)HE 方案。噪声管理技术（如模数切换、密钥切换）也依赖于格的性质。可以说，没有格理论和算法的发展，实用的 FHE 方案可能至今仍未出现。

6.4 格算法在密码分析中的应用 (Cryptanalysis)#

除了用于构造密码系统，格算法（尤其是 LLL 和 BKZ）也是分析密码系统安全性的强大武器。

攻击早期背包密码系统: LLL 算法最初的动机之一就是攻击 Merkle-Hellman 等基于背包问题（子集和问题）的公钥密码系统。这些系统可以被转化为格上的 SVP 或 CVP 问题，然后用 LLL 求解。
攻击低指数 RSA (Coppersmith 方法): Don Coppersmith (1996) 展示了如何利用 LLL 算法找到模 $N$ $N$ 的多项式方程的小整数根。这导致了对 RSA 的多种攻击：
- 小公钥指数 $e$ 攻击: 如果 $e$ 很小（例如 $e=3$ ），并且明文 $m$ 的一部分已知（例如高位或低位），Coppersmith 方法可以恢复整个明文 $m$ 。
- 相关密钥攻击: 如果两个用户使用相同的模 $N$ 但相关的私钥 $d_1, d_2$ 。
- 短填充攻击: 如果 RSA 填充方案不当，导致加密的消息 $m^e \pmod N$ 的一部分已知或具有某种结构。 Coppersmith 方法的核心是构造一个特定的格，使得该格中的短向量对应于多项式方程的小根。然后使用 LLL 找到这些短向量。
攻击旁路密码分析中的格方法: 格算法也被用于分析通过旁道（如功耗、时间、电磁辐射）泄露的信息。
- 例如，在差分功耗分析 (DPA) 攻击某些分组密码实现时，攻击者可能得到关于密钥 $k$ 的若干线性约束，形如 $\langle \mathbf{a}_i, \mathbf{k} \rangle \approx b_i$ （带有噪声）。这与 LWE 问题非常相似，可以用格算法（如将问题转化为 CVP 或 BDD）来求解，恢复密钥 $\mathbf{k}$ 。
评估格密码体制的实际安全性: 对于新提出的基于格的密码方案，必须使用当前最强的格约化算法（如 BKZ 配合筛法或枚举）来评估其安全性。研究者会根据方案参数（维度 $n$ 、模数 $q$ 、错误分布等）构造相应的格问题实例（SVP、CVP、LWE、SIS 等），然后估计使用 BKZ- $\beta$ 算法（对于某个实际可行的块大小 $\beta$ ）解决该实例所需的计算时间。如果所需时间超过了可接受的安全级别（例如 $2^{128}$ 次经典运算），则认为该参数是安全的。这种评估是 NIST PQC 标准化过程中确定安全参数的关键环节。例如，对于 LWE 问题 $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b} \pmod q$ ，攻击者可以构造一个格，其基包含 $\mathbf{A}$ 和 $q\mathbf{I}$ 的信息。在这个格中寻找特定的短向量（与 $(\mathbf{e}, \mathbf{s})$ 相关）可以恢复秘密 $\mathbf{s}$ 。BKZ 算法被用来寻找这个短向量。算法能达到的最短向量长度（由块大小 $\beta$ 决定）直接影响了攻击的成功率和所需样本数量。

总结: 格算法与密码学已经深度融合。一方面，格问题的困难性为后量子密码和高级密码功能（如 FHE）提供了坚实的基础。另一方面，LLL、BKZ 等格算法是分析这些密码系统以及其他传统密码系统（如 RSA）安全性的必备工具。理解格算法的能力和局限性，对于设计安全可靠的现代密码系统至关重要。

第七章：格算法在其他领域的应用#

虽然密码学是格算法最引人注目的应用领域之一，但其影响远不止于此。格的结构和相关算法在数学、计算机科学和工程学的其他多个分支中也找到了用武之地。本章将简要介绍格算法在一些其他领域中的应用。

7.1 编码理论 (Coding Theory)#

编码理论研究如何在有噪声的信道中可靠地传输信息。线性码 (Linear Code) 是编码理论中的一个重要类别，它可以被看作是有限域（如 $\mathbb{F}_2$ ）上的向量空间。某些解码问题可以与格上的 CVP 问题建立联系。

最大似然解码 (Maximum Likelihood Decoding, MLD): 接收端收到一个可能带噪的信号 $\mathbf{y}$ (通常是 $\mathbb{R}^n$ 中的向量)，目标是找到原始发送的码字 $\mathbf{c}$ (属于码字集 $C$ )，使得 $\mathbf{y}$ 在给定信道模型下最有可能由 $\mathbf{c}$ 产生。对于加性高斯白噪声 (AWGN) 信道，MLD 等价于找到离接收向量 $\mathbf{y}$ 最近的码字 $\mathbf{c}$ （在欧几里得距离下）。
格与线性码: 某些类型的线性码（例如，通过 Construction A 从格构造的码，或者某些代数几何码）具有与格密切相关的结构。对于这些码，或者通过将码字嵌入到欧几里得空间中，MLD 问题可以转化为一个格上的 CVP 问题。
Sphere Decoding: Sphere Decoding 是一种用于通信系统（如 MIMO 系统）的 MLD 算法。它本质上是一种 CVP 的枚举算法。它在一个以接收信号 $\mathbf{y}$ 为中心、半径不断增大的球内搜索格点（代表可能的发送符号组合）。LLL 或其他格约化算法可以用来预处理信道矩阵（相当于格的基），使得 Sphere Decoding 的搜索效率更高。

7.2 整数规划 (Integer Programming, IP)#

整数规划问题要求在一个由线性不等式定义的多面体区域内找到一个整数点，使得某个线性目标函数最优（最大化或最小化）。这是一个经典的 NP-hard 问题。

Lenstra 的算法 (1983): Hendrik Lenstra, Jr. 证明了在 固定维度 $n$ 下，整数规划问题可以在多项式时间内解决 [Len83]。他的算法中一个关键步骤就使用了 LLL 算法。
算法思想: 算法试图找到一个变换，使得可行域（多面体）在一个方向上“很宽”，而在其他 $n-1$ 个方向上“很窄”。如果可行域在一个方向上足够宽，那么可以沿这个方向分解问题。如果可行域在所有方向上都很“窄”（即它包含在一个“扁平”的椭球内），Lenstra 使用格基约化（LLL）来找到一个好的基，然后通过枚举该基对应的少量超平面来覆盖所有可能的整数解。
意义: 虽然这个算法的复杂度随着维度 $n$ 指数级增长（因此对于一般 IP 不实用），但它在理论上首次证明了固定维度的 IP 是多项式时间可解的，并且展示了格算法在解决这类优化问题中的潜力。

7.3 数论 (Number Theory)#

格算法在计算数论的多个方面都有应用。

丢番图逼近 (Diophantine Approximation): 寻找有理数 $p/q$ 来很好地逼近给定的实数 $\alpha$ 。这可以转化为在一个二维格（例如由 $(1, 0)^T$ 和 $(\alpha, \epsilon)^T$ 生成， $\epsilon$ 是小数）中寻找短向量的问题。LLL 可以找到好的有理逼近。
寻找整数关系 (Integer Relation Finding): 给定一组实数 $x_1, \dots, x_n$ $x_{1}, \dots, x_{n}$ ，找到一组不全为零的整数 $c_1, \dots, c_n$ $c_{1}, \dots, c_{n}$ 使得线性组合 $\sum_{i=1}^n c_i x_i = 0$ $\sum_{i = 1}^{n} c_{i} x_{i} = 0$ （或非常接近 0）。这是一个基本问题，在实验数学（例如，识别一个数是否是某个已知常数的代数组合）和物理学中都有应用。
- PSLQ 算法: 是解决整数关系问题的著名算法之一。虽然 PSLQ 本身不直接基于 LLL，但它与格基约化的思想密切相关。
- 基于 LLL 的方法: 可以构造一个 $n+1$ 维的格，例如基为： $\mathbf{b}_1 = (1, 0, \dots, 0, M x_1)^T$ $\mathbf{b}_2 = (0, 1, \dots, 0, M x_2)^T$ … $\mathbf{b}_n = (0, 0, \dots, 1, M x_n)^T$ $\mathbf{b}_{n+1} = (0, 0, \dots, 0, M \times \epsilon)^T$ (或类似结构，M是大数) 在这个格中寻找一个短向量 $\mathbf{v} = \sum c_i \mathbf{b}_i$ (且 $c_{n+1}$ 不为零)，它的最后一个分量 $M (\sum_{i=1}^n c_i x_i + c_{n+1} \epsilon)$ 会非常小。如果 $\epsilon$ 足够小，这意味着 $\sum_{i=1}^n c_i x_i \approx 0$ 。LLL 算法可以用来找到这样的短向量，从而发现整数关系。
代数数论: 在计算代数数域的单位群、类群等结构时，需要处理与数域相关的格（例如，通过 Minkowski 嵌入将代数整数映射到 $\mathbb{R}^n$ 中形成格）。寻找这些格中的短向量或约化基是这些计算中的一个子任务。

7.4 计算机图形学与模式识别中的应用简介#

虽然不是主流应用，但格的概念有时也出现在这些领域：

计算机图形学: 在某些纹理生成、采样模式（如泊松盘采样）或周期性结构建模中，可能会用到格或类似离散点集的概念。
模式识别: 在特征空间中进行量化或聚类时，如果数据点呈现某种规则的离散结构，格模型可能提供一种描述方式。例如，向量量化 (Vector Quantization) 中的码书可以看作是一种广义的“格点”集合（虽然不一定是严格的格）。

总结: 格算法的应用范围广泛，超越了密码学的范畴。它们为解决编码理论中的解码问题、整数规划（理论上）、数论中的基本问题（如丢番图逼近和整数关系）提供了有力的计算工具。这些应用进一步证明了格理论作为数学和计算机科学交叉领域的基础性和重要性。

第八章：总结与未来展望#

本报告对格理论及其算法进行了系统性的介绍，涵盖了基础数学概念、核心计算难题、关键算法（LLL、BKZ、枚举、筛法）以及在密码学和其他领域的广泛应用。格算法领域正处于一个蓬勃发展的时期，其理论深度和实践影响力都在不断扩展。

格算法的核心贡献与地位:

连接几何与代数: 格理论巧妙地将欧几里得空间的几何结构与整数的代数结构联系起来，为研究离散几何问题提供了强大的框架。
计算复杂性理论: 格上的困难问题（SVP, CVP 等）已成为计算复杂性理论，尤其是 NP-hardness 和近似算法研究中的重要对象。
算法设计的里程碑: LLL 算法的提出是算法设计史上的一个里程碑，它首次为一类重要的几何优化问题（近似 SVP/CVP）提供了多项式时间的解决方案，并催生了大量后续研究。BKZ 等更高级算法则在效率和解质量之间提供了更精细的权衡。
现代密码学的基石: 格密码学已成为后量子密码研究的主流方向，有望在未来取代当前面临量子威胁的公钥密码体系。同时，格也是实现全同态加密等前沿密码学技术的关键。
跨学科工具: 格算法在数论、编码理论、优化等多个领域都发挥着重要作用。

当前研究热点:

更优的格算法:
- 改进 SVP/CVP 算法: 研究更快的精确或近似 SVP/CVP 算法，特别是改进筛法和枚举技术的效率（例如，降低指数常数，减少空间复杂度）。
- 更好的格基约化: 探索新的格基约化策略，试图在多项式时间内达到比 LLL 更好的近似因子，或者改进 BKZ 的效率和理论保证。
- 量子格算法: 研究量子计算机是否能显著加速解决格问题。虽然目前认为量子对格问题的加速不如对因子分解/离散对数那样具有颠覆性，但仍在积极探索中（如 Kuperberg 算法及其改进）。
更安全的格密码体制:
- 标准化与部署: 随着 NIST PQC 标准化的完成（第一批标准已发布），如何安全、高效地实现和部署 Kyber、Dilithium、Falcon 等基于格的标准方案成为关键问题。
- 安全性分析: 对标准方案及其他格密码提案进行更深入的密码分析，理解它们在面对当前最强格算法攻击（包括侧信道攻击）时的实际安全裕度。
- 新结构与新假设: 探索新的格结构（如基于不同代数结构的格）和可能更强的困难性假设，以设计出可能更高效或具有新功能的密码方案。
FHE 的效率与应用:
- 提高 FHE 性能: 降低 FHE 的计算开销（尤其是 Bootstrapping 的开销）和密文膨胀，使其在更广泛的应用场景中变得实用。
- FHE 应用: 将 FHE 应用于实际问题，如隐私保护机器学习、安全数据外包、多方安全计算等。
格与其他密码学原语的结合: 利用格构造更高级的密码学工具，如零知识证明（特别是简洁非交互式的 ZK-SNARKs/STARKs）、属性基加密、函数加密、安全多方计算协议等。

未解决的问题与挑战:

SVP/CVP 的精确复杂度: SVP 和 CVP 的精确计算复杂度仍未完全确定。它们是否属于 NP-intermediate（即既不在 P 也不 NP-complete）？对于近似版本，其困难性阈值（即哪个近似因子下问题从 NP-hard 变为 P）仍在研究中。
格密码的实际安全性: 尽管有最坏情况到平均情况的归约，但这些归约通常涉及较大的参数和近似因子。实际方案的安全性最终依赖于具体参数下，使用最优算法（如 BKZ+筛法）攻击的难度。精确评估这种实际难度仍然是一个挑战，需要不断改进算法和攻击实验。
侧信道攻击: 基于格的密码方案的物理实现（硬件或软件）可能容易受到侧信道攻击（如功耗分析、时间攻击）。设计和实现抗侧信道攻击的格密码方案是一个重要的实践挑战。
FHE 的实用性: 尽管 FHE 取得了巨大进展，但其性能开销仍然是阻碍广泛应用的主要障碍。实现接近明文计算速度的 FHE 仍然是一个长期目标。

量子计算对格算法的影响: 量子计算对格算法领域带来了双重影响：

威胁 (驱动力): 正是量子计算对传统公钥密码的威胁，极大地推动了基于格的后量子密码的研究。
机遇 (潜在的攻击与分析): 量子算法可能会提供解决格问题的新途径。虽然目前没有像 Shor 算法那样颠覆性的量子格算法，但研究仍在进行。例如，某些量子行走算法或量子筛法可能提供一定的加速。理解量子计算对格问题困难性的真实影响，对于准确评估格密码的长期安全性至关重要。

结语: 格算法领域是一个充满活力、理论深刻且应用广泛的研究方向。从 LLL 算法的诞生到后量子密码和全同态加密的蓬勃发展，格理论和算法不断展现出其强大的生命力。随着计算能力的提升、新算法思想的涌现以及应用需求的驱动，我们可以期待格算法在未来将继续在计算机科学、数学和信息安全等领域扮演关键角色，并带来更多的理论突破和技术创新。

前言#