格基约减算法：LLL 与 BKZ 的原理与实现

Slug: lattice-reduction-algorithms-lll-bkz Category: algorithm Tags: ["格密", "LLL 算法", "BKZ 算法", "约减理论", "后量子密码"] Summary: 格基约减是格密码学的核心算法工具，LLL 算法与 BKZ 算法分别代表了多项式时间与启发式最优的不同 Trade-off。本文系统推导 LLL 与 BKZ 的数学原理，分析其时间复杂度与近似因子，并探讨它们在密码分析、密钥恢复和后量子密码安全参数选择中的实际应用。

概述

格（Lattice）是离散数学与密码学中的基础结构，定义为 $n$ 维欧氏空间中由一组基向量生成的离散加法子群。给定格的基矩阵 $B \in \mathbb{Z}^{m \times n}$，格 $L(B)$ 定义为所有整数线性组合 $\{\sum_{i=1}^{m} x_i b_i \mid x_i \in \mathbb{Z}\}$ 的集合。

格基约减（Lattice Basis Reduction）的核心问题是：给定一个格的任意基，寻找一组"短而正交"的等价基。约减后的基向量长度更接近格的最短非零向量（最短向量问题，SVP），这在密码分析中具有关键意义。

格基约减算法是现代密码学的基石：

• 格密码的安全性依赖于 SVP 和 CVP 的计算困难性，而约减算法提供了攻击这些问题的最已知最佳途径
• 后量子密码标准化的安全参数基于约减算法的最新进展确定
• 传统密码的分析（如 RSA 低指数攻击、NTRU 格攻击）大量依赖约减技术

LLL 与 BKZ 的对比概览

格的数学基础

格的定义与性质

定义 1（格）：设 $b_1, b_2, \ldots, b_m$ 是 $\mathbb{R}^n$ 中的线性无关向量（$m \leq n$），则集合 $$L(b_1, \ldots, b_m) = \left\{\sum_{i=1}^{m} x_i b_i \mid x_i \in \mathbb{Z}\right\}$$ 称为由基 $\{b_i\}$ 生成的格。向量 $b_i$ 称为格的基向量，$m$ 称为格的秩。

关键性质：

• 格是离散的：存在 $\delta > 0$ 使得格中任意两点距离 $\geq \delta$
• 格具有周期性：$L + v = L$ 当且仅当 $v \in L$
• 同一格可以有无穷多组不同的基

Gram-Schmidt 正交化

Gram-Schmidt 正交化是将非正交基转化为正交基的核心工具。

定义 2（Gram-Schmidt 正交化）：给定基 $\{b_1, \ldots, b_m\}$，定义正交化向量 $\{b_1^*, \ldots, b_m^*\}$ 递归地： $$b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{i,j} b_j^*, \quad \mu_{i,j} = \frac{\langle b_i, b_j^* \rangle}{\langle b_j^*, b_j^* \rangle}$$

其中 $\mu_{i,j}$ 称为 Gram-Schmidt 系数。

关键引理：对任意 $i$，有 $L(b_1, \ldots, b_i) = L(b_1^*, \ldots, b_i^*)$。这意味着 Gram-Schmidt 正交化不改变格本身，仅改变表示方式。

最短向量问题（SVP）与最近向量问题（CVP）

SVP（最短向量问题）：给定格 $L$ 的基 $B$，找到非零向量 $v \in L$ 使得 $\|v\|$ 最小，即： $$\lambda_1(L) = \min\{\|v\| : v \in L, v \neq 0\}$$

CVP（最近向量问题）：给定格 $L$ 的基 $B$ 和目标向量 $t \in \mathbb{R}^n$，找到格点 $v \in L$ 使得 $\|t - v\|$ 最小。

这两个问题是格密码学的安全基础：

