Enhanced private set union from secret-shared private membership test

Abstract

Abstract Private Set Union (PSU) is a critical cryptographic tool, but designing protocols that are efficient and secure against recent threats, such as during-execution leakage, remains a challenge. The dominant approach to avoid such leakage is over Cuckoo hashing paradigm, which has led to increasingly complex designs that require multiple layers of costly cryptographic patches. Furthermore, there has been reported an additional vulnerability that broadly affects Cuckoo hashing based PSU protocols, rendering even these enhanced solutions vulnerable. In this work, we depart from this complex paradigm and introduce a new PSU protocol that is simple, efficient, and secure against known during-execution leakage and hashing-related leakage without relying on Cuckoo Hashing. At the core of our design, we propose a novel and highly efficient construction of secret-shared Private Membership Test (ss-PMT), which is enabled by the use of a modern, Multi-Party Computation (MPC)-friendly Alternating Moduli pseudorandom function (PRF). Our protocol achieves linear complexity, and our implementation outperforms prior state-of-the-art enhanced PSUs (ePSUs) by 6.58 to 6.74x across various set sizes and network settings. Our results show that it is possible to achieve robust security and superior performance in PSU through a fundamentally simpler and more direct design, offering a cleaner blueprint for future private set operations.