格密码、施密特正交化- \(Gram-Schmidt\ orthogonalization,GSO\)，施密特正交化。
- 施密特正交化生成的正交基(\(CSO\)基)通常不在格本身上，但它为我们分析格的几何性质（如行列式、基的质量、最短向量下界）提供工具。
- \(GSO\)是欧氏空间下的一个基本运算，核心思想是剥离投影，它接收任意一组\(n\)个线性无关向量\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\)，逐个将后续向量在前面已确定向量所张成的子空间上的投影分量扣除，从而得到相互垂直的正交向量序列\(\vec{b_1}^*,\vec{b_2}^*,\cdots,\vec{b_n}^*\)。
![[施密特正交化 (格).png]] - 设输入基矩阵的向量为\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\in\mathbb{R}^n\)：
- 第一个正交向量直接继承：\[\vec{b_1}^*=\vec{b_1} \]
- 对于\(i=2,3,\cdots,n\)，将\(\vec{b_i}\)减去它在前面所有正交向量\(\vec{b_1}^*,\vec{b_2}^*,\cdots,\vec{b_{i-1}}^*\)上的投影。
- 第一个正交向量直接继承：
- 定义6：对于\(n\)个线性无关向量\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\)序列，\(GSO\)后为\(\vec{b_1}',\vec{b_2}',\cdots,\vec{b_n}'\)向量序列，其中：\[\vec{b_i}^*=\vec{b_i}-\sum_{j=1}^{i-1}\mu_{i,j}\vec{b_j}^*;\mu_{i,j}={\left<{\vec{b_i},\vec{b_j}^*}\right>\over\left<\vec{b_j}^*,\vec{b_j}^*\right>}={\vec{b_i}\cdot\vec{b_j}^*\over\Vert{}\vec{b_j}^*\Vert{}^2} \]
- \(GSO\)的一些特性：
- 对于任意\(i≠j\)，有\(\left<\vec{b_i}^*,\vec{b_j}^*\right>=0\)；
- 对于所有\(1\leq i\leq n\)，\(span(\vec{b_1},\vec{b_2},\cdots,\vec{b_n})=span(\vec{b_1}^*,\vec{b_2}^*,\cdots,\vec{b_n}^*)\)；
- 向量序列\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\)的顺序很重要，这也是为什么我们称其为序列而非集合的原因。
- 为什么正交基通常不属于原来的格？
在格密码中，格\(\mathcal{L}(B)\)定义为整数线性组合：\[\mathcal{L}(B)=\{\sum_{i=1}^nx_i\vec{b_i}\vert{}x_i\in\mathbb{Z}\} \]当计算正交系数\(\mu_{i,j}\)时，往往涉及分数/实数出发，导致\(\mu_{i,j}\)通常是非整数。因为\(\vec{b_i}^*=\vec{b_i}-\sum_{j=1}^{i-1}\mu_{i,j}\vec{b_j}^*\)包含非整数系数，所以\(\vec{b_i}^*\)（除\(\vec{b_1}^*\)外）通常部署于格\(\mathcal{L}\)。 - 施密特正交化在格密码中主要有下列的应用：
- 矩阵分解与格的行列式：
设向量\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\)是\(\mathbb{R}^m\)中\(n\)个线性无关向量，并考虑\(\vec{b_1}^*/\Vert{}\vec{b_1}\Vert{},\vec{b_2}^*/\Vert{}\vec{b_2}\Vert{},\cdots,\vec{b_n}^*/\Vert{}\vec{b_n}\Vert{}\)给出的正交基。在此基础上，给出向量\(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}\)，并作\(m×n\)矩阵的列：\[\left(\begin{matrix}\Vert{}\vec{b_1}^*\Vert{} & \mu_{2,1}\Vert{}\vec{b_1}^*\Vert{} & \cdots & \mu_{n-1,1}\Vert{}\vec{b_1}^*\Vert{} & \mu_{n,1}\Vert{}\vec{b_1}^*\Vert{}\\0 & \Vert{}\vec{b_2}^*\Vert{} & \cdots & \mu_{n-1,2}\Vert{}\vec{b_2}^*\Vert{} &\mu_{n,1}\Vert{}\vec{b_2}^*\Vert{}\\\vdots & \vdots & \ddots & \vdots & \vdots\\0 & 0 & \cdots & 0 & \Vert{}\vec{b_n}^*\Vert{}\\0 & 0 & \cdots & 0 & 0\\\vdots & \vdots & \ddots & \vdots & \vdots\\0 & 0 & \cdots & 0 & 0\end{matrix}\right) \]在\(m=n\)的情况下，这是一个上三角矩阵。从这种表示中，\(\mathcal{P}(\vec{b_1},\vec{b_2},\cdots,\vec{b_n})\)的\(volume\)（或等效的\(det(\mathcal{L}(\vec{b_1},\vec{b_2},\cdots,\vec{b_n}))\)）是由\(\prod_{i=1}^n\Vert{}\vec{b_i}^*\Vert{}\)给出的。事实上，这个等式可以看作是计算平行四边形面积的公式的\(n\)维扩展。 - 衡量基的质量
在格密码中，“好的基”指的是向量尽量短且接近相互垂直的基。正交性缺陷（Orthogonality Defect）定义为：\[\delta(B) = \frac{\prod_{i=1}^n \Vert{}\vec{b_i}\Vert{}}{\det(\mathcal{L})} = \frac{\prod_{i=1}^n \Vert{}\vec{b_i}\Vert{}}{\prod_{i=1}^n \Vert{}\vec{b_i}^*\Vert{}} \ge 1 \]- 当基完全正交时，\(\vec{b_i}^* = \vec{b_i}\)，\(\delta(B) = 1\)。
- 向量越倾斜、正交性越差，\(\Vert{}\vec{b_i}^*\Vert{}\) 相比于 \(\Vert{}\vec{b_i}\Vert{}\) 就越小，\(\delta(B)\) 越大。
- 求解\(SVP / CVP\)
在求解格的最短向量问题（\(SVP\)）或最近向量问题（\(CVP\)）时：- Babai 最近平面算法（Nearest Plane Algorithm）：直接利用\(GSO\)过程，将目标点依次沿 \(\vec{b_n}^*, \vec{b_{n-1}}^*, \cdots\) 寻找最近的格平面，从而得到\(CVP\)的近似解。
- SVP 下界估计：根据格的几何性质，格中任意非零向量 \(\vec{v} \in \mathcal{L}\) 的长度至少满足：\[\Vert{}\vec{v}\Vert{} \ge \min_{1 \le i \le n} \Vert{}\vec{b_i}^*\Vert{} \]这提供了极重要的格安全参数下界。
- \(LLL\)算法
\(LLL（Lenstra–Lenstra–Lovász）\)通过两个条件定义一组“好基”：- 尺寸约化条件（Size-reduced）：区间限制 \(\vert{}\mu_{i,j}\vert{} \le \frac{1}{2}\)（对所有 \(j < i\)）。
- Lovász 条件：保证正交向量长度下降不能太快：\[\Vert{}\vec{b_i}^*\Vert{}^2 \ge \left( \delta - \mu_{i,i-1}^2 \right) \Vert{}\vec{b_{i-1}}^*\Vert{}^2 \quad (\text{常取 } \delta = \frac{3}{4}) \]
- 矩阵分解与格的行列式：
格密码基础 —— Gram-Schmidt orthogonalization
