Welcome to the resource topic for 2022/772
Title:
Maliciously Secure Multi-Party PSI with Lower Bandwidth and Faster Computation
Authors: Zhi Qiu, Kang Yang, Yu Yu, and Lijing Zhou
Abstract:Private Set Intersection (PSI) allows a set of mutually distrustful parties, each holds a private data set, to compute the intersection of all sets, such that no information is revealed except for the intersection. The state-of-the-art PSI protocol (Garimella et al., CRYPTO’21) in the multi-party setting tolerating any number of malicious corruptions requires the communication bandwidth of O(n\ell|\mathbb{F}|) bits for the central party P_0 due to the star architecture, where n is the number of parties, \ell is the size of each set and |\mathbb{F}| is the size of an exponentially large field \mathbb{F}. When n and \ell are large, this forms an efficiency bottleneck (especially for networks with restricted bandwidthes). In this paper, we present a new multi-party PSI protocol in dishonest-majority malicious setting, which reduces the communication bandwidth of the central party P_0 from O(n\ell|\mathbb{F}|) bits to O(\ell|\mathbb{F}|) bits using a tree architecture. Furthermore, our PSI protocol reduces the expensive LPN encoding operations performed by P_0 by a factor of n as well as the computational cost by 2n\ell hash operations in total. Additionally, while the multi-party PSI protocol (Garimella et al., CRYPTO’21) with a single output is secure, we present a simple attack against its multi-output extension, which allows an adversary to learn more information on the sets of honest parties beyond the intersection of all sets.
ePrint: https://eprint.iacr.org/2022/772
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 .