18 Nguyen–Vidick、ListSieve 与 GaussSieve#

整理日期：2026-10-16。
适用范围：三种经典欧氏格筛法的采样、约化、更新与停止机制，以及各自的理论保证。
前置笔记：15 高斯启发式与随机球面模型、17 筛法的基本框架与两向量约化。局部投影环境见第 16 篇。

设当前格为 $\Lambda=\mathcal L(B)$，实际筛法维数为 $s\ge2$。沿用列基和欧氏范数；复杂度表述略去输入位长等多项式因子。

本文的 NV 指 Nguyen–Vidick 2008 的启发式批量筛法，ListSieve 指 Micciancio–Voulgaris 的原始带扰动算法，GaussSieve 指其直接处理格向量的实用变体。

下面的伪代码用于突出核心机制，显式处理零向量和结果记录。NV 与 ListSieve 保留原文的相减形式；GaussSieve 显式检查加减两种符号。

#1. Nguyen–Vidick：按轮缩短，消耗中心

NV 先生成 $N$ 条初始格向量，再反复调用一次筛选操作。原文以 LLL 预处理后的基为输入，采用 Klein 型随机化最近平面采样；初始采样的性质不能自动保证后续各轮仍满足所需分布假设。

给定非空列表 $S$，令

本轮构造中心列表 $H$ 和输出列表 $S'$：

NVStep(S, γ):
    R ← S 中的最大长度
    H ← 空列表
    S′ ← 空列表

    对每个 v ∈ S：
        如果 ||v|| ≤ γR：
            w ← v
        否则，如果存在 c ∈ H 满足 ||v−c|| ≤ γR：
            w ← v−c
        否则：
            将 v 加入 H
            继续处理下一个向量

        如果 w ≠ 0：
            将 w 加入 S′

    返回 S′

每轮中心只用于处理本轮后续向量，不进入下一轮。原始外层流程重复筛选直到列表为空，返回最后一个非空列表中的最短向量；实现时也可以持续记录遇到的最短非零向量。算法与采样入口见 Nguyen–Vidick，2008，作者稿 28 页版，§4.1，Algorithms 4–5，以及 §4.2.1，PDF 第 13–17 页。

由伪代码直接得到：只要下一轮非空，

但较小的半径不保证仍有足够多的向量。中心不进入输出、归零以及去重都会减少可用样本；若过早耗尽，返回值未必接近最短向量。这里允许列表保留重复项；若额外去重，需要将其损耗计入模型。

原文的启发式假设是：每轮参与筛选的长向量近似均匀分布于球壳

其球壳覆盖分析使用指数因子

在相应启发式及参数设置下，样本规模和时间的指数基准分别为 $c_\gamma^s$ 与 $c_\gamma^{2s}$，另含多项式因子。当 $\gamma\to1$ 时，

这解释了常见的两个指数；固定 $\gamma<1$ 时不能直接把它们当作精确值。更接近 $1$ 的 $\gamma$ 也意味着每轮缩短更少、所需轮数更多。来源见 原文 §4.1，Heuristic、Lemma 4.1 及复杂度讨论，PDF 第 14–16 页。

因此，应分别记录：半径收缩是算法保证，分布保持与预期输出质量依赖启发式；不能把 NV 论文中对 AKS 的证明直接用于这个简化版本。

#2. ListSieve：约化带扰动的点，保留已有列表

ListSieve 的输入除了格基，还包括目标长度 $\mu>0$。目标是找到

它维护只增不改的格向量列表 $D$。关键区别在于：约化判断作用于一个带扰动的点 $p$，而非直接作用于待输出的格向量。

取扰动参数 $\xi>1/2$，采样

其中 $\mathcal P(B)=\{Bt:t\in[0,1)^s\}$，取模表示选择同一格陪集在基本区域中的代表。于是

固定这次采样的 $e$，反复从 $p$ 中减去列表中的格向量。每次更新都保持 $p-e\in\Lambda$，最后恢复 $v=p-e$。中间点 $p$ 一般不属于格，列表中的向量始终属于格。

