Paper 2026/1537

UM-PSO: A Unified Multi-Party Framework for Private Set Operations with Malicious-Majority Security

Abstract

Private Set Operations (PSO) enable mutually untrusted parties to securely compute arbitrary functions (e.g., union, intersection, and cardinality) over their private input sets, which have wide applications in many real-world scenarios. Existing PSO protocols fall short of practical deployment for several reasons. (1) \textit{Function-specific}. Real-world privacy-preserving applications often require multiple set operations within the same task, while existing solutions typically address individual functionalities (e.g., intersection or union) in isolation, making it difficult and costly to support diverse set operations in a unified and efficient manner. (2) \textit{Lacking malicious security}. As PSO is commonly employed in highly sensitive applications, it is often necessary to provide strong adversarial guarantees with malicious security. Unfortunately, most of existing works only achieve semi-honest security, which limits their practical applicability. (3) \textit{Restricted settings}. Majority of existing works focus exclusively on the two-party setting. How to extend them to the multi-party setting with malicious majority securely and efficiently is unclear. To date, designing a maliciously secure multi-party PSO (mPSO) framework that efficiently supports diverse set operations remains an open challenge. This paper presents the \textit{first} maliciously secure mPSO framework, named UM-PSO, that supports a broad range of set operations with practical efficiency. At the core of our framework is a function-independent preprocessing phase that prepares a reusable pool of secret-shared items, which can then be leveraged to securely compute diverse set functionalities in the online phase. To achieve malicious security efficiently, we design verification mechanisms on top of SPDZ-based authenticated secret sharing, along with tailored techniques and optimizations to further improve practical performance. We implement our protocols and report concrete performance results. For a representative setting with 5 parties and a total of $2^{12}$ 128-bit items, our framework achieves an online running time of $0.627$ seconds and incurs $3.35$ MB of communication. Compared to the baselines, our framework achieves up to $51\times$ speedup and $76\times$ lower communication cost.