Paper 2026/1358

PSOs as fast as PSI: Efficient Private Set Operations from Batch Homomorphic OKVS Decoding

Abstract

Private set operations (PSOs) let two parties compute set-theoretic functionalities on private inputs while revealing nothing beyond the prescribed output. While private set intersection (PSI) has become highly efficient, many other PSOs remain significantly more expensive. The most effective general framework for such tasks is based on reverse private membership test (RPMT), but even state-of-the-art RPMT constructions rely on heavy elliptic-curve-based primitives. In this work, we propose a substantially faster RPMT protocol by replacing the elliptic-curve core with RLWE-based one. Our starting point is the Oblivious Key-Value Store (OKVS) based RPMT framework, whose direct adaptation to RLWE is obstructed by the batching structure of RLWE encryption. To address this, we introduce a batching-friendly variant of OKVS together with a homomorphic batched decoding procedure. We believe that this batching-friendly OKVS and its homomorphic decoding process may be of independent interest. For a set size $2^{20}$, our RPMT-based PSO protocols take only about $3$ seconds over LAN network and $120$-$138$MB communication, whose running time is comparable to state-of-the-art PSI. Compared to state-of-the-art PSI-Cardinality and PSI-Card-SUM, this is up to \(13.0\times\) speedups. Compared to state-of-the-art PSU, this is up to \(3.0\times\) smaller communication while achieving comparable computational cost, which results in up to $3.9\times$ faster running time over WAN.