Paper 2024/789

Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF

Abstract

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 \textit{semi-honest} adversaries. A straightforward approach to constructing a maliciously secure Circuit-PSI is to extend a pure garbled-circuit-based PSI (NDSS'12 \cite{huang2012private}) 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 \cite{rindal2021vole}; PoPETS'22 \cite{chandran2022circuit}) to be secure in the malicious setting. However, it will come across \textit{the consistency issue} (EUROCRYPT'11 \cite{shelat2011two}) 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 $5$x communication costs but also enhances efficiency, particularly for modest input sets ($\le 2^{14}$) in the case of the WAN setting with high latency and limited bandwidth.