💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

本文介绍了首个针对一般 $L_p$ 距离在单侧假设下的具体高效模糊隐私集合求交协议，该协议利用轻量级对称密钥原语和前缀字典树技术实现了 $O(\log \delta)$ 的复杂度，并在计算速度和通信开销方面显著优于先前的最先进工作。

原作者： Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

发布于 2026-08-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

在数字时代，两个组织通常需要在不向对方泄露全部秘密的情况下寻找共同点。想象一下，一家医院持有特定病症的患者名单，而一家研究机构持有志愿者名单。他们想知道哪些志愿者同时也是患者，但双方都不想交出各自的完整名单，因为这会暴露名单中其他人的隐私数据。标准的计算机协议可以高效地解决这种精确匹配问题，但当数据略有偏差时，这些协议就会失效。在现实世界中，名字可能拼写错误，位置可能略有偏差，生物识别扫描也会因日而异。如果医院的记录显示为“John Smith”，而志愿者的记录显示为“Jon Smyth”，标准系统会认为两者不匹配，尽管他们其实是同一个人。这就是“模糊”匹配发挥作用的地方，这是一种旨在寻找这些近似连接的方法。然而，安全地进行这种匹配极其困难。如果系统试图将每一个名字的所有可能变体与每一个其他变体进行比较，所交换的数据量会变得如此庞大，以至于导致进程停滞，或者需要极其沉重的数学机制，使其在日常使用中变得不切实际。

一支研究团队现在开发出了一种既快速又轻量化的执行这种模糊匹配的新方法。他们的工作专注于这样一种场景：两个参与方中只有一个需要遵循关于其数据排列方式的严格规则，而另一方的数据可以是任何混乱的顺序。以往在如此宽松的条件下解决该问题的尝试，要么依赖于沉重、缓慢的密码学工具，要么要求双方都拥有完美有序的数据，而这在现实中很少见。由来自新加坡和美国的 Xinpeng Yang 及其同事开发的新方法，仅使用简单、快速的构建模块就实现了相同的目标。他们成功地将这些比较所需的时间和数据量降低了巨大的幅度，使得安全、近似的匹配在许多现实场景中首次变得可行。

这项成就的核心在于研究人员如何处理数据点之间的“距离”。在这种语境下，距离是衡量两个信息点之间差异程度的度量，例如两个名字之间有多少个字母不同，或者两个 GPS 坐标之间有多远。目标是找到那些距离小于特定阈值的配对。研究人员意识到，以往的方法试图检查数据点的每一种可能的变体，这导致随着允许的差异增加，搜索空间呈爆炸式增长。为了解决这个问题，他们引入了一种类似于智能过滤器的方法。系统不再检查每一个可能的选项，而是将数据组织成一种树状结构，使其能够瞬间跳过大量无关的信息。这一改变将计算量从随搜索规模呈指数级增长的水平，降低到了仅随对数级增长的水平。在实际操作中，这意味着即使数据点之间的允许差异增加两倍或三倍，运行检查所需的时间也几乎不会增加。

团队将他们的新协议与目前最优秀的现有方法进行了测试。结果是惊人的。与 2024 年的一项近期协议相比，他们的新系统运行速度提高了多达 239 倍，通信带宽减少了多达 20 倍。针对 2025 年的一种方法，提速达到了 518 倍，数据传输减少了 63 倍。在针对另一种 2025 年构建方案的具体对比中，新系统的速度快了近 5,000 倍，且通信需求减少了 282 倍。这些数字并非仅仅是理论上的；研究人员实现了完整的系统，并在各种数据规模和设置下进行了广泛的实验。他们证实，无论发送方还是接收方是拥有有序数据的一方，该方法都能奏效，并且它支持多种类型的距离度量，而不仅仅是简单的度量。

他们工作中的一个关键创新是处理“单侧”假设的能力。在许多之前的安全系统中，双方都必须达成严格的协议，例如确保其数据点之间的间距足够远以避免混淆。这在现实生活中往往是不可能的，因为数据往往以集群或随机模式出现。新方法仅要求一方拥有相对有序的数据集，而另一方可以拥有完全任意、混乱的数据。这种灵活性使得该技术适用于诸如接触者追踪或基于位置的服务等场景，其中一个实体可能拥有已知位置的结构化数据库，而另一方则拥有非结构化的用户输入流。通过仅依赖于轻量级的对称密钥技术——本质上是快速且高效的标准加密工具——研究人员避开了以往阻碍类似尝试的沉重、缓慢的数学运算。

