💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

本文提出了针对通用 $L_p$ 距离的新型模糊隐私集合求交（FPSI）协议，该协议仅使用不经意传输和对称密钥原语，实现了对距离阈值 $\delta$ 的最优对数级依赖，从而消除了对昂贵同态加密的需求，并在运行时间和通信开销上显著优于现有技术方案。

原作者： Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，有两位主角——爱丽丝（Alice）和鲍勃（Bob），他们想要找出各自收藏品中是否有任何“相似”的物品，但又不想向对方展示自己的完整列表。

问题所在： 在标准的博弈中，他们只能匹配完全相同的物品（例如，双方都有一个“红苹果”）。
变体（模糊 PSI）： 在这个新游戏中，他们想要匹配“足够接近”的物品。例如，如果爱丽丝有一个“红苹果”，而鲍勃有一个“略微受损的红苹果”，他们应该将其计为一个匹配项。规则是：“如果我们两个物品之间的差异小于特定的距离（我们称之为阈值/Threshold），我们就视为匹配。”

要在这种情况下安全地进行匹配是一个挑战。爱丽丝不应该得知鲍勃的整个列表，鲍勃也不应该得知爱丽丝的整个列表。他们只想知道哪些物品是足够接近的。

旧的方法：缓慢且昂贵的搜索

以往的这种“模糊匹配”方法存在两个大问题：

“线性”陷阱： 如果“接近程度”的阈值很大（比如 100 个单位），计算机必须为每一个项目检查 100 种不同的可能性。这就像是在草堆里找针，必须一根一根地检查每一根稻草。阈值越大，速度就越慢。
“重型机械”问题： 为了安全地实现这一点，旧方法使用了非常沉重、缓慢的密码学工具（如加法同态加密）。这就像是试图用一辆笨重、耗油巨大的卡车来发送一条秘密信息，而其实用自行车就能完成。

新的突破：“前缀”捷径

这篇论文介绍了一种新的游戏方式，它是快速、轻量级且聪明的。

1. “邮政编码”类比（前缀/Prefixes）

作者并没有检查范围内的每一个数字（比如检查是否为 10, 11, 12... 直到 100），而是使用了被称为**“前缀”**的小技巧。

想象你在寻找一栋房子。

旧方法： 你敲开社区里的每一扇门，看看里面是否住着你的朋友。
新方法： 你查看邮政编码。如果你的朋友住在“10001”，你只需要检查具有该前缀的房子即可。你不需要检查整个城市。

作者意识到，任何数字的“范围”（阈值）都可以被分解为仅有的几个“邮政编码”（前缀）。

神奇之处： 检查这些前缀所需的时间不会随着阈值的增大而增长，而是呈对数级增长。
- 如果阈值翻倍，工作量只增加一点点。
- 如果阈值扩大 100 倍，工作量也仅仅是翻了一倍。
- 类比： 这就像在图书馆里找书。检查每一本书要花很长时间，但检查书架标签（前缀）只需几秒钟，无论书架上有多少本书。

2. “轻量级”工具（对称原语/Symmetric Primitives）

作者用“自行车”（对称密钥原语和不经意传输/Oblivious Transfer）取代了沉重的“卡车”（昂贵的加密）。

不经意传输 (OT)： 想象一名服务员，他可以给你两个秘密菜单项中的一个，而你不知道他给了你哪一个，同时他也不知道你选了哪一个。作者利用这一点，在不泄露整个列表的情况下安全地交换信息。
结果： 他们的系统完全由这些轻量级、快速的工具构建而成。

两种场景：小房间 vs. 大礼堂

论文根据数据的“拥挤程度”（维度/dimensionality）提供了两种不同的策略：

场景 A：低维情况（“公寓”假设）

设定： 想象一个小房间，人们站得很远（至少距离阈值的 2 倍）。
策略： 他们使用空间哈希（Spatial Hashing）。想象将房间划分为网格。如果两个人很接近，他们必然在同一个网格或相邻的网格中。该协议只检查这些特定的网格。
创新点： 他们将这种网格系统与新的“前缀”捷径以及一种特殊的“等值检查”工具（称为 ECSS）结合起来。这使得他们能够瞬间找到匹配项，而无需检查每一对组合。

