Nguyen–Vidick、ListSieve 与 GaussSieve

前置笔记：高斯启发式与随机球面模型、筛法的基本框架与两向量约化。局部投影环境见投影格、BKZ 与局部 SVP。

设当前格为 $\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$ ，令

R=\max_{v\in S}\|v\|, \qquad \frac23<\gamma<1.

本轮构造中心列表 $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′

每轮中心只用于处理本轮后续向量，不进入下一轮。原始外层流程重复筛选直到列表为空，返回最后一个非空列表中的最短向量 [1, pp. 13–17]。实现时也可以持续记录遇到的最短非零向量。

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

R_{t+1}\le\gamma R_t.

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

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

\{x:\gamma R\le\|x\|\le R\}.

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

c_\gamma=\frac{1}{\gamma\sqrt{1-\gamma^2/4}}.

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

c_\gamma\to\sqrt{\frac43}, \qquad \log_2 c_\gamma\to0.2075\ldots, \qquad 2\log_2 c_\gamma\to0.4150\ldots.

这解释了常见的两个指数；固定 $\gamma<1$ 时不能直接把它们当作精确值。更接近 $1$ 的 $\gamma$ 也意味着每轮缩短更少、所需轮数更多 [1, pp. 14–16]。

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

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

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

0\ne w\in\Lambda, \qquad \|w\|\le\mu.

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

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

e\sim\operatorname{Unif}\bigl(B_s(0,\xi\mu)\bigr), \qquad p=e\bmod\mathcal P(B),

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

p-e\in\Lambda.

固定这次采样的 $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$ 的目标写出返回检查；这一流程以原始 ListSieve 为基础 [2, pp. 6–7]。

扰动保留了分析碰撞概率所需的随机性：给定采样阶段的初始 $p$ ， $p-e$ 在 $\Lambda\cap B_s(p,\xi\mu)$ 上均匀分布。约化选择只依赖 $p$ 和当前列表，恢复格向量时才使用 $e$ ；这使证明能够比较“得到重复向量”和“得到新的短差向量”的概率 [3, secs. 2.2.1, 2.3.2]。

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

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

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

T\le2^{3.199s+o(s)}, \qquad M\le2^{1.325s+o(s)}.

这是原始带扰动 ListSieve 的可证明界 [2, sec. 3.1]。

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

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

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

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

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

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

用 $D$ 中不长于 $v$ 的向量反复缩短 $v$ 。
用处理后的 $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

上述伪代码显式写出了符号选择、严格变短和结果记录 [2, pp. 8–9]。

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

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

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

队列只回收已有向量，且队列未清空时不增加新样本，因此总存储也能按同一数量级控制 [3, pp. 13–15]。不过，容量界并没有控制需要多少次新采样。

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

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

M=2^{0.2075\ldots s+o(s)}, \qquad T=2^{0.4150\ldots s+o(s)}.

这类估计可作为算法比较的基线，不能由接吻数上界直接推出，也不能当成原始论文已证明的最坏情况时间界 [3, pp. 15–16]。

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

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

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

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

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

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

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

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

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

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

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

参考文献

1. Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology. 2008. DOI.

2. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms. 2010. DOI.

3. Daniele Micciancio. Sieving algorithms for exact SVP. 2021. 原文.

4. Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. Advances in cryptology – EUROCRYPT 2019. 2019. DOI.

Nguyen–Vidick、ListSieve 与 GaussSieve#

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

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

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

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

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

#参考文献