Unbalanced PSI from Client-Independent Relaxed Oblivious PRF
Authors: Xiaodong Wang (Tsinghua University & Beijing Institute of Mathematical Sciences and Applications), Zijie Lu (Beijing Institute of Mathematical Sciences and Applications), Bei Liang (Beijing Institute of Mathematical Sciences and Applications), Shengzhe Meng (Tsinghua University & Beijing Institute of Mathematical Sciences and Applications)
Volume: 2025
Issue: 3
Pages: 475–493
DOI: https://doi.org/10.56553/popets-2025-0109
Abstract: Private Set Intersection (PSI) enables parties to compute the intersection of their input sets while preserving privacy. While most PSI protocols are designed for balanced scenarios with sets of similar sizes, unbalanced PSI addresses situations where a server with a large database (e.g., millions of records) performs PSI with multiple clients, each with a set of only a few hundred elements. In this scenario, it is desirable for the server's computation on its large set to be performed offline and reusable, which we refer to as the "Client-Independent" property. However, existing offline/online unbalanced PSI protocols rely on less efficient OPRF constructions, which involve either computationally expensive exponential operations or communication-intensive garbled circuits.
In this work, we present a framework for offline/online unbalanced PSI, with its core component being a novel functionality called "Client-Independent Relaxed OPRF" (ci-rOPRF). The key insight behind ci-rOPRF is to capture the requirements for OPRF in offline/online scenarios. To realize this functionality, we propose two constructions of ci-rOPRF, inspired by the top-performing CM-OPRF (CRYPTO '20) and VOLE-OPRF (EUROCRYPT '21), respectively. Leveraging these efficient ci-rOPRF constructions, we design highly efficient offline/online unbalanced PSI protocols. Furthermore, we extend this framework with two enhancements: one supports set updates, while the other reduces offline communication costs.
Our C++ implementation demonstrates highly efficient performance. For instance, in the online phase, our fastest unbalanced PSI protocol computes the intersection of a client set with 2^12 elements and a server set with 2^28 elements in just 0.55 seconds and 0.62 MiB of communication on a 100 Mbps WiFi connection. Comparisons with state-of-the-art unbalanced PSI protocols show that our protocols significantly outperform existing solutions in the semi-honest model on most metrics.
Keywords: unbalanced PSI, OPRF, secure multiparty computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
