A Leakage-Free Framework for Private Set Operations

Private set operations (PSO) enable secure computation over private sets, supporting intersection, union, and related functionalities. Chen et al. (PKC 2024) proposed the first practical PSO framework, but it suffers from duringexecution leakage. Jia et al. (USENIX Security 2024) and Tu et al. (USENIX Security 2025) eliminate during-execution leakage in their PSU protocols, but they both lack support for general PSO functionalities. In this work, we present a leakage-free PSO framework that supports various PSO functionalities. Technically, we first propose a novel primitive called permuted secure equality test (pSEQT) from permutation correlation generator and secure equality test. Then we introduce permuted batch secret-shared private membership test (pbssPMT) by combining pSEQT, oblivious PRF and Oblivious Key-Value Store. Finally, we construct our leakage-free PSO framework by integrating our pbssPMT, together with cuckoo hashing technique and oblivious transfer. Experiments demonstrate that our protocol outperforms when dealing with data sets consisting of millions of elements. Compared to the state-of-the-art general PSO framework (Chen et al., PKC 2024), our pbssPMT-based solution achieves up to 3.43 × speedup in the online phase while eliminating during-execution leakage. Compared with the state-of-the-art leakage-free PSU protocol (Tu et al., USENIX Security 2025), our pbssPMT-based PSU achieves up to 3.97 × online phase speedup while supporting a broader range of PSO functionalities.