4. 格基约化算法
格密码的安全性几乎完全建立在“格中难找短向量”这一假设之上，而格基约化算法正是检验该假设的最有力工具。给定一组格基 B = {b₁, b₂, …, bₙ}，约化算法的目标是在不改变所张成格 L(B) 的前提下，把基变换成“更短、更正交”的一组向量。理解三类代表性算法——高斯约化、LLL 与 BKZ——的原理、复杂度与输出质量，是评估参数安全性的基础。
一、约化质量的衡量标准
约化算法并非追求“最短基”（这是 NP 难问题），而是追求可证明的近似质量。常用指标有两个：一是基向量长度比 ‖b*ᵢ‖/‖b*ᵢ₊₁‖ 的上界，二是首个基向量与格中真正最短向量之间的近似因子。LLL 保证 ‖b₁‖ ≤ 2^((n−1)/2) · λ₁(L)，这个指数级因子说明：维数越高，LLL 的输出离真正的最短向量越远，这正是 BKZ 存在的理由。
二、高斯约化：二维的精确解
高斯约化只处理二维格，却给出了一个漂亮的精确结果。设基为 (b₁, b₂)，算法反复执行两步：先做带余除法式约化 b₂ ← b₂ − round(⟨b₁,b₂⟩/⟨b₁,b₁⟩)·b₁，使 |⟨b₁,b₂⟩| ≤ ‖b₁‖²/2；若此时 ‖b₂‖ < ‖b₁‖，则交换两向量并重复。由于每次交换都严格缩短基向量，算法必然终止，且输出就是该二维格的最短向量。它是理解“约化即不断缩短并正交化”这一思想的最小模型。
三、LLL：多项式时间的近似约化
LLL 把高斯约化的思想推广到 n 维，核心是 Gram-Schmidt 正交化与两个条件的维护。设 GSO 系数为 μᵢⱼ，LLL 要求基满足：
- 尺寸约化条件：对所有
j < i，|μᵢⱼ| ≤ 1/2； - Lovász 条件：
‖b*ᵢ₊₁ + μᵢ₊₁,ᵢ b*ᵢ‖² ≥ (δ − μ²ᵢ₊₁,ᵢ)·‖b*ᵢ‖²，常用δ = 3/4。
实现上通常维护 GSO 数据，循环做“尺寸约化—检查 Lovász—必要时交换并回退”。一个可参考的教学实现骨架如下（示例参数，非实测）：
输入: 基 B (n×n 整数矩阵), δ = 0.75
计算 GSO: b*, μ
k = 1
while k < n:
for j = k-1 downto 0:
q = round(μ[k][j])
if q != 0: b[k] -= q * b[j]; 更新 μ
if ‖b*[k]‖² ≥ (δ - μ[k][k-1]²) * ‖b*[k-1]‖²:
k += 1
else:
swap(b[k], b[k-1]); 重算局部 GSO; k = max(k-1, 1)
输出: 约化基 BLLL 的复杂度在经典模型下约为 O(n⁴ log B)（B 为基向量长度上界），使用快速算术可进一步降低。它的输出质量由 δ 控制：δ 越接近 1，基越短，但交换次数增多、运行更慢。实践中常取 δ = 0.99 以换取更好质量。
四、BKZ：用块内枚举换取更强约化
BKZ 的关键洞察是：LLL 之所以弱，是因为它只看相邻两个向量。BKZ 引入块大小 β，对每个长度为 β 的滑动窗口调用一次“强约化子程序”（通常是枚举求窗口内最短向量），再用得到的短向量去约化窗口外的向量。当 β = 2 时 BKZ 退化为 LLL；β 增大，输出质量迅速提升，但枚举代价随 β 指数增长。
BKZ 的复杂度可粗略分为两部分：枚举子程序约 2^O(β)，外层轮数约 O(n²/β²) 或更多。因此实际调参时，β 是唯一真正决定“安全评估强度”的旋钮。评估格密码参数时，常用 BKZ 的“根 Hermite 因子” δ₀(β) 来估算攻击者能达到的向量长度，进而与方案所依赖的 λ₁ 比较。
五、约化基在密码分析中的作用
约化基不是密码分析的终点，而是起点。典型用法有三类：其一，对 NTRU 类方案的公钥格直接约化，若约化后出现异常短的向量，说明参数偏弱；其二，在格基签名或加密的攻击中，先用 LLL/BKZ 把基“整理”到较好状态，再交给枚举或筛法寻找目标短向量；其三，用 BKZ 的预估质量反推安全位数，判断给定 (n, q, β) 下攻击者需要多少资源。
‖b₁‖ 与理论下界 λ₁ 估计值的比值。若该比值明显大于 1，说明当前 β 或 δ 不足，需要加大块大小或增加轮数。δ、β 与复杂度数值均为说明性假设，用于展示调参逻辑，不代表任何具体方案的实际破解结果。真实安全评估必须结合具体方案参数与最新攻击文献。综上，高斯约化给出二维精确解，LLL 以多项式时间换取指数级近似因子，BKZ 用可调的块枚举在质量与代价之间滑动。三者构成一条清晰的质量阶梯，而约化基的质量评估，正是把这条阶梯转化为密码参数安全结论的桥梁。