Review the Cuckoo Hash-Based Unbalanced Private Set Union: Leakage, Fix, and Optimization

A Private Set Union (PSU) protocol involves two participants-the sender and receiver-computing the union of their privately held sets, X and Y, and outputs 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. In this paper, we reassess Tu et al.’s protocol and present a statistical and computational leakage attack targeting their Hash + RPMT framework. We estimate the lower bound of our attack’s success probability and highlight how Tu’s parameter choices lead to leaks. 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), which eliminates one permutation round at no extra cost.