# 16 投影格、BKZ 与局部 SVP

整理日期：2026-10-16。
适用范围：格基约化中的投影格、局部短向量计算，以及它们与筛法维数和向量提升的关系。
前置笔记：[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)、[05 格基约化与 LLL 算法](/knowledge/lattice-reduction-and-lll/)、[06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)、[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)。

设 $B=(b_1,\ldots,b_n)\in\mathbb Z^{n\times n}$ 满秩，$\Lambda=\mathcal L(B)$。沿用列基与欧氏范数，记 $b_k^*$ 为 GSO 向量，$g_k=\|b_k^*\|$。

本篇使用从 $1$ 开始的下标，区间 $[i,j]$ 包含两个端点。

## 1. 投影格与局部块

定义 $\pi_i$ 为到前缀空间 $\operatorname{span}(b_1,\ldots,b_{i-1})$ 的正交补上的投影：

$$
\pi_i(x)
=
x-\sum_{k<i}
\frac{\langle x,b_k^*\rangle}{g_k^2}b_k^*.
$$

特别地，$\pi_1$ 是恒等映射，且

$$
\pi_i(b_k)=0\quad(k<i),
\qquad
\pi_i(b_i)=b_i^*.
$$

对 $1\le i\le j\le n$，定义局部投影基及其生成的格：

$$
B_{[i,j]}
=
\bigl(\pi_i(b_i),\ldots,\pi_i(b_j)\bigr),
\qquad
\Lambda_{[i,j]}=\mathcal L(B_{[i,j]}).
$$

投影后的这些向量仍线性无关，所以 $\Lambda_{[i,j]}$ 是维数为

$$
d=j-i+1
$$

的格。特别地，$\pi_i(\Lambda)=\Lambda_{[i,n]}$。

这里的投影与格基前缀相配合，保证了投影后的离散性；任意子空间上的正交投影并不一定把格映成格。局部格位于投影空间中，其向量通常不属于原格。

这一记法对应 [G6K，EUROCRYPT 2019，§2.1，PDF 第 6 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)的 local projected basis；原文使用从 $0$ 开始的下标和右端点不包含在内的区间，阅读时需换算。

## 2. 局部长度、体积与高斯启发式

局部基 $B_{[i,j]}$ 的 GSO 向量正是

$$
b_i^*,b_{i+1}^*,\ldots,b_j^*.
$$

原因是：先消去前缀方向，再对剩余列正交化，与完整 GSO 的对应步骤一致。

因此，局部格在自身张成空间中的体积为

$$
\boxed{
\det(\Lambda_{[i,j]})
=
\prod_{k=i}^{j}g_k.
}
$$

它一般不同于未经投影的子格 $\mathcal L(b_i,\ldots,b_j)$ 的体积。全格行列式由全部 GSO 长度的乘积给出；局部计算只使用相应区间。

对整数系数 $z_i,\ldots,z_j$，有

$$
y=\sum_{\ell=i}^{j}z_\ell\pi_i(b_\ell),
$$

以及

$$
\boxed{
\|y\|^2
=
\sum_{k=i}^{j}
\left(
z_k+\sum_{\ell=k+1}^{j}\mu_{\ell,k}z_\ell
\right)^2g_k^2.
}
$$

这个式子由正交分解直接得到，说明局部 SVP 的长度计算需要 GSO 长度和投影系数 $\mu$；只知道体积，不能确定哪些整数系数组合最短。

沿用第 15 篇的参考长度定义，令 $V_d$ 为 $d$ 维单位球体积，则

$$
\boxed{
\operatorname{gh}(\Lambda_{[i,j]})
=
\left(\frac{\prod_{k=i}^{j}g_k}{V_d}\right)^{1/d}
\approx
\sqrt{\frac{d}{2\pi e}}
\left(\prod_{k=i}^{j}g_k\right)^{1/d}.
}
$$

最后一个近似用于较大的 $d$。它估计的是这个局部格的长度尺度，所用维数和体积都应来自当前局部块。

## 3. 局部 SVP 与 BKZ 约化条件

局部 SVP 的输入是 $B_{[i,j]}$，目标是寻找

$$
0\ne y\in\Lambda_{[i,j]},
\qquad
\|y\|=\lambda_1(\Lambda_{[i,j]}).
$$

求解器还应返回相对于局部基的整数系数 $z_i,\ldots,z_j$，以便恢复对应的原格向量。

BKZ，全称 Block Korkine–Zolotarev，使用块大小参数

