以下是研究论文的摘要，随后是自动化检查器发现的缺陷。

=== 摘要 ===

技术摘要：通过高效模糊匹配实现可扩展的模糊 PSI

1. 问题陈述

模糊隐私集合求交（fuzzy PSI）允许持有 $d$ 维点集 $Q$ 的发送方和持有点集 $W$ 的接收方，在给定度量（例如 $L_p$，$p \in [1, \infty]$）下，在满足距离阈值 $\delta$（即 $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$）的情况下，私密地计算交集。虽然传统的 PSI 处理精确匹配，但模糊 PSI 对于生物识别和基于位置的服务等含有噪声数据的应用至关重要。

现有方案面临显著的可扩展性挑战：

1. 沉重的密码学原语： 许多协议依赖于昂贵的同态加密（AHE）或混淆电路（GC），导致了极高的具体开销。
2. 较差的渐近复杂度： 最先进的轻量级协议（例如 van Baarsen 和 Pu [46]）通常会产生随距离阈值 $\delta$ 和维度 $d$ 呈 $O((\log \delta)^d)$ 或 $O(\delta)$ 增长的复杂度。这为较大的 $\delta$ 或高维数据造成了严重的瓶颈。
3. 二次方开销： 两两比较会导致 $O(mn)$ 的复杂度，这对于大规模集合是不切实际的。

作者提出了这样一个问题：我们能否构建出既具有具体效率、又具有渐近效率保证，且适用于低维和高维集合的一般 $L_p$ 距离的可扩展模糊 PSI 协议？

2. 方法论

本文提出了一套基于两项核心技术创新的协议套件：渐近高效的模糊匹配和双层哈希框架。

2.1 渐近高效的模糊匹配

作者设计了两种单点模糊匹配协议，用于安全地评估 $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$：

• 角色反转 OPRF 协议：

  • 机制： 该协议改进了以往的 OPRF 方法（以往方法使用前缀树来减少发送方编程，但增加了接收方的计算量至 $O((\log \delta)^{d/2})$）。作者引入了一种两步角色反转 OPRF 机制。
  • 过程：
    1. 发送方对区间前缀进行编程，将其映射到随机值。
    2. 接收方进行评估以获得一组值。
    3. 创新点： 在第二次 OPRF 调用中反转角色。接收方编程一个新的 OPRF，将第一轮的输出映射为单个值，而由发送方进行评估。
  • 结果： 这将接收方的 $O(\log \delta)$ 次评估压缩为每个维度的单个值，从而将计算开销从 $O((\log \delta)^d)$ 降低到 $O(d \log \delta)$。

• 定制化 OT 协议：

  • 机制： 专为输入位长度（$\ell$）较短的情况设计，该协议利用不经意传输（OT）直接计算最高有效位（MSB）和 AND 操作。
  • 结果： 它实现了 $O(d \ell)$ 的开销。当结合领域缩减（见下文）时，它通过消除 OPRF 构建中固有的统计安全性参数 $\lambda$ 依赖，提供了卓越的具体性能。

2.2 模糊 PSI 框架

针对低维集合

作者提出了一个结合空间哈希（Spatial Hashing）和 Cuckoo 哈希（Cuckoo Hashing）的双层哈希框架：

• 空间哈希： 将 $d$ 维空间划分为边长为 $2\delta$ 的网格单元。
• 双层优化：
  • 作者观察到，与其让接收方检查每个点的 $2^d$ 个相邻单元（导致 $O(2^d n)$ 次模糊匹配调用），不如只关注包含发送方点的单元才是相关的。
  • Cuckoo 哈希： 发送方将其点映射到一个表中。接收方将其潜在的相邻单元也映射到同一个表中。
  • 缩减： 这将所需的模糊匹配调用次数从 $O(2^d n)$ 减少到 $O(m)$。
• 领域缩减与一致性检查： 为了利用高效的 OT 匹配，输入领域被缩减为发送方点的局部邻域（边长为 $6\delta$ 的超立方体）。为了防止由于该小领域导致的假阳性（即随机值可能意外落在 $\delta$ 之内），增加了一个一致性检查，验证发送方的点和接收方的点是否映射到完全相同的网格单元。

