PMPSI: Privacy-Preserving Predicate-Supporting Multi-Party Private Set Intersection

Multi-Party Private Set Intersection (MPSI) protocol allows multiple participants to secretly compute their data intersection without any additional disclosure. However, conventional MPSI protocols treat all participants as identical entities and fail to accommodate the diverse characteristics of participants, which may lead to intersection results that do not align with the requestor's intent. To this end, we introduce a new cryptographic primitive of MPSI, wherein only participants whose attributes satisfy a predicate defined by a designated requestor are eligible to contribute to the intersection computation, termed Predicate-Supporting Multi-party Private Set Intersection (PMPSI). PMPSI enables conditional intersection with strong privacy guarantees. Specifically, PMPSI ensures that the predicate, participant attributes, and match status remain confidential to all entities involved. To instantiate this primitive under the honest-but-curious adversarial model, we design a dual-mode oblivious comparison (DMOC) protocol with two operational versions as a core subroutine and integrate it with threshold homomorphic encryption and encrypted inverse Bloom filter. We formally prove the security of the protocol via simulation-based arguments and implement a prototype to evaluate its efficiency. Experimental results demonstrate that the PMPSI protocol achieves linear computational and communication complexity with respect to the number of participants, confirming its practicality for realistic application scenarios such as secure cross-organizational collaboration and privacy-preserving resource sharing in mobile networks.