场景 B：高维情况（“分离”假设）

设定： 想象一个巨大的、多维的仓库。在高维空间中，将空间划分为网格会导致产生过多的空网格（即“维度诅咒”）。
策略： 他们使用分布式 ID 生成（Distributed ID Generation）。他们不再使用网格，而是根据位置为每个项目生成一张唯一的“身份证”。
创新点： 他们创造了一种新的方法，利用其“前缀”技巧来安全地生成这些 ID。即使在巨大的仓库里，他们也能生成这些 ID，使得如果两个项目很接近，它们的 ID 就会匹配，同时又不会泄露实际的位置。

“秘密武器”：等值条件和（ECSS）

他们发明的一个核心数学工具叫做等值条件和（Equality Conditional Sum, ECSS）。

运作方式： 想象爱丽丝和鲍勃各有一份数字列表。他们想要累加这些数字，但仅当满足特定条件时（例如，“仅当前缀匹配时”）才进行累加。
神奇之处： 他们可以在不泄露各自数字的情况下安全地进行这种加法。如果前缀不匹配，结果就是随机噪声；如果前缀匹配，结果则是正确的总和。这使得他们能够在不查看实际数值的情况下，验证项目是否接近。

结果：巨大的加速

作者构建了一个系统的运行版本，并将其与现有的最佳方法进行了对比测试。

速度： 他们的系统比之前的最佳方法快了高达 43.7 倍。
数据量： 传输过程中使用的网络数据减少了高达 31.3 倍。
可扩展性： 当数据集变得非常大时，其他系统会崩溃（内存溢出），而他们的系统则能保持平稳运行。

总结

简而言之，这篇论文通过以下方式解决了“模糊匹配”问题：

取代了缓慢、沉重的加密，转而使用快速、轻量级的工具。
利用“前缀”（类似于邮政编码）将缓慢的线性搜索转变为快速的对数搜索。
创建了新的“秘密求和”工具，让双方可以在不泄露秘密的情况下检查接近程度。

其结果是，该系统几乎可以瞬间在海量的隐私数据集中找到“相似”的项，使大规模的隐私保护数据匹配变得切实可行。

技术摘要：基于对称原语且对距离阈值具有精确对数依赖性的模糊 PSI

问题陈述
模糊隐私集合求交（Fuzzy Private Set Intersection, FPSI）使发送方拥有的 $d$ 维向量集合 $Q$ 与接收方拥有的集合 $W$ 能够识别出满足条件的项 $q \in Q$ ，即存在 $w \in W$ 使得 $\text{dist}(q, w) \le \delta$ ，同时不对额外信息进行泄露。虽然标准 PSI 已实现了极高的效率，但现有的 FPSI 协议面临显著的理论与实际瓶颈。以往的工作通常表现出对距离阈值 $\delta$ 的线性缩放（即 $O(\delta)$ ），或者仅在 $L_\infty$ 距离下实现多项式对数依赖。支持通用 Minkowski 距离（ $L_p$ ， $p \in [1, \infty]$ ）且对 $\delta$ 具有对数依赖性的协议，要么依赖于昂贵的加法同态加密（AHE），要么在维度 $d$ 上遭受安全性缺陷或指数级复杂度项的影响。本研究的目标是使用仅由高效对称密钥原语构建的协议，实现对通用 $L_p$ 距离的精确对数依赖于 $\delta$ 。

方法论与核心技术
作者提出了完全基于不经意传输（OT）和对称密钥原语的新型 FPSI 协议，避免了使用 AHE 等公钥操作。该构建依赖于两个主要假设：适用于低维场景的 apart 假设，以及适用于高维场景的 separate 假设。

