Efficient Malicious Multiparty Private Set Intersection Supporting Cardinality, Sharing, and Batching

Xiyuan Han

doi:10.1109/TIFS.2026.3671114

2026-03-05

PRE

Kim-Kwang Raymond Choo

DOI：10.1109/TIFS.2026.3671114

原文链接

原文求助

摘要

En 中文

高效且恶意安全的多方私有集合交集（mPSI）协议——尤其是支持基数（mPSI-CA）或秘密共享输出且通信开销低的变体——在性能和可扩展性方面仍面临持续挑战。然而，现有方法要么依赖于非合谋中心的强安全假设，要么在计算和通信开销方面成本较高。为解决这些局限性，本文提出了一套新的协议，并在真实/理想模型中对其进行形式化，以证明协议的安全性。首先，我们的核心mPSI协议在标准诚实多数模型下实现了恶意安全，仅依赖于对称密钥原语。该方法采用轻量级、基于 oblivion key-value store（OKVS）的架构，其中每个非枢纽方仅向指定的枢纽方发送单条消息。受Nevo等人（CCS 2021）的启发，该方法通过仔细委托核心计算来最小化客户端开销。我们将此框架扩展以支持基数（mPSI-CA）和秘密共享（mPSI-SS）功能，这需要特定方之间满足额外的非合谋假设。我们还引入了一种基于中国剩余定理（CRT）的批处理技术，用于并行mPSI，通过压缩多个OKVS结构实现近线性的通信节省。该方法通常以更高的计算成本（来自多项式运算和CRT）换取通信效率，但在通信至关重要或批处理大量小项集时效果显著，此时编码计算具有竞争力。最后，我们在局域网（LAN）和广域网（WAN）环境中对所提出的mPSI和mPSI-CA协议进行了实现和评估，展示了其实用优势。例如，在所描述的LAN设置（15方，$t=7, m=2^{20}$）中，我们的mPSI协议比Nevo等人（CCS 2021）快$3.0\times$，且通信开销低$2.5\times$。与Gao等人（CCS 2024）的方法相比，在较弱假设下，我们的恶意安全协议快$1.4\times$，且通信开销相当。

Keyword:

Private set intersection

secure multiparty computation

malicious adversarial model

symmetric-key cryptography

secret sharing

batch processing