Paper 2026/1721

Efficient Private Set Union from Multi-Query Oblivious Membership Transfer

Abstract

Private Set Union (PSU) allows two parties to compute the union of their private sets while revealing nothing beyond the union. Existing PSU protocols mainly follow two paradigms: reverse private membership test (RPMT) and invertible Bloom lookup table (IBLT). IBLT-based protocols achieve linear complexity using lightweight symmetric-key operations and offer excellent concrete efficiency. RPMT, on the other hand, provides a more general membership-testing functionality that can serve as a reusable building block for PSU and other private-set computations. However, existing RPMT-based protocols either rely on costly building blocks, such as public-key operations and generic secure two-party computation, or incur super-linear complexity. This raises a natural question: can the generality of the RPMT paradigm be retained while matching the asymptotic and concrete efficiency of IBLT-based PSU? In this work, we answer this question affirmatively by introducing a lightweight mechanism for multi-query membership testing. Our mechanism yields a concretely efficient multi-query RPMT (mqRPMT) protocol that is useful beyond PSU and may be of independent interest. Building on this protocol, we construct a PSU protocol with linear computation and communication complexity. Our construction avoids expensive public-key operations and generic secure two-party computation, relying instead on efficient symmetric-key primitives. We extensively evaluate our protocol against state-of-the-art PSU protocols from both the RPMT and IBLT paradigms. Compared with the leading RPMT-based PSU protocol from PKC 2024, our construction is $41.7\times$ $-$ $48.9\times$ faster in the LAN setting and up to $4.5\times$ faster in WAN settings. Compared with the leading IBLT-based PSU protocol from EUROCRYPT 2026, our protocol achieves competitive and, in several metrics, superior performance: it is $1.9\times$ $-$ $2.5\times$ faster in LAN settings and reduces communication by up to $1.4\times$. These results demonstrate that the broader applicability of the RPMT abstraction need not come at the cost of asymptotic or concrete efficiency.