Welcome to the resource topic for 2022/157
Title:
Shuffle-based Private Set Union: Faster and More Secure
Authors: Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Jiajun Du, Dawu Gu
Abstract:Private Set Union (\mathsf{PSU}) allows two players, the sender and the receiver, to compute the union of their input datasets without 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 \mathsf{PSU} protocols for the first time. By shuffling receiver’s set, we put forward the first protocol, denoted as \Pi_{\mathsf{PSU}}^{\mathsf{receiver}}, 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_{\mathsf{PSU}}^{\mathsf{sender}}, 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_{\mathsf{PSU}}^{\mathsf{receiver}} and \Pi_{\mathsf{PSU}}^{\mathsf{sender}} 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 \times improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.
ePrint: https://eprint.iacr.org/2022/157
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .