16 投影格、BKZ 与局部 SVP 整理日期：2026-10-16。
适用范围：格基约化中的投影格、局部短向量计算，以及它们与筛法维数和向量提升的关系。
前置笔记：02 基本区域、格行列式与正交化 、05 格基约化与 LLL 算法 、06 Babai 最近平面算法与近似 CVP 、15 高斯启发式与随机球面模型 。
设 B = ( b 1 , … , b n ) ∈ Z n × n B=(b_1,\ldots,b_n)\in\mathbb Z^{n\times n} B = ( b 1 , … , b n ) ∈ Z n × n Λ = L ( B ) \Lambda=\mathcal L(B) Λ = L ( B ) b k ∗ b_k^* b k ∗ g k = ∥ b k ∗ ∥ g_k=\|b_k^*\| g k = ∥ b k ∗ ∥
本篇使用从 1 1 1 [ i , j ] [i,j] [ i , j ]
1. 投影格与局部块
定义 π i \pi_i π i span ( b 1 , … , b i − 1 ) \operatorname{span}(b_1,\ldots,b_{i-1}) span ( b 1 , … , b i − 1 )
π i ( x ) = x − ∑ k < i ⟨ x , b k ∗ ⟩ g k 2 b k ∗ . \pi_i(x)
=
x-\sum_{k<i}
\frac{\langle x,b_k^*\rangle}{g_k^2}b_k^*. π i ( x ) = x − k < i ∑ g k 2 ⟨ x , b k ∗ ⟩ b k ∗ . 特别地，π 1 \pi_1 π 1
π i ( b k ) = 0 ( k < i ) , π i ( b i ) = b i ∗ . \pi_i(b_k)=0\quad(k<i),
\qquad
\pi_i(b_i)=b_i^*. π i ( b k ) = 0 ( k < i ) , π i ( b i ) = b i ∗ . 对 1 ≤ i ≤ j ≤ n 1\le i\le j\le n 1 ≤ i ≤ j ≤ n
B [ i , j ] = ( π i ( b i ) , … , π i ( b j ) ) , Λ [ i , j ] = L ( B [ i , j ] ) . B_{[i,j]}
=
\bigl(\pi_i(b_i),\ldots,\pi_i(b_j)\bigr),
\qquad
\Lambda_{[i,j]}=\mathcal L(B_{[i,j]}). B [ i , j ] = ( π i ( b i ) , … , π i ( b j ) ) , Λ [ i , j ] = L ( B [ i , j ] ) . 投影后的这些向量仍线性无关，所以 Λ [ i , j ] \Lambda_{[i,j]} Λ [ i , j ]
d = j − i + 1 d=j-i+1 d = j − i + 1 的格。特别地，π i ( Λ ) = Λ [ i , n ] \pi_i(\Lambda)=\Lambda_{[i,n]} π i ( Λ ) = Λ [ i , n ]
这里的投影与格基前缀相配合，保证了投影后的离散性；任意子空间上的正交投影并不一定把格映成格。局部格位于投影空间中，其向量通常不属于原格。
这一记法对应 G6K，EUROCRYPT 2019，§2.1，PDF 第 6 页 的 local projected basis；原文使用从 0 0 0
2. 局部长度、体积与高斯启发式
局部基 B [ i , j ] B_{[i,j]} B [ i , j ]
b i ∗ , b i + 1 ∗ , … , b j ∗ . b_i^*,b_{i+1}^*,\ldots,b_j^*. b i ∗ , b i + 1 ∗ , … , b j ∗ . 原因是：先消去前缀方向，再对剩余列正交化，与完整 GSO 的对应步骤一致。
因此，局部格在自身张成空间中的体积为
det ( Λ [ i , j ] ) = ∏ k = i j g k . \boxed{
\det(\Lambda_{[i,j]})
=
\prod_{k=i}^{j}g_k.
} det ( Λ [ i , j ] ) = k = i ∏ j g k . 它一般不同于未经投影的子格 L ( b i , … , b j ) \mathcal L(b_i,\ldots,b_j) L ( b i , … , b j )
对整数系数 z i , … , z j z_i,\ldots,z_j z i , … , z j
y = ∑ ℓ = i j z ℓ π i ( b ℓ ) , y=\sum_{\ell=i}^{j}z_\ell\pi_i(b_\ell), y = ℓ = i ∑ j z ℓ π i ( b ℓ ) , 以及
∥ y ∥ 2 = ∑ k = i j ( z k + ∑ ℓ = k + 1 j μ ℓ , k z ℓ ) 2 g k 2 . \boxed{
\|y\|^2
=
\sum_{k=i}^{j}
\left(
z_k+\sum_{\ell=k+1}^{j}\mu_{\ell,k}z_\ell
\right)^2g_k^2.
} ∥ y ∥ 2 = k = i ∑ j ( z k + ℓ = k + 1 ∑ j μ ℓ , k z ℓ ) 2 g k 2 . 这个式子由正交分解直接得到，说明局部 SVP 的长度计算需要 GSO 长度和投影系数 μ \mu μ
沿用第 15 篇的参考长度定义，令 V d V_d V d d d d
gh ( Λ [ i , j ] ) = ( ∏ k = i j g k V d ) 1 / d ≈ d 2 π e ( ∏ k = i j g k ) 1 / 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}.
} gh ( Λ [ i , j ] ) = ( V d ∏ k = i j g k ) 1/ d ≈ 2 π e d ( k = i ∏ j g k ) 1/ d . 最后一个近似用于较大的 d d d
3. 局部 SVP 与 BKZ 约化条件
局部 SVP 的输入是 B [ i , j ] B_{[i,j]} B [ i , j ]
0 ≠ y ∈ Λ [ i , j ] , ∥ y ∥ = λ 1 ( Λ [ i , j ] ) . 0\ne y\in\Lambda_{[i,j]},
\qquad
\|y\|=\lambda_1(\Lambda_{[i,j]}). 0 = y ∈ Λ [ i , j ] , ∥ y ∥ = λ 1 ( Λ [ i , j ] ) . 求解器还应返回相对于局部基的整数系数 z i , … , z j z_i,\ldots,z_j z i , … , z j
BKZ，全称 Block Korkine–Zolotarev，使用块大小参数
2 ≤ β ≤ n . 2\le\beta\le n. 2 ≤ β ≤ n . 在位置 i i i
j = min ( i + β − 1 , n ) , d = j − i + 1 ≤ β . j=\min(i+\beta-1,n),
\qquad
d=j-i+1\le\beta. j = min ( i + β − 1 , n ) , d = j − i + 1 ≤ β . 由于 b i ∗ = π i ( b i ) b_i^*=\pi_i(b_i) b i ∗ = π i ( b i )
λ 1 ( Λ [ i , j ] ) ≤ g i . \lambda_1(\Lambda_{[i,j]})\le g_i. λ 1 ( Λ [ i , j ] ) ≤ g i . 理想的精确 BKZ 条件 要求基满足尺寸约化，并且每个位置都有
g i = λ 1 ( Λ [ i , j ] ) . \boxed{
g_i=\lambda_1(\Lambda_{[i,j]}).
} g i = λ 1 ( Λ [ i , j ] ) . 也就是：在该位置允许考虑的投影块内，第一条投影基向量已经最短。定义见 G6K，§2.2，Definition 1，PDF 第 7 页 。
算法中通常使用带松弛的条件，例如固定 1 / 4 < δ < 1 1/4<\delta<1 1/4 < δ < 1
δ g i 2 ≤ λ 1 ( Λ [ i , j ] ) 2 . \delta g_i^2
\le
\lambda_1(\Lambda_{[i,j]})^2. δ g i 2 ≤ λ 1 ( Λ [ i , j ] ) 2 . 它允许第一条投影基向量比局部最短向量稍长，并给出明确的改善阈值。
对同一组基，增大 β \beta β β = n \beta=n β = n b 1 b_1 b 1
4. 从投影向量到原格向量：Babai 提升
设局部求解器得到
y = ∑ k = i j z k π i ( b k ) . y=\sum_{k=i}^{j}z_k\pi_i(b_k). y = k = i ∑ j z k π i ( b k ) . 使用相同整数系数构造
x 0 = ∑ k = i j z k b k ∈ Λ , π i ( x 0 ) = y . x_0=\sum_{k=i}^{j}z_kb_k\in\Lambda,
\qquad
\pi_i(x_0)=y. x 0 = k = i ∑ j z k b k ∈ Λ , π i ( x 0 ) = y . 这给出一个提升，但 x 0 x_0 x 0 y y y
x 0 + L ( b 1 , … , b i − 1 ) . \boxed{
x_0+\mathcal L(b_1,\ldots,b_{i-1}).
} x 0 + L ( b 1 , … , b i − 1 ) . 因此，可以通过加减前缀格向量，寻找更短的提升。这正好衔接第 06 篇的 Babai 取整：
x ← x₀ 对 k = i−1, i−2, …, 1： q ← round(〈x, bₖ*〉 / gₖ²) x ← x − q·bₖ 返回 x 每一步保持 x ∈ Λ x\in\Lambda x ∈ Λ π i ( x ) = y \pi_i(x)=y π i ( x ) = y
x = y + ∑ k < i ε k b k ∗ , ∣ ε k ∣ ≤ 1 2 . x=y+\sum_{k<i}\varepsilon_kb_k^*,
\qquad
|\varepsilon_k|\le\frac12. x = y + k < i ∑ ε k b k ∗ , ∣ ε k ∣ ≤ 2 1 . 由正交性，
∥ x ∥ 2 = ∥ y ∥ 2 + ∑ k < i ε k 2 g k 2 ≤ ∥ y ∥ 2 + 1 4 ∑ k < i g k 2 . \boxed{
\|x\|^2
=
\|y\|^2+\sum_{k<i}\varepsilon_k^2g_k^2
\le
\|y\|^2+\frac14\sum_{k<i}g_k^2.
} ∥ x ∥ 2 = ∥ y ∥ 2 + k < i ∑ ε k 2 g k 2 ≤ ∥ y ∥ 2 + 4 1 k < i ∑ g k 2 . 这是将 Babai 残差界用于提升得到的直接推论。逐维提升的同类公式见 G6K，§3.2，Extend Left，PDF 第 9 页 。
提升恢复了被投影掉的方向，也增加了相应长度。Babai 给出一个易计算的提升，但不保证它是该陪集中最短的向量。
5. 插入局部解与 BKZ 的基本流程
找到原格中的短向量后，还需要将它纳入一组仍生成原格的基。
设局部解的系数向量为 z = ( z i , … , z j ) T z=(z_i,\ldots,z_j)^T z = ( z i , … , z j ) T y y y
gcd ( z i , … , z j ) = 1. \gcd(z_i,\ldots,z_j)=1. g cd( z i , … , z j ) = 1. 否则可以除去公共因子，得到更短的非零局部格向量。满足这一条件的整数向量称为原始向量，可以补成某个幺模矩阵 U U U
于是，对未投影的原基块执行
( b i , … , b j ) ← ( b i , … , b j ) U , U ∈ G L d ( Z ) , (b_i,\ldots,b_j)
\leftarrow
(b_i,\ldots,b_j)U,
\qquad
U\in\mathrm{GL}_d(\mathbb Z), ( b i , … , b j ) ← ( b i , … , b j ) U , U ∈ GL d ( Z ) , 就能使 x 0 x_0 x 0
在前缀保持不变的这一步，新基满足
b i , n e w ∗ = y . b_{i,\mathrm{new}}^*=y. b i , new ∗ = y . 所以，BKZ 在位置 i i i ∥ y ∥ \|y\| ∥ y ∥ g i g_i g i
下面给出一次扫描，也称一轮 tour ，的简化结构：
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 页 。
一次插入及后续 LLL 可能改变其他窗口，因此通常需要多轮扫描。实际实现还会指定局部预处理、搜索成功率、目标半径及停止规则；启发式求解器某次没有找到改善向量，并不证明该局部格已满足精确条件。
6. 全格维数、块大小与实际筛法维数
现在可以区分三个量：
全格维数 n n n ：原始格的秩。BKZ 块大小 β \beta β ：局部窗口的名义上限；当前位置的实际块维数为 d = min ( β , n − i + 1 ) d=\min(\beta,n-i+1) d = min ( β , n − i + 1 ) 实际筛法维数 s s s ：本次向量池所在投影格的维数。
直接在整个局部块中筛法时，s = d s=d s = d 0 ≤ f < d 0\le f<d 0 ≤ f < d f f f
Λ [ i + f , j ] \Lambda_{[i+f,j]} Λ [ i + f , j ] 中筛出候选，则
s = d − f . \boxed{s=d-f.} s = d − f . 随后，可以把候选 y ∈ Λ [ i + f , j ] y\in\Lambda_{[i+f,j]} y ∈ Λ [ i + f , j ] y ~ ∈ Λ [ i , j ] \widetilde y\in\Lambda_{[i,j]} y ∈ Λ [ i , j ]
∥ y ~ ∥ 2 ≤ ∥ y ∥ 2 + 1 4 ∑ k = i i + f − 1 g k 2 . \boxed{
\|\widetilde y\|^2
\le
\|y\|^2+\frac14\sum_{k=i}^{i+f-1}g_k^2.
} ∥ y ∥ 2 ≤ ∥ y ∥ 2 + 4 1 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 页 。
这里通常需要考察多个候选：投影最短的向量不一定具有最短的提升。“免费”表示减少昂贵搜索所需的维数，提升本身仍有计算成本和长度代价。
应用第 15 篇的概率与数量模型时，应使用当前筛法空间：
gh ( Λ [ i + f , j ] ) = ( ∏ k = i + f j g k V s ) 1 / s , \operatorname{gh}(\Lambda_{[i+f,j]})
=
\left(
\frac{\prod_{k=i+f}^{j}g_k}{V_s}
\right)^{1/s}, gh ( Λ [ i + f , j ] ) = ( V s ∏ k = i + f j g k ) 1/ s , 球帽概率也相应使用 p s ( t ) p_s(t) p s ( t )
7. 与后续筛法研究的联系
BKZ 负责选择局部问题、调用短向量求解器并调整格基；筛法负责在当前投影格中维护和约化向量池。完整运行成本需要结合局部调用次数、每次的筛法维数、轮数，以及预处理、提升和换基开销。
渐进筛法改变维数时，还会改变向量池的几何状态：
向右扩展窗口 ：旧向量可以直接嵌入更大的局部格，但在新增 GSO 方向上的分量为零。向左扩展窗口 ：Babai 提升补入一个受取整约束的分量，并增加相应长度。
因此，扩展后的旧向量不会自动成为新空间中的独立均匀样本；局部体积、参考长度和分布假设都需要随窗口更新。G6K 对这些操作及筛法、提升范围的区分，见 §3.2–§3.3，PDF 第 9–11 页 。
下一篇进入《17 筛法的基本框架与两向量约化》，具体讨论向量池如何生成、约化、更新和停止，再衔接 Nguyen–Vidick、ListSieve 与 GaussSieve。
引用此笔记