• NTRU 的安全性基于 CVP 的困难性
• 基于格的 KEM（如 Kyber） 的安全性基于 Decision-LWE 问题，而 LWE 与 SVP/CVP 紧密相关
• 签名方案（如 Dilithium、Falcon） 的安全性依赖于短向量问题的困难性

LLL 算法：原理与实现

算法思想

LLL 算法由 Lenstra、Lenstra 和 Lovász 于 1982 年提出，是第一个在多项式时间内给出理论保证的格基约减算法。其核心思想是迭代地改善基的质量：通过检查 Gram-Schmidt 系数的 size-reduced 条件和 Lovász 条件，决定何时交换相邻基向量。

Size-Reduced 条件：基 $\{b_1, \ldots, b_m\}$ 是 size-reduced 的，当且仅当对所有 $i > j$，有 $|\mu_{i,j}| \leq 1/2$。

Lovász 条件：对任意 $k$，满足： $$\delta \|b_k^*\|^2 \leq \|\mu_{k+1,k} b_k^* + b_{k+1}^*\|^2$$ 其中 $\delta \in (1/4, 1)$ 是约减参数（通常取 $\delta = 3/4$）。

算法流程

输入：格的基 $B = (b_1, \ldots, b_m)$，参数 $\delta \in (1/4, 1)$

输出：LLL 约减基 $B' = (b_1', \ldots, b_m')$

Algorithm LLL(B, δ):
    1. 对 B 进行 Gram-Schmidt 正交化，得到 {b_i*} 和 {μ_{i,j}}
    2. k := 2
    3. while k ≤ m do:
        a. // Size-reduction step
           for j := k-1 downto 1 do:
               μ := ⟨b_k, b_j*⟩ / ⟨b_j*, b_j*⟩
               r := round(μ)
               b_k := b_k - r · b_j
               更新 μ_{k,j} := μ - r
        b. // Lovász condition check
           θ := ⟨b_k, b_{k-1}*⟩
           if δ·‖b_{k-1}*‖² ≤ ‖b_k*‖² + θ² then:
               k := k + 1
           else:
               // 交换 b_k 和 b_{k-1}
               swap(b_k, b_{k-1})
               更新 Gram-Schmidt 系数
               k := max(k-1, 2)
    4. return B

正确性证明思路

定理 1（LLL 正确性）：LLL 算法在有限步内终止，输出满足以下性质的基：

• Size-reduced：对所有 $i > j$，$|\mu_{i,j}| \leq 1/2$
• Lovász 条件：对所有 $k$，$\delta \|b_k^*\|^2 \leq \|\mu_{k+1,k} b_k^* + b_{k+1}^*\|^2$

近似因子分析

定理 2（LLL 近似因子）：LLL 约减基的第一个向量 $b_1$ 满足： $$\|b_1\| \leq 2^{(n-1)/2} \cdot \lambda_1(L)$$

证明：由 Lovász 条件，有 $\|b_k^*\|^2 \leq \frac{1}{\delta - 1/4} \|b_{k-1}^*\|^2$。取 $\delta = 3/4$，得 $\|b_k^*\| \leq 2 \|b_{k-1}^*\|$。递推得 $\|b_k^*\| \leq 2^{k-1} \|b_1^*\|$。

又由 Gram-Schmidt 正交性，$\|b_1\|^2 = \sum_{i=1}^{k} \mu_{i,1}^2 \|b_i^*\|^2 + \|b_1^*\|^2 \leq 2^{2(k-1)} \|b_1^*\|^2 \cdot \sum_{i=0}^{k-1} (1/4)^i < 2^{2(k-1)+1} \|b_1^*\|^2$。

而 $\lambda_1(L) \geq \|b_k^*\|$（因为 $\{b_i^*\}$ 正交，最短向量的下界由最后一个 Gram-Schmidt 向量给出），结合 $\|b_1^*\| \leq 2^{-(k-1)} \|b_k^*\|$，可得结论。

