Paper 2024/1146
Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions
Abstract
Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of multi-party private set union (MPSU) protocols: The first category builds on public-key techniques, where existing works require a super-linear number of public-key operations, resulting in their poor practical efficiency. The second category builds on oblivious transfer and symmetric-key techniques. The only work in this category, proposed by Liu and Gao (ASIACRYPT 2023), features the best concrete performance among all existing protocols, but still has super-linear computation and communication. Moreover, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice. There remain two significant open problems so far: no MPSU protocol achieves semi-honest security based on oblivious transfer and symmetric-key techniques, and no MPSU protocol achieves both linear computation and linear communication complexity. In this work, we resolve both of them. - We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $3.9-10.0 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $2^{20}$ items each. - We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao. We implement our protocols and conduct an extensive experiment to compare the performance of our protocols and the state-of-the-art. To the best of our knowledge, our code is the first correct and secure implementation of MPSU that reports on large-size experiments.
Note: This paper is also available at https://arxiv.org/abs/2406.07011.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Multi-Party Private Set Union
- Contact author(s)
-
minglang_dong @ mail sdu edu cn
yuchen @ sdu edu cn
zhangcong @ mail tsinghua edu cn
baiyujie @ mail sdu edu cn - History
- 2024-09-08: last of 2 revisions
- 2024-07-15: received
- See all versions
- Short URL
- https://ia.cr/2024/1146
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1146,
author = {Minglang Dong and Yu Chen and Cong Zhang and Yujie Bai},
title = {Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1146},
year = {2024},
url = {https://eprint.iacr.org/2024/1146}
}