针对高维集合

为了避免指数级的 $2^d$ 爆炸，作者构建了基于全局不相交假设（Globally Disjoint Assumption，即球体的投影在任何维度上都不重叠）的协议。

• 机制： 他们将基于 OPRF 的模糊匹配编译为多点 PSI。
• 过滤： 协议首先基于 $L_\infty$ 距离生成唯一标识符。由于 $L_\infty$ 限制了 $L_p$，这些标识符充当粗略过滤器。只有具有匹配标识符的点对才会进行严格的 $L_p$ 距离检查。
• 复杂度： 这实现了在集合大小（$m, n$）、维度（$d$）以及距离阈值（$\log \delta$）上的线性渐近开销，即 $O((m+n)d \log \delta)$。

3. 主要贡献

1. 渐近高效的模糊匹配：
   • 一种实现 $O(d \log \delta)$ 开销的角色反转 OPRF 协议，改进了以往工作的 $O((\log \delta)^d)$。
   • 一种具有 $O(d \ell)$ 开销的 OT 协议，适用于短输入。
2. 新的低维框架：
   • 一个结合空间哈希与 Cuckoo 哈希的双层哈希框架，将模糊匹配调用次数从 $O(2^d n)$ 减少到 $O(m)$。
   • 一种输入空间缩减优化方案，并带有一致性检查，以实现高效的 OT 匹配且无假阳性。
3. 改进的高维协议：
   • 在全局不相交假设下的高维集合协议，实现了对 $d$ 的线性复杂度和对 $\delta$ 的对数级 $O(\log \delta)$ 复杂度。
4. 广泛的评估：
   • 在 $L_\infty, L_1,$ 和 $L_2$ 度量下，针对维度 $d \in [2, 64]$ 和阈值 $\delta \in [16, 1024]$ 进行了全面的基准测试。

4. 实验结果

作者实现了他们的协议，并将其与最先进的工作进行了对比：van Baarsen 和 Pu [46]（基于 OPRF）以及 Piske 等人 [38]（基于 OPRF 和 OT）。

• 低维性能 ($d \in [2, 8]$)：

  • 加速： 运行时间比 [46] 快达 145$\times$，比 [38] 快达 25$\times$。
  • 通信： 通信成本比 [46] 降低达 20$\times$，比 [38] 降低达 17$\times$。
  • 可扩展性： 与 [46] 的运行时随 $(\log \delta)^{d/2}$ 增长不同，所提协议的性能在 $\delta$ 增加时保持接近常数。

• 高维性能 ($d \in [16, 64]$)：

  • 加速： 运行时间比 [46] 快达 36$\times$。
  • 通信： 通信成本比 [46] 降低达 54$\times$。
  • 这种优势在距离阈值 ($\delta$) 较大时尤为明显，因为先前的协议在 $\delta$ 方面表现出线性或超线性缩放。

5. 重要性与主张

本文声称在具体和渐近两个层面都推进了模糊 PSI 的发展：

• 渐近改进： 它解决了以往轻量级协议中的 $O((\log \delta)^d)$ 和 $O(\delta)$ 瓶颈，提供了 $O(d \log \delta)$ 以及对集合大小的线性依赖关系。
• 具体效率： 通过结合角色反转 OPRF、OT 和新型双层哈希框架，所提协议实现了巨大的实际加速和通信减少，使得模糊 PSI 在处理更大阈值和更高维度时变得可行。
• 通用性： 该方案支持一般 $L_p$ 距离（$p \in [1, \infty]$），涵盖低维和高维场景，而许多先前的工作仅限于特定度量（如仅限 $L_\infty$）或需要沉重的密码学假设。

作者强调，虽然高维协议依赖于较强的“全局不相交”假设，但低维协议是在更弱、更实际的假设（每个网格单元唯一的中心/球体）下运行的，这与以往高效的工作是一致的。