$$
2\le\beta\le n.
$$

在位置 $i$，取

$$
j=\min(i+\beta-1,n),
\qquad
d=j-i+1\le\beta.
$$

由于 $b_i^*=\pi_i(b_i)$ 本身就是局部格中的非零向量，总有

$$
\lambda_1(\Lambda_{[i,j]})\le g_i.
$$

**理想的精确 BKZ 条件**要求基满足尺寸约化，并且每个位置都有

$$
\boxed{
g_i=\lambda_1(\Lambda_{[i,j]}).
}
$$

也就是：在该位置允许考虑的投影块内，第一条投影基向量已经最短。定义见 [G6K，§2.2，Definition 1，PDF 第 7 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

算法中通常使用带松弛的条件，例如固定 $1/4<\delta<1$，要求

$$
\delta g_i^2
\le
\lambda_1(\Lambda_{[i,j]})^2.
$$

它允许第一条投影基向量比局部最短向量稍长，并给出明确的改善阈值。

对同一组基，增大 $\beta$ 会扩大局部搜索空间，使约化条件更强，通常也提高局部求解成本。当 $\beta=n$ 时，精确条件成为 HKZ 条件，且 $b_1$ 是全格最短向量；一般的较小块条件只约束相应的局部问题。

## 4. 从投影向量到原格向量：Babai 提升

设局部求解器得到

$$
y=\sum_{k=i}^{j}z_k\pi_i(b_k).
$$

使用相同整数系数构造

$$
x_0=\sum_{k=i}^{j}z_kb_k\in\Lambda,
\qquad
\pi_i(x_0)=y.
$$

这给出一个提升，但 $x_0$ 在前缀方向上的分量可能较长。所有投影到同一个 $y$ 的原格向量构成陪集

$$
\boxed{
x_0+\mathcal L(b_1,\ldots,b_{i-1}).
}
$$

因此，可以通过加减前缀格向量，寻找更短的提升。这正好衔接第 06 篇的 Babai 取整：

~~~text
x ← x₀
对 k = i−1, i−2, …, 1：
    q ← round(〈x, bₖ*〉 / gₖ²)
    x ← x − q·bₖ
返回 x
~~~

每一步保持 $x\in\Lambda$ 和 $\pi_i(x)=y$。结束后，

$$
x=y+\sum_{k<i}\varepsilon_kb_k^*,
\qquad
|\varepsilon_k|\le\frac12.
$$

由正交性，

$$
\boxed{
\|x\|^2
=
\|y\|^2+\sum_{k<i}\varepsilon_k^2g_k^2
\le
\|y\|^2+\frac14\sum_{k<i}g_k^2.
}
$$

这是将 Babai 残差界用于提升得到的直接推论。逐维提升的同类公式见 [G6K，§3.2，Extend Left，PDF 第 9 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

提升恢复了被投影掉的方向，也增加了相应长度。Babai 给出一个易计算的提升，但不保证它是该陪集中最短的向量。

## 5. 插入局部解与 BKZ 的基本流程

找到原格中的短向量后，还需要将它纳入一组仍生成原格的基。

设局部解的系数向量为 $z=(z_i,\ldots,z_j)^T$。若 $y$ 是精确最短非零向量，则

$$
\gcd(z_i,\ldots,z_j)=1.
$$

否则可以除去公共因子，得到更短的非零局部格向量。满足这一条件的整数向量称为原始向量，可以补成某个幺模矩阵 $U$ 的第一列。

于是，对未投影的原基块执行

$$
(b_i,\ldots,b_j)
\leftarrow
(b_i,\ldots,b_j)U,
\qquad
U\in\mathrm{GL}_d(\mathbb Z),
$$

就能使 $x_0$ 成为块的第一列，同时保持原格不变。再减去前缀基向量的整数倍，可以得到上一节的 Babai 提升。

在前缀保持不变的这一步，新基满足

$$
b_{i,\mathrm{new}}^*=y.
$$

所以，BKZ 在位置 $i$ 比较的是投影长度 $\|y\|$ 与原来的 $g_i$。提升后的完整向量长度与这个局部比较量需要分别记录。若使用非精确求解器，插入前同样需要处理整数系数的公共因子及换基条件。

下面给出一次扫描，也称一轮 **tour**，的简化结构：

~~~text
BKZTour(B, β, δ):
    B ← LLLδ(B)

    对 i = 1, …, n−1：
        更新当前基的 GSO
        j ← min(i+β−1, n)

        (y, z) ← LocalSVP(B_[i,j])

        如果 ||y||² < δ·gᵢ²：
            用 z 构造原格中的提升
            通过保持原格的换基，将它插入位置 i
            B ← LLLδ(B)

    返回 B
~~~

这里暂将 **LocalSVP** 视为精确求解器；枚举和筛法是实现局部求解的不同途径。以低维 SVP 改善格基的思路，也见 [Micciancio《Blockwise Basis Reduction》，Fall 2025，第 4 页](https://cseweb.ucsd.edu/classes/fa25/cse206A-a/slides-bkz.pdf)。

一次插入及后续 LLL 可能改变其他窗口，因此通常需要多轮扫描。实际实现还会指定局部预处理、搜索成功率、目标半径及停止规则；启发式求解器某次没有找到改善向量，并不证明该局部格已满足精确条件。

## 6. 全格维数、块大小与实际筛法维数

现在可以区分三个量：

- **全格维数 $n$**：原始格的秩。
- **BKZ 块大小 $\beta$**：局部窗口的名义上限；当前位置的实际块维数为 $d=\min(\beta,n-i+1)$。
- **实际筛法维数 $s$**：本次向量池所在投影格的维数。

直接在整个局部块中筛法时，$s=d$。如果选取整数 $0\le f<d$，先投影掉块内前 $f$ 个方向，只在

$$
\Lambda_{[i+f,j]}
$$

中筛出候选，则

$$
\boxed{s=d-f.}
$$

随后，可以把候选 $y\in\Lambda_{[i+f,j]}$ 向左提升为 $\widetilde y\in\Lambda_{[i,j]}$。对局部基应用同样的 Babai 过程，得到

$$
\boxed{
\|\widetilde y\|^2
\le
\|y\|^2+\frac14\sum_{k=i}^{i+f-1}g_k^2.
}
$$

这解释了 **dimensions for free** 的基本思路：把主要的筛法搜索放在较小维数中，再利用提升获得更大块里的短向量。其可行性依赖预处理后的 GSO 长度、候选覆盖范围和提升效果。相关算法与启发式分析见 [Ducas，EUROCRYPT 2018，《Shortest Vector from Lattice Sieving: A Few Dimensions for Free》，§3.1–§3.2，Algorithm 2 与 Heuristic Claims 1–2，PDF 第 5–7 页](https://ir.cwi.nl/pub/27649/27649.pdf)。

这里通常需要考察多个候选：投影最短的向量不一定具有最短的提升。“免费”表示减少昂贵搜索所需的维数，提升本身仍有计算成本和长度代价。

应用第 15 篇的概率与数量模型时，应使用当前筛法空间：

$$
\operatorname{gh}(\Lambda_{[i+f,j]})
=
\left(
\frac{\prod_{k=i+f}^{j}g_k}{V_s}
\right)^{1/s},
$$

球帽概率也相应使用 $p_s(t)$，同时保留方向分布和独立性的假设。

## 7. 与后续筛法研究的联系

BKZ 负责选择局部问题、调用短向量求解器并调整格基；筛法负责在当前投影格中维护和约化向量池。完整运行成本需要结合局部调用次数、每次的筛法维数、轮数，以及预处理、提升和换基开销。

渐进筛法改变维数时，还会改变向量池的几何状态：

- **向右扩展窗口**：旧向量可以直接嵌入更大的局部格，但在新增 GSO 方向上的分量为零。
- **向左扩展窗口**：Babai 提升补入一个受取整约束的分量，并增加相应长度。

因此，扩展后的旧向量不会自动成为新空间中的独立均匀样本；局部体积、参考长度和分布假设都需要随窗口更新。G6K 对这些操作及筛法、提升范围的区分，见 [§3.2–§3.3，PDF 第 9–11 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

下一篇进入《17 筛法的基本框架与两向量约化》，具体讨论向量池如何生成、约化、更新和停止，再衔接 Nguyen–Vidick、ListSieve 与 GaussSieve。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [17 筛法的基本框架与两向量约化](/knowledge/lattice-sieving-basics/)
- [18 Nguyen–Vidick、ListSieve 与 GaussSieve](/knowledge/nguyen-vidick-listsieve-and-gausssieve/)
- [25 渐进筛法与向量池复用](/knowledge/progressive-sieving-and-vector-pool-reuse/)
- [26 G6K 与 Pump](/knowledge/g6k-and-pump/)