研究人员还探索了在数据稀疏（即数据点分布较散而非聚集）的情况下如何使系统更加高效。在这些情况下，他们发现通过交换双方在匹配过程中的角色，可以进一步平衡工作负载并提高性能。这种适应性表明，该系统可以在无需重新设计的情况下，针对不同的应用类型进行调整。这项工作证明，构建不仅在理论上成立，而且在实践上足够快速、可用于现实世界部署的安全隐私保护系统是可能的。

这项工作的意义不仅限于速度。通过使模糊匹配变得高效，研究人员为更复杂的隐私保护应用打开了大门。由于担心隐私泄露或匹配过程过于缓慢，许多组织长期以来一直避免共享数据，而现在他们可以考虑进行安全的协作。无论是为了医学研究而匹配患者记录，还是在不暴露生物识别模板的情况下验证用户身份，亦或是寻找大型目录中的相似物品而不必公开目录内容，进入门槛都已显著降低。这项研究证明，通过正确的算法方法，可以解决隐私与性能之间的权衡问题，从而让数据即使在不完美或带有噪声的情况下也能安全流动。

最后，论文提出了一个困扰多年的问题的具体解决方案：如何在不牺牲速度或要求不切实际的条件下，在私密数据中寻找近似匹配。研究人员不仅提出了一个新想法，还构建并测试了它，并证明了其性能比以往任何方法都高出数个数量级。他们的工作证明，通过优化问题的底层逻辑，而非仅仅依靠投入更多的计算能力，可以取得怎样的成就。对于好奇的观察者来说，其结果展示出的不是一台沉重、笨拙的机器，而是一个精准、高效的工具，随时准备应对充满杂乱、不完美数据的真实世界。

技术摘要：单侧假设下的高效模糊 PSI

问题陈述

模糊隐私集合求交（Fuzzy Private Set Intersection, Fuzzy PSI）允许两方（发送方和接收方）识别各自输入集中近似匹配的元素。具体而言，给定距离阈值 $\delta$ 和度量函数 $dist(\cdot, \cdot)$ ，接收方旨在学习所有满足存在接收方元素 $\mathbf{w}$ 使得 $dist(\mathbf{q}, \mathbf{w}) \le \delta$ 的发送方元素 $\mathbf{q}$ 。

虽然标准 PSI 已取得显著进展，但模糊 PSI 在效率与底层假设强度之间面临权衡。现有的针对一般 $L_p$ ( $p \in [1, \infty]$ ) 距离的构建通常分为两类：

双侧假设： 要求双方的输入都必须满足强几何分离约束（例如，点与点之间需满足 $2\delta$ 或 $4\delta$ 的间隔）。这类协议虽然高效，但在处理现实世界的噪声数据时往往不切实际。
单侧假设： 仅要求其中一方的输入满足分离约束，而另一方可以持有任意输入。然而，现有的单侧解决方案要么依赖于沉重的密码学原语（如加法同态加密），要么在阈值 $\delta$ 上承受巨大的渐近开销（例如 $O(\delta)$ 或 $O((\log \delta)^d)$ ）。

核心挑战在于：如何在仅依赖轻量级对称密钥原语的情况下，为一般 $L_p$ 距离构建具体的、高效的、基于弱单侧假设的模糊 PSI 协议。

方法论

作者提出了一种基于 秘密共享不透明可编程伪随机函数（so-OPPRF） 和 空间哈希（Spatial Hashing），并结合 前缀树（Prefix Trie） 技术的框架。

1. 多点模糊匹配原语

为了在不泄露信息的前提下处理一方的任意输入，本文引入了两种无假设的多点模糊匹配协议：

1 对 $n$ 匹配（接收方持有任意点）： 发送方围绕其单个点对 so-OPPRF 进行编程。为了防止接收方通过聚合份额中的碰撞推断出发送方的输入分布（这是先前工作中存在的泄露问题），作者引入了 等值条件重随机化（Equality-conditional Randomization, EqRand）。该原语在保留匹配输入正确总和的同时，对非匹配输入进行重随机化，从而确保即使多个接收方点映射到同一个编程区间时也能保证隐私。
$m$ 对 1 匹配（发送方持有任意点）： 角色互换。接收方围绕其单个点对 so-OPPRF 进行编程。发送方在其多个点上评估该函数。由于接收方不会从发送方侧重建聚合值，因此自然避免了泄露问题，且无需使用 EqRand。

2. 单侧假设下的模糊 PSI

