TY - GEN
T1 - Maliciously Secure Multi-party PSI with Lower Bandwidth and Faster Computation
AU - Qiu, Zhi
AU - Yang, Kang
AU - Yu, Yu
AU - Zhou, Lijing
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - 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ℓ| F| ) bits for the central party P0 due to the star architecture, where n is the number of parties, ℓ is the size of each set and | F| is the size of an exponentially large field F. When n and ℓ 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 P0 from O(nℓ| F| ) bits to O(ℓ| F| ) bits using a tree architecture. Furthermore, our PSI protocol reduces the expensive LPN encoding operations performed by P0 by a factor of n as well as the computational cost by 2 nℓ 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.
AB - 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ℓ| F| ) bits for the central party P0 due to the star architecture, where n is the number of parties, ℓ is the size of each set and | F| is the size of an exponentially large field F. When n and ℓ 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 P0 from O(nℓ| F| ) bits to O(ℓ| F| ) bits using a tree architecture. Furthermore, our PSI protocol reduces the expensive LPN encoding operations performed by P0 by a factor of n as well as the computational cost by 2 nℓ 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.
UR - https://www.scopus.com/pages/publications/85137019704
U2 - 10.1007/978-3-031-15777-6_5
DO - 10.1007/978-3-031-15777-6_5
M3 - 会议稿件
AN - SCOPUS:85137019704
SN - 9783031157769
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 69
EP - 88
BT - Information and Communications Security - 24th International Conference, ICICS 2022, Proceedings
A2 - Alcaraz, Cristina
A2 - Chen, Liqun
A2 - Li, Shujun
A2 - Samarati, Pierangela
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Conference on Information and Communications Security, ICICS 2022
Y2 - 5 September 2022 through 8 September 2022
ER -