筛法中的近邻搜索与分桶

前置笔记：高斯启发式与随机球面模型、筛法的基本框架与两向量约化、Nguyen–Vidick、ListSieve 与 GaussSieve。

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

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

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

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

BGJ 将后一类任务表述为：给定单位向量列表和角度阈值，寻找夹角满足阈值的向量对 [1, sec. Abstract]。

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

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

则有效对满足

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

等长情形下，这对应高斯启发式与随机球面模型的 $|\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 的基本构造 [2, p. 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)$ 是高斯启发式与随机球面模型定义的单侧球帽概率。由旋转对称性， $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$ 。单侧版本由两个球帽交集的相对面积描述 [2, pp. 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 分析明确把“高效找到一个向量所属的过滤器”作为关键条件，并进一步构造相应的结构化方法 [2, secs. 3, 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}.

夹角越小，同键概率越大 [3, p. 6]。同键仍不保证满足筛法长度条件。

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

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

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

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

角度 LSH 可以用于 NV 类筛法和 GaussSieve 的近邻候选搜索 [3, secs. 3, 5]。阅读时可对照经典格筛法中的更新规则。

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

参考文献

1. Anja Becker, Nicolas Gama, and Antoine Joux. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. 2015. 原文.

2. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms. 2016. DOI.

3. Thijs Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. Advances in cryptology – CRYPTO 2015. 2015. DOI.

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

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

#2. 用桶生成候选

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

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

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

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

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

#参考文献