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

doi:10.1109/TIFS.2026.3671114

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

2026-03-05

0

PRE

AI

Kim-Kwang Raymond Choo

DOI：10.1109/TIFS.2026.3671114

Original

Original request for help

Save

Abstract

En 中文

Efficient and maliciously secure multiparty private set intersection (mPSI)—especially for variants enabling cardinality (mPSI-CA) or secret shared outputs with low communication overhead—faces ongoing challenges regarding performance and scalability. However, existing approaches are either based on strong security assumptions of non-colluding centers or are relatively expensive in terms of computational and communication overheads. Addressing these limitations, this paper introduces a new suite of protocols and formalizes them in a real/ideal model to prove the security of the protocols. Firstly, our core mPSI protocol achieves malicious security under the standard honest majority model, relying solely on symmetric-key primitives. The approach employs a lightweight, oblivious key-value store (OKVS)-based architecture where each non-pivot party sends only a single message to a designated pivot. This approach, inspired by Nevo et al. (CCS 2021), minimizes client overhead by carefully delegating core computations. We extend this framework to support cardinality (mPSI-CA) and secret sharing (mPSI-SS) functionalities, which require an additional non-collusion assumption among specific parties. We also introduce a Chinese Remainder Theorem (CRT)-based batching technique for parallel mPSI, achieving near-linear communication savings by compressing multiple OKVS structures. This method generally trades higher computational costs (from polynomial operations and CRT) for communication efficiency, but it is highly effective when communication is paramount or when batching numerous instances of small item sets, where encoding computations can be competitive. Finally, our implementation and evaluation of the proposed mPSI and mPSI-CA protocols in both LAN and WAN settings demonstrate their practical advantages. For instance, in the LAN setting depicted (15 parties, $t=7, m=2^{20}$ ), our mPSI protocol is $3.0\times $ faster and uses $2.5\times $ less communication than Nevo et al. (CCS 2021). Against the approach of Gao et al. (CCS 2024), our maliciously secure protocol is $1.4\times $ faster with comparable communication overhead under weaker assumptions.

Keywords:

Private set intersection

secure multiparty computation

malicious adversarial model

symmetric-key cryptography

secret sharing

batch processing

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

Abstract

Journal

Organization

Cited Papers