Efficient Scalable Multi-Party Private Set Intersection

论文学习：Efficient Scalable Multi-Party Private Set Intersection

这篇论文提出了一种基于双中心零共享（Bicentric Zero-Sharing）的高效、可扩展的MPSI协议及其变体，解决了现有方案在参与方数量、通信开销和抗共谋能力方面的局限性。
摘要

本文提出了一种基于双中心零共享（Bicentric Zero-Sharing）的高效可扩展多方隐私集合求交协议（MPSI）及其变体（如MPSI-CA和MTPSI）。通过将MPSI问题简化为两个中心参与者（Pivot与Leader）之间的两方PSI，我们实现了以下核心贡献：

• 双中心零共享的构建
  

提出一种基于不经意键值存储（OKVS）的对称密钥操作方案，通过一轮共享与重构实现零共享。每个参与者的通信复杂度仅为O(n + m)，且无需公钥操作。安全性依赖于Leader与Pivot不共谋的假设，在半诚实模型下可抵抗任意其他参与者的共谋攻击，在随机预言机模型下可抵抗至多n−2个恶意客户端的攻击。

• 高效MPSI及变体协议
  

MPSI：通过结合双中心零共享与两方PSI协议，仅需Pivot和Leader执行两方PSI，其余客户端无额外操作。
MPSI-CA（交集基数计算）与MTPSI（阈值PSI）：通过调用两方PSI变体协议实现，例如基于DH-PSI-CA的实例化方案。

• 性能与可扩展性
  

实验表明，在15个参与者（各含2²⁰元素）的场景下，相比当前最优协议（Nevo等，CCS’21），我们的协议在局域网（LAN）中提速46.4倍，在广域网（WAN）中提速18.3倍，通信成本降低24.7倍。支持超大规模参与者：140个参与者（各含2²⁰元素）时，MPSI与MPSI-CA在LAN中仅需4.557秒与16.02秒。
引言

在安全多方计算（MPC）的众多功能中，多方隐私集合求交（MPSI）是实践需求最强烈的技术之一。在MPSI中，多个参与者各自持有数据集，他们希望在不泄露任何额外信息的前提下计算所有数据集的交集。

根据参与者数量，PSI可分为两方PSI和多方PSI（MPSI）。过去十年间，两方PSI技术发展迅速。基于向量不经意线性评估（VOLE）和不经意键值存储（OKVS）的协议速度已接近原始非安全哈希PSI。两方PSI可应用于隐私联系人发现、安全事件信息共享、密码安全检查等场景。例如，谷歌在2019年基于PSI推出"密码安全检查"插件，帮助用户验证密码安全性而不泄露隐私。此外，研究者还提出了PSI的多种变体，如PSI基数统计（PSI-CA）和阈值PSI（TPSI）。PSI-CA仅输出交集大小，可用于广告转化率测量；TPSI仅在交集大小超过预设阈值
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！