Search for: All records

Private Set Union (PSU) protocol allows parties, each hold- ing an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomor- phic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical. To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE- based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our per- formance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage. 

Private Set Union (PSU) allows two players, the sender and the receiver, to compute the union of their input datasets with- out revealing any more information than the result. While it has found numerous applications in practice, not much research has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to design PSU protocols for the first time. By shuffling receiver’s set, we put forward the first protocol, denoted as $$\Pi^R_{PSU}$$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver’s set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.’s design, can be avoided in our design. We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $$\Pi^S_{PSU}$$, by shuffling the sender’s dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender’s input size is much smaller than the receiver’s. Finally, we implement our protocols $$\Pi^R_{PSU}$$ and $$\Pi^S_{PSU}$$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a 4-5X improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings. 

Private Set Union (PSU) allows two players, the sender and the receiver, to compute the union of their input datasets with- out revealing any more information than the result. While it has found numerous applications in practice, not much re- search has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to de- sign PSU protocols for the first time. By shuffling receiver’s set, we put forward the first protocol, denoted as ΠRPSU, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver’s set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.’s design, can be avoided in our design. We further extend our investigation to the application sce- narios in which both players may hold unbalanced input datasets. We propose our second protocol ΠSPSU, by shuffling the sender’s dataset. This design can be viewed as a dual ver- sion of our first protocol, and it is suitable in the cases where the sender’s input size is much smaller than the receiver’s. Finally, we implement our protocols ΠRPSU and ΠSPSU in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a 4-5× improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.