Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF
Yaxi Yang, Xiaojian Liang, Xiangfu Song, Ye Dong, Linting Huang, Hong‐Yu Ren, Changyu Dong, Jianying Zhou · Proceedings on Privacy Enhancing Technologies · 2025
Circuit Private Set Intersection (Circuit-PSI) allows two parties to compute a function f on items in the intersection of their input sets without revealing items in the intersection set. It is a well-known variant of PSI and has numerous practical applications. However, existing Circuit-PSI protocols only provide security against semi-honest adversaries. A straightforward approach to constructing a maliciously secure Circuit-PSI is to extend a pure garbled-circuit-based PSI (NDSS'12) to a maliciously secure circuit-PSI, but it will not be concretely efficient. Another is converting state-of-the-art semi-honest Circuit-PSI protocols (EUROCRYPT'21; PoPETS'22) to be secure in the malicious setting. However, it will come across the consistency issue (EUROCRYPT'11) since parties can not guarantee the inputs of the function f stay unchanged as obtained from the last step. This paper tackles the previously mentioned issue by presenting the first maliciously secure Circuit-PSI protocol. Our key innovation, the Distributed Dual-key Oblivious Pseudorandom Function (DDOPRF), enables the oblivious evaluation of secret-shared inputs using dual keys within the SPDZ MPC framework. Notably, this construction seamlessly ensures fairness within the Circuit-PSI. Compared to the state-of-the-art semi-honest Circuit-PSI protocol (PoPETS'22), experimental results demonstrate that our malicious Circuit-PSI protocol not only reduces around 5x communication costs but also enhances efficiency, particularly for modest input sets (<= 2^{14}) in the case of the WAN setting with high latency and limited bandwidth.