推论：LLL 算法给出的近似因子为 $2^{(n-1)/2}$，这是一个指数级的近似比。虽然理论保证较弱，但在实践中 LLL 往往能给出远优于该界限的结果。

时间复杂度

定理 3（LLL 复杂度）：LLL 算法的时间复杂度为 $O(m^6 \log^3 B)$，其中 $m$ 是基向量个数，$B$ 是基向量长度的上界。

分析：

• 每次 size-reduction 操作的时间为 $O(m^3)$（需要更新 $O(m^2)$ 个 $\mu$ 系数）
• 交换操作的总次数为 $O(m^2 \log B)$（由势函数的下降保证）
• 总时间复杂度为 $O(m^6 \log^3 B)$

Python 实现

以下是 LLL 算法的核心实现（纯 Python，不依赖第三方库）：

from math import sqrt, floor, ceil

def gram_schmidt(B):
    """Gram-Schmidt 正交化"""
    m = len(B)
    n = len(B[0])
    B_star = [[0.0] * n for _ in range(m)]
    mu = [[0.0] * m for _ in range(m)]
    
    for i in range(m):
        B_star[i] = list(B[i])
        for j in range(i):
            dot_ij = sum(B[i][k] * B_star[j][k] for k in range(n))
            dot_jj = sum(B_star[j][k] ** 2 for k in range(n))
            mu[i][j] = dot_ij / dot_jj
            for k in range(n):
                B_star[i][k] -= mu[i][j] * B_star[j][k]
    
    return B_star, mu

def lll_reduce(B, delta=0.75):
    """LLL 约减算法"""
    m = len(B)
    n = len(B[0])
    B = [list(row) for row in B]  # 深拷贝
    
    for k in range(1, m):
        # 计算 Gram-Schmidt 正交化
        B_star, mu = gram_schmidt(B)
        
        # Size-reduction
        for j in range(k - 1, -1, -1):
            r = round(mu[k][j])
            if r != 0:
                for x in range(n):
                    B[k][x] -= r * B[j][x]
        
        # 重新计算 Gram-Schmidt
        B_star, mu = gram_schmidt(B)
        
        # Lovász condition
        theta = mu[k][k - 1]
        norm_k_minus_1_sq = sum(B_star[k - 1][x] ** 2 for x in range(n))
        norm_k_sq = sum(B_star[k][x] ** 2 for x in range(n))
        
        if delta * norm_k_minus_1_sq > norm_k_sq + theta ** 2:
            # Swap
            B[k - 1], B[k] = B[k], B[k - 1]
            k = max(k - 1, 1)
    
    return B

# 测试示例
B = [[2, 1], [1, 3]]
result = lll_reduce(B)
print("约减结果:", result)  # 输出约减后的基

BKZ 算法：原理与实现

算法思想

LLL 算法虽然高效，但其近似因子 $2^{(n-1)/2}$ 对于密码分析来说仍然过松。为了获得更短的向量，需要更强的约减算法——BKZ 算法应运而生。

BKZ（Block Korkine-Zolotarev）算法的核心思想是：在子格上进行精确的 SVP 求解，而非像 LLL 那样进行多项式时间的近似。通过调整子格的大小（块大小 $\beta$），可以在计算时间和输出质量之间进行权衡。

关键洞察：当块大小 $\beta = 2$ 时，BKZ 退化为 LLL 算法；当 $\beta = n$ 时，BKZ 等价于在整格上求解 SVP。

算法流程

输入：格的基 $B = (b_1, \ldots, b_m)$，块大小 $\beta$，参数 $\delta$

输出：BKZ 约减基 $B'$

Algorithm BKZ(B, β, δ):
    1. clamp := 0
    2. while clamp ≠ m - 1 do:
        clamp := 0
        for k := 1 to m - 1 do:
            // 提取子格
            B_sub := 提取 B[k:min(k+β,m)] 的子格基
            // 在子格上求解 SVP（使用枚举或约减）
            b_short := 子格中的最短向量
            // 如果找到更短的向量，进行交换
            if ‖b_short‖ < ‖b_k*‖ / sqrt(δ) then:
                用 b_short 替换 b_k
                clamp := k
        // 重复直到无变化
    3. return B

