私有集合交集：系统综述

《Chinese Journal of Electronics》：Private Set Intersection: A Systematic Review

　　

各种服务，例如搜索引擎，越来越多地部署在基于云和分布式系统中。然而，数据通常由受信任的服务器管理，使得用户隐私和数据安全成为关键问题。私有集合交集（PSI）是一种强大的密码学原语，它使多方能够计算其数据集的交集，同时不泄露私有输入。在过去二十年中，它得到了广泛研究，从而在计算和通信效率方面取得了显著提升。然而，在许多现实场景中，揭示原始交集仍可能泄露敏感信息。为解决此问题，已开发出众多PSI变体以满足不同的应用需求。在本论文中，研究人员对PSI及其变体进行了全面综述。研究人员根据功能性和底层密码学技术对现有协议进行分类，并分析其理论特性。研究人员重点关注过去五年的最新进展，包括新兴方向如模糊PSI和可更新PSI。研究人员还探讨了这些协议在各领域的应用。最后，研究人员指出了关键研究挑战，包括改进隐私保证、增强计算效率以及确保大规模数据集的可扩展性。这些发现旨在指导未来研究，因为PSI及其变体在推进隐私保护应用中发挥着核心作用。

论文解读文章

**研究背景与问题**

随着云计算和分布式系统的快速发展，服务计算已成为驱动数字应用的关键引擎。然而，传统信任模型要求用户完全信任云服务器，一旦服务器被恶意对手控制，协议的正确性将被破坏，用户隐私也可能泄露。例如，在搜索引擎中，服务器可明文获取用户请求，从而推断偏好并推送定向广告；在数据搜索场景中，用户未加密的数据直接发送给服务器，敏感信息（如商业秘密）可能造成巨大损失。私有集合交集（PSI）是一种强大的密码学原语，允许多方在不泄露各自输入的情况下计算数据集的交集，已在安全数据匹配、可搜索加密等领域得到广泛应用。尽管现有两方PSI协议在性能上已非常高效（如100 Mbit/s信道下6秒内完成百万规模集合交集计算），但在许多实际场景中，仅计算交集本身仍不够——交集元素可能包含敏感信息（如患者姓名）。此外，静态数据集和精确匹配的假设也限制了PSI在动态、近似匹配需求中的适用性。因此，研究人员开展这项系统综述，旨在对PSI及其变体进行系统分类、理论分析，并指出开放挑战与未来方向。

**研究内容与结论**

本论文对PSI协议及其变体进行了全面综述，涵盖理论基础和实际应用。研究人员首先将协议按功能性和密码学构建模块进行分类，并对基于不经意伪随机函数（OPRF）、公钥加密（PKE）和电路（circuit）三种主要框架的协议进行理论分析。随后，研究人员重点探讨了近五年来的新兴变体（如可更新PSI和模糊PSI）及其应用场景。最后，研究人员总结了在隐私、安全性、性能和可扩展性方面的关键挑战，并提出了潜在的未来研究方向。论文指出，PSI及其变体在隐私保护应用中扮演核心角色，该综述可为后续研究提供指导。论文发表在《Chinese Journal of Electronics》。

**主要关键技术方法**

研究人员采用分类法，根据功能性和密码学构建模块将PSI协议分为若干类别，并基于三大技术路线（OPRF、PKE、电路）进行理论比较。对于基于OPRF的协议，进一步细分为不经意传输扩展（OTE）、不经意键值存储（OKVS）、函数秘密共享（FSS）和布隆过滤器（BF）四种构造方式。对于基于PKE的协议，涵盖全同态加密（FHE）、部分同态加密（PHE）、属性基加密（ABE）和硬假设（如Diffie-Hellman、RSA）。对于基于电路的协议，主要采用混淆电路（GC）及优化技术（如Cuckoo哈希）。忽略具体试剂、质粒构建等操作步骤，无特定样本队列来源。

**研究结果**

**1. 分类（Taxonomy）**
研究人员据功能性和构建模块对PSI协议进行分类。通用PSI仅计算交集；多方PSI（MPSI）支持多个参与者联合计算；电路PSI可在交集上执行任意函数；带标签PSI（Labeled PSI）额外输出与交集元素关联的标签；外包PSI（Outsourced PSI）将计算委托给不可信第三方；私有集合并集（PSU）计算并集。类别见表1（忽略表格）。