取长度缩短因子 $\delta=1-1/s$；这里的 $\delta$ 只表示本子程序的缩短比例。

ListSieve(B, μ, ξ, δ, K):
    D ← {0}                    # 0 用于统一检查候选自身的长度

    重复 K 次：
        e ← 在半径 ξμ 的球内均匀采样
        p ← e mod P(B)

        当存在 u ∈ D \ {0} 满足 ||p−u|| ≤ δ||p||：
            p ← p−u

        v ← p−e
        如果 v ∈ D：
            继续下一次采样

        如果存在 u ∈ D 满足 0 < ||v−u|| ≤ μ：
            返回 v−u

        将 v 加入 D            # 已有向量不修改、不移除

    返回 ⊥                     # 本次未找到目标向量

这里显式排除了零约化向量，并按非零、长度至多 $\mu$ 的目标写出返回检查；核心结构对应 Micciancio–Voulgaris，SODA 2010，作者稿 19 页版，§3.1，Algorithm 1，PDF 第 6–7 页。

扰动保留了分析碰撞概率所需的随机性：给定采样阶段的初始 $p$，$p-e$ 在 $\Lambda\cap B_s(p,\xi\mu)$ 上均匀分布。约化选择只依赖 $p$ 和当前列表，恢复格向量时才使用 $e$；这使证明能够比较“得到重复向量”和“得到新的短差向量”的概率。相关解释见 Micciancio《Sieving Algorithms for Exact SVP》，正文标注 Fall 2021，§2.2.1 与 §2.3.2。

其证明可以按两部分理解：

• 控制列表容量。 尚未返回目标解时，列表中不同向量的距离大于 $\mu$；再结合约化产生的几何约束，得到列表大小上界。
• 控制无效采样。 扰动与碰撞概率分析保证：采样次数足够多时，不能一直重复而不找到目标解。

当 $\lambda_1(\Lambda)\le\mu$，按定理选择采样预算 $K$，并取 $\xi\approx0.685$，原文给出高概率成功及以下复杂度界：

这是原始带扰动 ListSieve 的可证明界。来源见 原文 Theorem 3.1、Corollary 3.2 及 Appendix A。

返回向量可以直接验证；返回 $\perp$ 则可能是随机失败，不能视为不存在短向量的确定证书。配合外层长度搜索和失败概率控制，才能将该目标长度子程序用于精确 SVP。

此外，停止约化的是 $p$。恢复后的 $v=p-e$ 不自动满足第 17 篇的两两约化条件，已有列表也不会被 $v$ 反向约化。

#3. GaussSieve：双向约化与待处理队列

GaussSieve 直接采样格向量，使用两个容器：

• $D$：已经维护好两两约化关系的非零向量列表。
• $Q$：因更新而需要重新处理的向量队列或栈。

每次优先从 $Q$ 取向量；只有 $Q$ 为空时才生成新样本。处理候选 $v$ 分为两步：

1. 用 $D$ 中不长于 $v$ 的向量反复缩短 $v$。
2. 用处理后的 $v$ 缩短列表中更长的向量，将这些旧向量移出，约化结果放入 $Q$。

令 $\operatorname{Shorter}(a\pm b)$ 表示从 $a-b,a+b$ 中选择较短者。下面采用严格变短条件，并记录遇到的最短非零向量：

GaussSieve(B, c_max):
    D ← 空列表
    Q ← 空队列
    collisions ← 0
    best ← B 中最短的基向量

    当 collisions < c_max：
        v ← 从 Q 取出一个向量；若 Q 为空，则采样格向量

        当 v ≠ 0 且存在 u ∈ D 满足
            ||u|| ≤ ||v|| 且 min(||v−u||, ||v+u||) < ||v||：
            v ← Shorter(v±u)
            # v 改变后，重新扫描 D

        如果 v = 0：
            collisions ← collisions + 1
            继续下一轮

        用 v 更新 best

        对 D 中每个满足以下条件的 u：
            ||u|| > ||v|| 且 min(||u−v||, ||u+v||) < ||u||：
                从 D 移除 u
                w ← Shorter(u±v)
                将 w 放入 Q
                用 w 更新 best

        将 v 加入 D

    返回 best

