Paper 2024/1560

Private Set Operations from Circuit-Based PSI

Abstract

Private set operations~(PSOs) have been extensively studied due to their wide range of applications. In many practical scenarios, it is essential to perform advanced computations on the set operation result while maintaining the security. However, existing PSO protocols for advanced computations often suffer from the during-execution leakage, allowing an adversary to extract additional information beyond the final operation result. In this paper, we propose a novel framework for constructing PSO protocols by leveraging circuit-based private set intersection~(circuit-PSI) in a black-box manner, enabling a range of advanced operations on the set intersection result while mitigating information leakage. Specifically, we present PSI variants, including PSI-Sum, which computes the sum of associated values; PSI-Card, which determines the cardinality of the intersection; PSI-Threshold, which evaluates whether the intersection cardinality exceeds a given threshold; and PSI-InnerProd, which computes the inner product of vectors associated with the intersection. We also provide a private set union~(PSU) protocol based on circuit-PSI without the during-execution leakage. To evaluate the efficiency of our proposed protocols, we provide implementation results of ours and existing PSO protocols closely related to our work. The experimental results demonstrate that our proposed protocols achieve performance comparable to state-of-the-art methods, while resolving the during-execution leakage that the state-of-the-art methods suffer from. Furthermore, as a unique feature of our proposals, our protocols can significantly reduce the online protocol execution time by separating time-consuming setup phase, which comes from the preprocessing optimization of circuit-PSI. In terms of online execution time, PSI-Card and PSI-Sum show a 9.92--13$\times$ improvement over prior work, while PSU achieves a 4.8--5.2$\times$ speedup. Additionally, PSI-InnerProd demonstrates a remarkable 47--56$\times$ speedup over the previous result over a LAN network environment.