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

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

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

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

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

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

BGJ 将后一类任务表述为：给定单位向量列表和角度阈值，寻找夹角满足阈值的向量对。参见 Becker–Gama–Joux，ePrint 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 页。

需要区分三个性质：

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

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

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

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

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 页。

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

\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。

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 页。

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

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

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

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

角度 LSH 接入 NV 类筛法和 GaussSieve 的具体方式，可参见 Laarhoven，§3 与 §5，并对照第 18 篇中的更新规则。

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

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

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

#2. 用桶生成候选

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

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

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

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

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

#引用此笔记