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

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ICICS 2022
Multi-party PSI malicious adversaries dishonest majority
Contact author(s)
chonps @ sjtu edu cn
yangk @ sklc org
yuyuathk @ gmail com
zhoulijing @ huawei com
2022-06-20: revised
2022-06-15: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.