International Association
for Cryptologic Research

Circuit-based Private Set Intersection (circuit-PSI) enables two parties, a client and a server, with their input sets $X$ and $Y$ respectively, to securely compute a function $f$ on the intersection $X \cap Y$, while keeping $X \cap Y$ secret from both parties. Although several computationally efficient circuit-PSI protocols have been proposed recently, they most focus on the balanced scenario where $|X|$ is similar to $|Y|$. However, in many realistic scenarios, a circuit-PSI protocol may be performed in the unbalanced case where $|X|$ is remarkably smaller than $|Y|$ (e.g., the client is a constrained device holding a small set, while the server is a service provider holding a large set). Directly applying existing protocols to this scenario will lead to significant efficiency issues because the communication complexity of the protocols scales at least linearly with the size of the larger set, i.e., $\max(|X|, |Y|)$.

In this work, we put forth efficient constructions for unbalanced circuit-PSI with sublinear communication complexity in the size of the larger set. The main insight is that we formalize unbalanced circuit-PSI as obliviously retrieving values corresponding to keys from a set of key-value pairs. To this end, we present a new functionality called Oblivious Key-Value Retrieval (OKVR) and design the OKVR protocol from a new notion called sparse Oblivious Key-Value Stores (sparse OKVS). We conduct extensive experiments and the results show that our constructions remarkably outperform the state-of-the-art circuit-PSI schemes (EUROCRYPT'19, PETs'22, CCS'22), i.e., $1.84 \sim 48.86 \times$ communication improvement and $1.50 \sim39.81 \times$ faster computation. Very recently, Son and Jeong (AsiaCCS'23) also present unbalanced circuit-PSI protocols, and our constructions outperform them by $1.18 \sim 15.99 \times$ and $1.22 \sim 10.44 \times$ in communication and computation overhead, respectively, depending on set sizes and network environments.