A Private Set Union (PSU) protocol involves two participants –the sender and the receiver–computing the union of their privately held sets, X and Y, and outputting the result to the receiver. PSU protocols are categorized into balanced ( \(|X| \approx |Y|\) ) and unbalanced ( \(|X| \ll |Y|\) or \(|X| \gg |Y|\) ) settings. Tu et al. (CCS 2023) developed the first efficient unbalanced PSU ( \(|X| \ll |Y|\) ) protocol using Cuckoo hashing and a novel permuted Reversed Private Membership Test (p-RPMT) protocol. In this paper, we propose two security models: a statistical non-leaky model and a computational non-leaky model, both of which are stronger than the semi-honest model. We reassess Tu et al.’s protocol and present an attack on the protocol, showing that their solution leaks the sender’s inputs to the receiver. We estimate the lower bound of our attack’s success probability and highlight how Tu’s parameter choices lead to leaks, which can be extended to other protocols using the Hash + RPMT framework. To counter these vulnerabilities, we offer two mitigation strategies with different tradeoffs. Finally, we optimize the p-RPMT protocol by introducing a new shuffled-PMT (s-PMT) under the semi-honest model, which eliminates one permutation round at no extra cost.
