# 19 筛法中的近邻搜索与分桶

整理日期：2026-10-16。  
适用范围：欧氏格两向量筛法中的伙伴搜索、分桶候选生成，以及检查成本和有效配对覆盖的基本模型。  
前置笔记：[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)、[17 筛法的基本框架与两向量约化](/knowledge/lattice-sieving-basics/)、[18 Nguyen–Vidick、ListSieve 与 GaussSieve](/knowledge/nguyen-vidick-listsieve-and-gausssieve/)。

设当前筛法维数为 $s\ge2$，待搜索的非零格向量池为 $D=\{x_1,\ldots,x_N\}$。本篇先固定一轮中的输入池，不预设它已经两两约化。

## 1. 筛法需要怎样的近邻搜索

第 18 篇中的基础算法需要反复寻找能够产生较短结果的向量。搜索任务可以分为两种：

- **单个候选的伙伴搜索。** 给定 $x$，在当前池中寻找满足约化条件的 $y$；找到后可能更新 $x$ 并继续搜索。
- **批量配对搜索。** 在整个池中寻找许多有效向量对，供下一轮筛选或数据库更新使用。

BGJ 将后一类任务表述为：给定单位向量列表和角度阈值，寻找夹角满足阈值的向量对。参见 [Becker–Gama–Joux，ePrint 2015/522，摘要中的固定半径近邻问题](https://eprint.iacr.org/2015/522)。

以下批量模型采用“缩短两条向量中较长者”的判据。令

$$
d_{\pm}(x,y)=\min\{\|x-y\|,\|x+y\|\},
$$

则有效对满足

$$
0<d_{\pm}(x,y)<\max\{\|x\|,\|y\|\}.
$$

等长情形下，这对应第 15 篇的 $|\cos\theta|>1/2$，并排除产生零向量的情形。长度不同时，需要保留真实范数；归一化方向只用于组织搜索。

这里通常只需要找到符合长度条件的伙伴，不必找到有限池中距离最小的元素。搜索范围也是当前池中的有限个向量；CVP 的搜索范围则是整个格。

嵌入具体算法时，仍应使用它原有的约化方向和目标长度。例如，用 $y$ 缩短指定的 $x$，与只要求缩短两者中的较长者，是不同的任务。

## 2. 用桶生成候选

分桶先把可能形成有效对的向量放到共同的小集合中，再检查这些集合内部的向量对。

令

$$
u_i=\frac{x_i}{\|x_i\|}\in S^{s-1}.
$$

考虑一个简单的对称球帽模型：选择中心方向 $c_\ell\in S^{s-1}$ 和阈值 $0<\alpha<1$，定义

$$
B_\ell
=\{i:|\langle u_i,c_\ell\rangle|\ge\alpha\}.
$$

它包含以 $c_\ell$ 和 $-c_\ell$ 为中心的两个球帽，用绝对值同时照顾加法与减法方向。桶中存储原向量的编号，长度和坐标仍保留在 $D$ 中。

单侧球帽过滤 $\langle u,c\rangle\ge\alpha$ 是球面 LSF 的基本构造；本篇在此基础上使用对称的两个球帽。参见 [Becker–Ducas–Gama–Laarhoven，SODA 2016，§4，PDF 第 5 页](https://ir.cwi.nl/pub/23692/23692.pdf)。

需要区分三个性质：

- 桶可以重叠，一条向量可以进入多个桶。
- 同桶只意味着成为待检查的候选，不保证满足约化条件。
- 有效对也可能没有进入任何共同的桶，因此需要分析漏检概率。

提高 $\alpha$ 会缩小桶，但也可能降低有效对共同入桶的概率。分桶参数要同时考虑检查成本与搜索覆盖。

## 3. 一个固定输入池的搜索流程

下面的伪代码使用 $t$ 个独立、均匀随机的中心，展示一次批量搜索。它允许跨桶重复检查，也允许重复输出：

~~~text
BucketSearch(D, α, t):
    固定本轮的 D，计算各向量的范数与归一化方向

    重复 t 次：
        c ← 在单位球面上独立均匀采样
        B ← {i : |〈u_i,c〉| ≥ α}

        对 B 中每个无序对 i < j：
            σ ← 1（若 〈x_i,x_j〉 ≥ 0），否则 −1
            w ← x_i − σ·x_j

            如果 0 < ||w|| < max(||x_i||, ||x_j||)：
                输出 (i, j, w)    # 可以流式处理

        释放本桶
~~~

符号选择使 $w$ 在 $x_i-x_j$ 和 $x_i+x_j$ 中取较短者。输出的是候选及其来源，外层算法再决定去重、接纳和替换规则。

这个流程仅描述搜索阶段。它没有规定初始采样、完整筛法的停止条件，也没有凭分桶本身保证找到最短向量。

## 4. 检查次数与有效对覆盖

记第 $\ell$ 个桶的大小为 $b_\ell=|B_\ell|$。如果每个桶内部都完整枚举无序对，且没有跨桶去重，则检查次数为

$$
C=\sum_{\ell=1}^{t}\binom{b_\ell}{2}.
$$

同一对向量在三个桶中出现，就贡献三次检查。因此，平均桶大小不足以确定 $C$；在总入桶次数固定时，桶大小越不均衡，检查次数越多。

对固定源向量对 $(i,j)$，定义共同入桶次数

$$
m_{ij}
=\sum_{\ell=1}^{t}
\mathbf 1\{i,j\in B_\ell\}.
$$

于是

$$
C=\sum_{i<j}m_{ij}.
$$

再令 $E$ 为固定输入池中所有有效无序对的集合，则：

$$
H=\sum_{(i,j)\in E}m_{ij},
\qquad
U=\sum_{(i,j)\in E}\mathbf 1\{m_{ij}>0\}.
$$

其中，$H$ 是包含重复的有效对命中次数，$U$ 是实际覆盖的不同有效源向量对数。对本流程，$C-H$ 是未通过约化检查的次数。

$U$ 仍不等于不同新向量的数量：不同源向量对可能产生相同结果，结果也可能已在池中。实际池更新还取决于接纳规则。

以上等式直接来自固定输入池、完整桶内枚举的计数定义。若提前停止、跨桶去重或在搜索中修改输入池，需要按实际流程重新计数。

## 5. 从入桶概率到覆盖概率

下面的概率公式都针对第 3 节的理想化随机中心模型。

对任意固定单位向量 $u$，令

$$
p=\Pr_c[|\langle u,c\rangle|\ge\alpha]
=2p_s(\alpha),
$$

其中 $p_s(\alpha)$ 是第 15 篇定义的单侧球帽概率。由旋转对称性，$p$ 不依赖 $u$ 的方向，因此对任意固定输入池都有

$$
\mathbb E[b_\ell]=Np.
$$

这个期望不要求池内向量相互独立。

但两个固定向量共同入桶的概率是

$$
q_{ij}
=\Pr_c\!\left[
|\langle u_i,c\rangle|\ge\alpha,\
|\langle u_j,c\rangle|\ge\alpha
\right].
$$

$q_{ij}$ 取决于两条向量的夹角，一般不等于 $p^2$。单侧版本由两个球帽交集的相对面积描述；双侧版本还需要计入对应的符号方向。球帽交集与共同过滤概率的关系见 [BDGL，§2 的球楔定义与 §4，PDF 第 3、5 页](https://ir.cwi.nl/pub/23692/23692.pdf)。

由期望的线性性，检查次数满足

$$
\mathbb E[C]
=t\sum_{i<j}q_{ij}.
$$

固定一对 $(i,j)$，由于不同桶中心独立采样，它至少共同入桶一次的概率为

$$
\Pr[m_{ij}>0]
=1-(1-q_{ij})^t.
$$

因此，不同有效源向量对的预期覆盖数为

$$
\boxed{
\mathbb E[U]
=\sum_{(i,j)\in E}
\left[1-(1-q_{ij})^t\right].
}
$$

覆盖公式使用了同一对向量在不同桶中的命中事件独立这一条件，不要求不同源向量对之间独立。检查次数的期望只使用线性性。使用结构化、相关或自适应选择的桶时，需要重新核对覆盖公式。

若希望某个固定有效对的漏检概率至多为 $\delta\in(0,1)$，且 $q_{ij}>0$，则需要

$$
t\ge
\frac{\ln\delta}{\ln(1-q_{ij})}
\approx
\frac{\ln(1/\delta)}{q_{ij}},
\qquad q_{ij}\ll1.
$$

这是单个固定对的要求；覆盖全部有效对还要控制整体失败概率。若某类有效对的 $q_{ij}=0$，增加桶数也无法找回它们。

只有进一步把输入方向建模为独立球面均匀样本，并让中心与输入独立时，才可对输入与中心共同取期望，得到

$$
\mathbb E_{D,c}\!\left[\binom{b_\ell}{2}\right]
=\binom N2p^2.
$$

这个随机输入平均式不能直接替代实际固定池中的 $\sum q_{ij}$，尤其不能把有效对的共同入桶概率设成 $p^2$。桶内筛选和后续多层条件还会改变分布。

## 6. 分桶成本需要包含建桶

对第 3 节的直接实现，每个中心都扫描全部 $N$ 条向量。按 $s$ 维内积的运算量计，

$$
T_{\mathrm{build}}=O(stN),
\qquad
T_{\mathrm{check}}=O(sC).
$$

完整流程还要计入候选去重、池更新和访存成本。检查次数变少，并不自动意味着总时间下降；寻找相关桶和生成桶成员本身也可能很昂贵。

内存同样取决于处理顺序：若逐桶处理并释放，桶成员引用的峰值为 $\max_\ell b_\ell$；若同时保存全部桶，则为 $\sum_\ell b_\ell$。原向量、中心、索引和候选缓冲的存储另计。

BDGL 的 LSF 分析明确把“高效找到一个向量所属的过滤器”作为关键条件，并进一步构造相应的结构化方法。参见 [BDGL，§3 的 Theorem 3.1 及其后的说明、§5](https://ir.cwi.nl/pub/23692/23692.pdf)。

## 7. LSH、LSF 与具体筛法的衔接

**LSH 通过哈希值组织桶。** 在一张标准哈希表中，$h(u)$ 指定向量所属的一个桶；查询检查相同键对应的候选，多张表提供多次相遇机会。

以 Charikar 的随机超平面哈希为例，随机选择单位方向 $a$，令

$$
h_a(u)=\mathbf 1\{\langle a,u\rangle\ge0\}.
$$

若两方向夹角为 $\theta$，则

$$
\Pr[h_a(u)=h_a(v)]
=1-\frac{\theta}{\pi}.
$$

夹角越小，同键概率越大；同键仍不保证满足筛法长度条件。构造与公式见 [Laarhoven，CRYPTO 2015，ePrint 2014/744 的 23 页版，§2.5，式 (3)–(4)，PDF 第 6 页](https://eprint.iacr.org/2014/744.pdf)。

用于同时处理加法与减法时，需要查询正负两个方向，或采用等价的符号对称设计。

**LSF 通过过滤条件组织桶。** 每个过滤器判断一个向量是否通过；一个向量可以通过多个过滤器，也可能一个都不通过。第 2 节的球帽桶提供了一个具体模型。两者的区别在于候选集合如何生成，不能仅由程序是否使用哈希表来判断。参见 [BDGL，§3，PDF 第 4–5 页](https://ir.cwi.nl/pub/23692/23692.pdf)。

将这些搜索方法接入筛法，还要维护原算法的状态：

- 批量流程可以固定本轮输入，收集候选后统一更新。
- 动态流程中，向量改变后，需要同步更新对应索引；再次约化也需要根据新向量重新搜索。
- 概率搜索没有找到伙伴，只表示本次未命中，不能据此认证“两两约化完成”，也不能直接继承完整扫描时的不变量。

角度 LSH 接入 NV 类筛法和 GaussSieve 的具体方式，可参见 [Laarhoven，§3 与 §5](https://eprint.iacr.org/2014/744.pdf)，并对照第 18 篇中的更新规则。

后续先展开角度 LSH 的多位组合与多表搜索，再进入球面 LSF 和 BGJ 递归分桶。比较具体方法时，继续沿用本篇的四类量：建桶成本、向量对检查次数、不同有效对覆盖数，以及实际池更新。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [20 角度 LSH 与多表搜索](/knowledge/angular-lsh-and-multiple-tables/)
- [21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)
- [22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)
- [23 多层分桶的参数选择与优化](/knowledge/multilevel-bucketing-optimization/)
- [24 重复配对、去重与有效覆盖](/knowledge/duplicate-pairs-and-effective-coverage/)