更精确的 BKZ 描述（采用 Gama-Nguyen 框架）：

Algorithm BKZ(B, β):
    1. 初始化：令 B = (b_1, ..., b_m)
    2. repeat
        changed := false
        for k := 1 to m - β do:
            // 步骤 1：在当前块 [k, k+β-1] 上进行 LLL 约减
            B[k:k+β] := LLL_reduce(B[k:k+β], δ=0.75)
            
            // 步骤 2：在投影格上求解 SVP
            // 投影到 span(b_k*, ..., b_{k+β-1}*) 的正交补
            t := 投影(b_{k+β}, span(b_k*, ..., b_{k+β-1}*))
            
            // 步骤 3：如果投影更短，交换
            if ‖t‖ < ‖b_{k+β}*‖ / sqrt(δ) then:
                交换 b_{k+β-1} 和 b_{k+β}
                changed := true
        until not changed
    3. return B

近似因子分析

定理 4（BKZ 近似因子）：设 BKZ 算法使用块大小 $\beta$ 和参数 $\delta$，则输出的第一个向量 $b_1$ 满足： $$\|b_1\| \leq \left(\frac{4\delta}{4\delta - 1}\right)^{(\beta-1)/2} \cdot \beta^{1/(2(\beta-1))} \cdot \lambda_1(L)^{(\beta-1)/\beta} \cdot (\det L)^{1/\beta}$$

简化版本（取 $\delta = 3/4$）： $$\|b_1\| \leq 2^{\beta/2} \cdot \lambda_1(L)$$

对比：

• LLL ($\beta = 2$)：近似因子 $2^{(n-1)/2}$，与格维度 $n$ 呈指数关系
• BKZ ($\beta = 10$)：近似因子约 $2^5 = 32$，显著改善
• BKZ ($\beta = 40$)：近似因子约 $2^{20} \approx 10^6$，但仍远优于 LLL

时间复杂度

定理 5（BKZ 复杂度）：BKZ 算法的时间复杂度为： $$O\left(2^{0.292\beta \cdot poly(m)}\right)$$

其中 $\beta$ 是块大小，$m$ 是格的秩。关键点：

• 指数依赖 $\beta$：复杂度随块大小指数增长
• 多项式依赖 $m$：复杂度随格维度多项式增长
• 实际攻击：$\beta \leq 50$ 时可在可行时间内完成；$\beta > 100$ 时计算不可行

BKZ 与 SVP 求解器

BKZ 的核心子程序是 SVP 求解器。常用的 SVP 求解方法包括：

密码分析应用

RSA 低指数攻击

定理（Coppersmith 攻击）：当 RSA 模数 $N$ 的比特长度接近 $e \cdot d$ 时，可以使用格基约减恢复私钥 $d$。

具体地，若 $N = p \cdot q$ 且 $d < N^{0.292}$，则可以使用 LLL 算法在多项式时间内恢复 $d$。这是通过将 RSA 方程 $ed \equiv 1 \pmod{\phi(N)}$ 转化为格上的短向量问题实现的。

攻击流程：

• 构造格：基于多项式 $f(x) = e \cdot x + 1$ 的根构造理想格
• 应用 LLL 约减：找到格中的短向量
• 恢复私钥：从短向量中提取 $d$

NTRU 格攻击

NTRU 密码系统的核心是基于环理想格（Ideal Lattice）的困难性问题。攻击 NTRU 的关键是将解密过程转化为格的最近向量问题。

