密码学中的格（Lattice）理论数学基础
格的基本定义
\(格\)是欧几里得空间 ℝⁿ 中一组向量的所有整数线性组合构成的离散加法子群。形式化地，给定一组线性无关的向量 \(\mathbf{b}_1, \dots, \mathbf{b}_d \in \mathbb{R}^n\)，由它们生成的格定义为：
\(\mathcal{L} = \left\{ \sum_{i=1}^d x_i \mathbf{b}_i : x_i \in \mathbb{Z} \right\}\)
其中 \(d\) 称为格的秩，\(n\) 为空间维数。若 \(d=n\)，则称格为满秩格
格基与基变换
向量集合 \(B = \{\mathbf{b}_1, \dots, \mathbf{b}_d\}\) 称为格 \(\mathcal{L}\) 的一组基。同一个格可以由不同的基生成，这些基通过幺模变换相互关联：
若 \(B\) 和 \(B'\) 是同一格的两组基，则存在一个幺模矩阵 \(U \in \mathbb{Z}^{d \times d}\)（即满足 \(\det(U) = \pm 1\)），使得 \(B' = B \cdot U\)
行列式的几何意义
格的\(行列式\) \(\det(\mathcal{L})\) 定义为基向量构成的行列式的绝对值：
\(\det(\mathcal{L}) = |\det(B)|\)
几何上，它表示格的基本平行多面体（由基张成）的体积。行列式是格的不变量，与基的选取无关。当 \(d=n\) 时，\(\det(\mathcal{L})\) 等于 \(ℝ^n\) 空间中每个格点平均占有的体积的倒数，反映了格的密度
格点的稠密度
在满秩格中，格点在空间中的\(稠密度\)定义为每单位体积中的平均格点数，即：
\(\rho = \frac{1}{\det(\mathcal{L})}\)
直观上，行列式越小，格点越密集
最小距离与连续极小量
最小距离 \(\lambda_1(\mathcal{L})\) 是格中非零向量最短的欧几里得范数：
\(\lambda_1(\mathcal{L}) = \min_{\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}} \|\mathbf{v}\|\)
连续极小量 \(\lambda_i(\mathcal{L})\)（\(1 \leq i \leq d\)）定义为最小的实数 \(r\)，使得格中存在 \(i\) 个线性无关的向量，其范数均不超过 \(r\)：
\(\lambda_i(\mathcal{L}) = \min \{ r : \dim(\text{span}( \mathcal{L} \cap \overline{B}_r(0) )) \geq i \}\)
其中 \(\overline{B}_r(0)\) 是半径为 \(r\) 的闭球。显然 \(\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_d\)
向量范数与距离
格理论中常用的范数包括：
- \(欧几里得范数（ℓ²范数）\)：\(\|\mathbf{v}\|_2 = \sqrt{\sum v_i^2}\)
- \(最大值范数（ℓ∞范数）\)：\(\|\mathbf{v}\|_\infty = \max_i |v_i|\)
- 一般 ℓᵖ 范数
格上的困难问题
格密码学基于几个计算困难问题，对量子算法目前仍然安全：
-
最短向量问题\((SVP)\)：给定格基 \(B\)，找到非零格向量 \(\mathbf{v} \in \mathcal{L}(B)\) 使得 \(\|\mathbf{v}\| = \lambda_1(\mathcal{L})\)
-
近似最短向量问题\(（SVP-γ）\)：给定基 \(B\) 和近似因子 \(\gamma \geq 1\)，找到非零格向量 \(\mathbf{v}\) 满足 \(\|\mathbf{v}\| \leq \gamma \cdot \lambda_1(\mathcal{L})\)
-
最近向量问题\(（CVP）\)：给定格基 \(B\) 和目标向量 \(\mathbf{t} \in \mathbb{R}^n\)，找到格向量 \(\mathbf{v} \in \mathcal{L}(B)\) 最小化 \(\|\mathbf{v} - \mathbf{t}\|\)
-
有界距离解码问题\(（BDD/α）\)：CVP 的变种，承诺目标向量 \(\mathbf{t}\) 距离格至多为 \(\alpha \cdot \lambda_1(\mathcal{L})\)，其中 \(\alpha < 1/2\)
-
最短线性无关向量问题\(（SIVP）\)：找到 \(d\) 个线性无关的格向量，其最大长度不超过 \(\lambda_d(\mathcal{L})\) 的近似倍数