**2. 基于OPRF的协议（OPRF-Based Protocols）**
基于OPRF的协议效率取决于OPRF构造。主要包括：(a) 不经意传输扩展（OTE）：如BaRK-OPRF和GPSI协议，通过对称加密替代公钥操作降低计算开销。(b) 不经意键值存储（OKVS）：如PaXoS结构，通过优化矩阵大小降低通信开销；在此基础上产生MPSI协议（如O-Ring、K-Star）及恶意安全CPSI协议。(c) 函数秘密共享（FSS）：结合FSS与OT实现半诚实PSI，并扩展至恶意安全。(d) 布隆过滤器（BF）：基于GBF的OPPRF实现线性性能，用于MPSI。研究显示，基于OKVS和FSS的协议在通信效率上具有优势。

**3. 基于PKE的协议（PKE-Based Protocols）**
基于PKE的协议包括：(a) 全同态加密（FHE）：通过多项式编码实现集合交集，通信复杂度为O(n₂log n₁)；并扩展至标签PSI、模糊标签PSI、阈值PSI（TPSI）和多方PSU。(b) 部分同态加密（PHE）：如利用阈值HE与反演布隆过滤器构建MPSI，或基于加法HE与OT实现准线性复杂度的多方TPSI。(c) 属性基加密（ABE）：用于外包PSI中的细粒度访问控制。(d) 硬假设：基于DH或RSA的轻量级方案适用于小集合或不平衡场景。FHE灵活性高但计算开销大，PHE在受限场景中更高效。

**4. 基于电路的协议（Circuit-Based Protocols）**
基于电路的协议主要采用混淆电路（GC）。Huang等提出三种GC-PSI协议，其中排序-比较-混淆（SCS）方案达到O(n·log n)计算复杂度。Pinkas等通过Cuckoo哈希和镜像Cuckoo哈希将比较次数降至O(n)。Ciampi等利用私有集合成员（PSM）测试作为输入，结合GC实现交集。Pinkas等结合Cuckoo哈希与OPPRF实现线性通信复杂度。Su等将两方PSI扩展到多方场景，时间复杂度为O(nm log²(n log₂ m))。

**新兴PSI变体（Novel PSI Variants）**
研究人员介绍可更新PSI和模糊PSI。可更新PSI支持动态插入/删除，现有方案面临高通信成本、隐私泄露及仅支持半诚实模型等问题。模糊PSI基于汉明距离进行近似匹配，现有方法在低维场景有效，但在高维场景可扩展性差且存在误报率与计算复杂度的权衡。

**应用（Applications）**
PSI应用于可搜索加密（如IXT协议利用标签PSI隐藏搜索模式）、联邦学习（如垂直联邦学习中的ID对齐，通过差分隐私或标签PSI实现）、模糊搜索（如基于模糊标签PSI的生物特征匹配）、安全数据库搜索（电路PSI支持连接、相等、并集、求和等操作）和基因组研究（外包PSI用于共享遗传标记）。

**开放挑战与未来方向（Open Challenges and Future Directions）**
隐私泄露：可更新PSI的插入/删除模式及近似匹配的误差阈值可能泄露信息，可引入差分隐私或填充技术。安全性：多数协议仅针对半诚实对手，需加入零知识证明或可验证计算对抗恶意行为；后量子密码（如格密码）可抵御量子攻击。性能：高计算开销限制轻量级应用，可优化布隆过滤器等数据结构。可扩展性：多方场景通信成本随参与者数量快速增长，阈值HE或层次化协议结构有望改善。

**讨论与结论**
本文系统综述了PSI及其变体的理论基础与应用，通过分类和理论比较揭示了不同密码学原语对协议效率的影响。新兴变体（可更新PSI、模糊PSI）虽拓展了应用场景，但仍在隐私、安全性、性能和可扩展性方面面临显著挑战。未来研究应聚焦于设计更高效的动态更新机制、实现恶意安全下的近似匹配、降低多方场景的通信开销，并探索后量子安全方案。这些努力将推动PSI在隐私保护应用中的实际部署。