Paper 2022/772

Maliciously Secure Multi-Party PSI with Lower Bandwidth and Faster Computation

Zhi Qiu, Shanghai Jiao Tong University
Kang Yang, State Key Laboratory of Cryptology
Yu Yu, Shanghai Jiao Tong University
Lijing Zhou, Huawei Technology
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ICICS 2022
Keywords
Multi-party PSI malicious adversaries dishonest majority
Contact author(s)
chonps @ sjtu edu cn
yangk @ sklc org
yuyuathk @ gmail com
zhoulijing @ huawei com
History
2022-06-20: revised
2022-06-15: received
See all versions
Short URL
https://ia.cr/2022/772
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/772,
      author = {Zhi Qiu and Kang Yang and Yu Yu and Lijing Zhou},
      title = {Maliciously Secure Multi-Party PSI with Lower Bandwidth and Faster Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/772},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/772}},
      url = {https://eprint.iacr.org/2022/772}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.