基于上述原被，作者构建了在两种特定单侧假设下的完整 $m$ 对 $n$ 模糊 PSI 协议：

唯一单元假设（Unique Cell Assumption）： 每个空间单元（边长为 $2\delta$ ）内最多包含一个受限方的点。
唯一块假设（Unique Block Assumption, 更稀疏）： 每个空间单元与受限方的最多一个 $L_\infty$ 球相交。

该协议利用空间哈希对空间进行划分。受限方使用由其点和单元标识符导出的键对 so-OPPRF 进行编程，以确保无碰撞。不受限方则在其点和相邻单元上评估函数。使用 so-OPPRF 确保输出是秘密共享的，从而防止任何一方获知对方的原始数据。

3. 前缀树优化

为了解决先前工作中存在的随 $\delta$ 呈线性或超线性增长的复杂度问题，作者引入了 前缀树（Prefix Trie） 技术。

机制： 并非枚举区间 $[w - \delta, w + \delta]$ 中的所有点（这需要 $O(\delta)$ ），而是使用 PxTrie 算法将区间编码为 $O(\log \delta)$ 个前缀节点。
逐维过滤： 先前的研究需要评估跨 $d$ 个维度的所有前缀组合，导致了 $O((\log \delta)^d)$ 的复杂度。作者引入了 条件选择（Conditional Selection, ConSel） 原语，实现逐维度过滤前缀。由于每个维度最多只有一个前缀能与目标匹配，搜索空间从 $O((\log \delta)^d)$ 被剪枝至 $O(d \cdot \log \delta)$ 。
结果： 这使得在一般 $L_p$ 距离下，针对阈值 $\delta$ 的复杂度达到了 $O(\log \delta)$ ，较之前的 $O((\log \delta)^d)$ 或 $O(\delta)$ 取得了显著提升。

4. 处理一般 $L_p$ 距离

对于 $L_p$ 距离 ( $p > 1$ )，协议将每维距离贡献的 $p$ 次幂 ( $|t|^p$ ) 编码进 so-OPPRF 的值中。随后，双方通过安全多方计算（加法和乘法）来聚合这些份额，并检查总距离是否在阈值 $\delta^p$ 之内。

核心贡献

首个针对一般 $L_p$ 的高效单侧模糊 PSI： 本文展示了针对一般 $L_p \in [1, \infty]$ 距离、完全基于轻量级对称密钥原语（so-OPPRF, OKVS, silent OT）的第一个具体高效的单侧模糊 PSI 协议。
对 $\delta$ 的对数级复杂度： 通过将前缀树技术与逐维度过滤机制进行非平凡的集成，协议实现了对距离阈值的 $O(\log \delta)$ 复杂度，优于现有最先进工作的 $O((\log \delta)^d)$ 或 $O(\delta)$ 复杂度。
灵活的假设支持： 该框架支持 发送方侧 和 接收方侧 场景，以及 唯一单元 和 唯一块 假设。唯一块假设允许通过反转编程与评估的角色来进一步优化，以利用“编程比评估 so-OPPRF 更廉价”的特性。
广泛的评估： 作者实现了这些协议，并将其与最先进的工作（如 van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6] 等）进行了对比。

实验结果

评估在配备 AMD EPYC 9554 处理器的服务器上进行。结果显示在通信和计算方面均有显著提升：

对比 van Baarsen 和 Pu (EUROCRYPT'24)： 计算速度提升高达 239倍，通信量降低高达 20倍。
对比 Dang et al. (CCS'25)： 加速高达 518倍，通信量减少高达 63倍。
对比 Bui et al. (ASIACRYPT'25)： 计算速度提升高达 4818倍，通信量降低高达 282倍。

前缀优化变体（Ours-Px）在处理大 $\delta$ 和高维数据时表现出更优的通信性能，而未优化变体（Ours）由于计算开销较低，在较小阈值下极具竞争力。

意义与主张

本文声称解决了模糊 PSI 协议中几何假设强度与效率之间的长期权衡问题。通过证明在弱单侧假设下，仅使用轻量级对称密钥原语即可实现通用的 $L_p$ 模糊 PSI，这项工作使模糊 PSI 在数据存在噪声且无法保证严格分离假设的现实场景中更具适用性。

作者强调，其协议在同等假设下显著优于以往工作，实现了数量级的效率提升。通过前缀树实现的逐维度过滤机制被视为一项关键的技术创新，它打破了阈值参数对维度的指数依赖，使得协议能够扩展到高维数据和大匹配阈值的场景。