前缀表示与区间测试：
核心创新在于使用 $O(\log \delta)$ 个前缀来替代枚举所有整数区间 $[q_k - \delta, q_k + \delta]$ 的过程（其成本为 $O(\delta)$ ）。这使得每维度的区间测试成本降低至 $O(\log \delta)$ 。
等值条件和/内积份额（ECSS/ECIPS）：
为了处理前缀匹配所需的交互，同时避免泄露发送方的输入或引入指数级开销，作者引入了两种新的密码学原语：
- 等值条件和份额（Equality Conditional Sum Share, ECSS）： 用于 $L_\infty$ 距离。它允许各方在输入向量匹配的情况下计算值的总和，并输出结果的秘密份额。
- 等值条件内积份额（Equality Conditional Inner-Product Share, ECIPS）： 用于通用 $L_p$ 距离。它在条件相等的情况下计算内积，通过二项式展开实现对 $|w_k - q_k|^p$ 的计算，而无需泄露具体的项。
  这两种原语均通过 OT、不经意可编程伪随机函数（OPPRF）和置换+份额（Permute+Share, PS）协议高效实现。
处理多个元素：
- 低维度（ $L_\infty$ 和 $L_p$ ）： 协议利用空间哈希（网格单元）结合 Cuckoo 哈希来减少两两比较的数量。作者通过使用共享 OPRF（sOPRF）进行了优化，消除了空桶中虚拟值的需求，从而隐藏了发送方的哈希位置，并在特定配置下移除了对全局置换步骤的需求。
- 高维度（ $L_\infty$ 和 $L_p$ ）： 为了避免空间哈希带来的 $O(2^d)$ 指数级成本，作者采用了分布式 ID 生成（dIDG）协议。该协议生成元素的唯一 ID，使得接近的元素共享相同的 ID。作者识别了先前 dIDG 构建（特别是 [DZL25]）中存在的安全缺陷（即碰撞泄露问题），并提出了一种基于 sOPRF 和 ECSS 的安全对称密钥型 dIDG。

核心贡献

新原语： 引入了 ECSS 和 ECIPS，这些原基使得仅使用对称原语即可实现对 $\delta$ 具有精确对数依赖性的高效模糊匹配。
最优复杂度： 首次实现了针对通用 $L_p \in [1, \infty]$ 距离的 FPSI 协议，其对 $\delta$ 的复杂度为严格的对数级 $O(d \log \delta)$ 。这是理论最优的，因为在长度为 $O(\delta)$ 的区间内区分数值需要 $\Omega(\log \delta)$ 位的信息量。
安全性与效率： 协议消除了对 AHE 的依赖，将其替换为 OT 和对称密钥操作。作者还识别并修复了近期基于前缀的协议（如 [DZL25]）中的安全漏洞，这些协议存在掩码重用和碰撞泄露的问题。
可扩展构建： 针对低维度（使用空间哈希）和高维度（使用 dIDG）提供了独立的构建方案，两者均实现了最优渐近复杂度。

实验结果
作者实现了其协议，并将其与最先进的工作（[GQL+24], [DZL25], [BGMP25]）进行了对比。

性能： 新协议显著优于现有技术。在低维度设置下，其运行速度提升高达 43.7 倍，通信开销降低了 31.3 倍。
可扩展性： 当集合规模达到 $2^{16}$ 时，先前的研究（如 [GQL+24] 和 [DZL25]）在高维度设置下遇到了内存溢出问题，而所提出的协议在相同配置下仍能成功执行。
阈值依赖性： 实验证实，运行时间和通信成本随 $\delta$ 呈对数级增长，这与以往具有线性依赖性的协议所观察到的线性缩放形成了鲜明对比。

意义
本文声称在 FPSI 的最优阈值缩放方面取得了理论突破，证明了在不使用昂贵公钥密码学的情况下，实现通用 $L_p$ 距离对 $\delta$ 的精确对数依赖是可行的。在实践层面，通过消除与距离阈值和维度相关的效率瓶颈，该研究推动了需要模糊匹配的领域（如基因组序列匹配、相似图像检索及受损凭据检测）中可扩展 FPSI 应用的可行性。