Hermite 常数与 NTRU 安全：NTRU 的安全性依赖于 Hermite 常数 $\gamma_n$ 的增长。已知 $\gamma_n \approx \frac{n}{2\pi e} \cdot (1 + o(1))$，而 LLL 给出的 Hermite 因子约为 $\sqrt{4\delta/(4\delta-1)}^{(n-1)/(2(n-1)))}$。

实际攻击参数：

• 对于 NTRU Prime，块大小 $\beta \approx 50$ 的 BKZ 可以攻击 128 位安全级别的参数
• 对于标准 NTRU，需要更大的参数空间才能抵抗 BKZ 攻击

后量子密码安全参数评估

NIST PQC 标准化过程中，安全参数的选择直接依赖于对 BKZ 算法最新进展的理解。

当前最佳估计（基于 2024 年的研究成果）：

• Kyber-512（NIST Level 1）：需要 BKZ $\beta \approx 400$ 才能破解，对应约 $2^{100}$ 次操作
• Kyber-768（NIST Level 3）：需要 BKZ $\beta \approx 600$，对应约 $2^{160}$ 次操作
• Kyber-1024（NIST Level 5）：需要 BKZ $\beta \approx 800$，对应约 $2^{256}$ 次操作

格密码的参数选择原则

基于格基约减算法的分析，格密码系统的参数选择应遵循以下原则：

• 安全参数与 BKZ 块大小的关系：安全强度 $2^\lambda$ 对应需要的 BKZ 块大小 $\beta \approx \frac{2\lambda}{\log_2(\text{Hermite 常数})}$
• 维度选择：格维度 $n$ 应足够大，使得 BKZ $\beta = n$ 的计算不可行
• 模数选择：模数 $q$ 应足够大，以确保误差分布的统计安全性

与国密标准的关联

SM9 与格密码的比较

虽然 SM9 基于配对密码学而非格密码学，但两者在安全性分析上有相似之处：

国密算法与格密码的结合

未来国密体系可能会与格密码结合，形成混合密码系统。例如：

• SM2 + Kyber 混合密钥交换：结合 SM2 的成熟生态与 Kyber 的量子抗性
• SM3 + 格哈希函数：使用 SM3 作为格密码中的哈希原语
• SM4 + 格封装机制：使用 SM4 加密封装后的格密码共享密钥

总结

格基约减算法是连接纯数学与密码实践的桥梁：

• LLL 算法提供了多项式时间的格基约减，近似因子为 $2^{(n-1)/2}$，适合快速近似和理论分析
• BKZ 算法通过调整块大小 $\beta$，在计算时间和输出质量之间提供灵活的权衡
• 密码分析应用广泛，包括 RSA 低指数攻击、NTRU 格攻击、LWE 问题求解等
• 后量子密码标准化直接依赖于对 BKZ 算法最新进展的理解

参考来源

• Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). *Factoring polynomials with rational coefficients*. Mathematische Annalen, 261(4), 515-534. https://doi.org/10.1007/BF01457454
• Schnorr, C. P., & Euchner, M. (1994). *Lattice reduction by continued fractions*. Algorithmica, 12(2-3), 195-218.
• Gama, N., & Nguyen, P. Q. (2008). *Finding lattice short vectors with sieving*. Lecture Notes in Computer Science, 5165, 157-173.
• Albrecht, M. R., et al. (2015). *LWE hardness estimation for lattice-based cryptosystems*. IACR ePrint Archive, 2015/1010.
• NIST FIPS 203 (2024). *Module-Lattice-Based Key-Encapsulation Mechanism Standard*. https://csrc.nist.gov/pubs/fips/203/final
• GM/T 0044-2016. *SM9 标识密码算法*. 国家密码管理局.

相关实践

• FIPS 203 (ML-KEM/Kyber) 后量子密钥封装标准深度解读 — NIST 后量子密码标准化的核心成果
• NTRU 格密码系统：从 1996 年到 NIST PQC 竞赛 — 最早的格密码方案及其演进
• SM9 标识密码算法原理详解 — 配对密码学与格密码学的对比视角