这个整理版显式写出了符号选择、严格变短和结果记录。原始机制见 Micciancio–Voulgaris，§3.2，Algorithm 2，PDF 第 8–9 页。

为什么旧向量需要进入队列，可以直接由第 17 篇理解：旧向量一旦改变，就可能再次被其他列表向量缩短，不能直接留在已处理列表中。

插入 $v$ 后，$D$ 仍满足两两约化条件：不长于 $v$ 的旧向量已经与它检查过；更长且可被它缩短的旧向量已被移出。这个不变量属于 $D$，不要求待处理的 $Q$ 同时满足。

由第 17 篇的夹角推导，$D$ 的归一化方向之间至少相隔 $60^\circ$，因此可用 $s$ 维接吻数 $\tau_s$ 控制列表容量，例如 $|D|\le\tau_s$。这里 $\tau_s$ 表示单位球面上最小夹角至少为 $60^\circ$ 的点集的最大大小。

队列只回收已有向量，且队列未清空时不增加新样本，因此总存储也能按同一数量级控制。不过，容量界并没有控制需要多少次新采样。此处的空间论证与时间分析之间的区别，见 Micciancio 讲义 §3.1，PDF 第 13–15 页。

伪代码中的 $c_{\max}$ 是累计归零次数阈值，不是连续碰撞次数。它是启发式停止条件；队列清空、碰撞增多或列表两两约化，都不能单独证明已经找到最短向量。

若额外采用经典的池规模与处理次数启发式，常用估计为

这类估计可作为算法比较的基线，不能由接吻数上界直接推出，也不能当成原始论文已证明的最坏情况时间界。参见 Micciancio 讲义 §3.1–§3.2，Table 1，PDF 第 15–16 页。

#4. 阅读三种算法时怎样对应

三者最值得保留的区别是：

• NV：按轮缩小半径。 中心在本轮使用后丢弃，分析同时追踪半径收缩与样本损耗。
• ListSieve：带扰动地增加列表。 旧向量不变，以列表容量和碰撞概率分析得到高概率时间保证。
• GaussSieve：维护两两约化关系。 新旧向量相互约化，队列负责重新处理；几何不变量更直接，但原始 ListSieve 的概率证明不能原样搬过来。

碰撞的含义也随流程变化：NV 中可以表现为相同样本相减归零；ListSieve 显式检查恢复出的向量是否已在列表中；GaussSieve 通过候选最终归零计数。比较运行记录时，应先核对统计口径。

还要区分原始 NV 与后续实现变体。例如，G6K 的 nv 实现使用固定大小数据库；发现足够短的 $x\pm y$ 后，替换数据库中最长的向量。它不要求被替换者就是 $x$ 或 $y$，也不是上面按轮消耗中心的伪代码。G6K 明确将其称为 NV 的放松版本，见 G6K，EUROCRYPT 2019，§4.5–§5.1，PDF 第 16–17 页。

这种变化会影响整数张成与秩的保持，相关代数区别已经在第 17 篇说明。阅读 BGJ 或具体实现时，需要先确定它沿用哪一种数据库更新规则。

#5. 与近邻搜索和分桶的衔接

以上基础版本中，昂贵操作都包含：给定一个候选，在已有向量中寻找满足长度条件的伙伴。

后续近邻搜索与分桶主要改变这个搜索过程：先缩小候选范围，再验证真实的约化条件。研究这种改进时，需要同时保留：

• 搜索能覆盖多少有效向量对；
• 同一向量对会被重复检查多少次；
• 搜索结果如何进入原有的列表、队列或固定数据库；
• 加速后是否仍维护所需的不变量。

下一篇《19 筛法中的近邻搜索与分桶》从线性扫描进入近邻问题，再逐步讨论 LSH、LSF 以及筛法中的分桶机制。

#引用此笔记

• 00 概览与阅读路线
• 19 筛法中的近邻搜索与分桶
• 20 角度 LSH 与多表搜索