Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF
Authors: Yaxi Yang (Singapore University of Technology and Design), Xiaojian Liang (Ant International), Xiangfu Song (National University of Singapore & Guangzhou University), Ye Dong (Singapore University of Technology and Design), Linting Huang (Guangzhou University), Hongyu Ren (Guangzhou University), Changyu Dong (Guangzhou University), Jianying Zhou (Singapore University of Technology and Design)
Volume: 2025
Issue: 2
Pages: 680–696
DOI: https://doi.org/10.56553/popets-2025-0082
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 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.
Keywords: private set intersection, secure multiparty computation, oblivious pseudorandom function, malicious, secret sharing
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
