FastPSC: A Fast and Maliciously Secure Set Computation Service for Multi-Owner Set Data

The field of privacy-preserving computation has recently seen a surge in specialized methods for Private Set Intersection (PSI) and Private Set Union (PSU). The primary focus of existing research lies in the multi-party setting, where set owners collaboratively execute PSI/PSU protocols on their sets. Limited research has investigated the more scalable outsourced service setting, where set owners secretly share their sets among a set of servers that collaboratively provide PSI/PSU query services over the secret-shared data. In this paper, we present FastPSC, a new system design supporting maliciously secure PSI/PSU in the outsourced service setting. FastPSC delicately bridges lightweight secure computation techniques and differential privacy mechanisms. The key insight is to leverage differentially private leakage to achieve a significant efficiency boost in secure and accurate intersection and union query services. Experiments show that with differentially private leakage allowed, FastPSC can achieve a significant performance advantage over the-state-of-the-art prior works without differentially private leakage. Specifically, compared with the work by Mohassel et al. (CCS'20) with semi-honest security, FastPSC achieves a 1.5×-52.2× speedup and reduces server-side communication cost by 78%-98%. Compared with the work by Asharov et al. (CCS'23) with malicious security, FastPSC achieves a 4.2×-7.4× speedup and reduces server-side communication cost by 99%.