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.

We present an efficient and simple multi-party private set intersection cardinality (PSI-CA) protocol that allows several parties to learn the intersection size of their private sets without revealing any other information. Our protocol is highly efficient because it only utilizes the Oblivious Key-Value Store and zero-sharing techniques, without incorporating components such as OPPRF (Oblivious Programmable Pseudorandom Function) which is the main building block of multi-party PSI-CA protocol by Gao et al. (PoPETs 2024). Our protocol exhibits better communication and computational overhead than the state-ofthe-art. To compute the intersection between 16 parties with a set size of 220each, our PSI-CA protocol only takes 5.84 seconds and 326.6 MiB of total communication, which yields a reduction in communication by a factor of up to 2.4× compared to the state-of-the-art multi-party PSI-CA protocol of Gao et al. (PoPETs 2024). We prove that our protocol is secure in the presence of a semi-honest adversary who may passively corrupt any (t−2)-out-of-t parties once two specific participants are non-colluding.