A Practical Multiparty Private Set Intersection Protocol Based on Bloom Filters for Unbalanced Scenarios

Abstract

Multiparty Private Set Intersection (MPSI) is dedicated to finding the intersection of datasets of multiple participants without disclosing any other information. Although many MPSI protocols have been presented, there are still some important practical scenarios that require in-depth consideration such as an unbalanced scenario, where the server’s dataset is much larger than the clients’ datasets, and in cases where the number of participants is large. This paper proposes a practical MPSI protocol for unbalanced scenarios. The protocol uses the Bloom filter, an efficient data structure, and the ElGamal encryption algorithm to reduce the computation of clients and the server; adopts randomization technology to solve the encryption problem of the 0s in the Bloom filter; and introduces the idea of the Shamir threshold secret-sharing scheme to adapt to multiple environments. A formal security proof and three detailed experiments are given. The results of the experiments showed that the new protocol is very suitable for unbalanced scenarios with a large number of participants, and it has a significant improvement in efficiency compared with the typical related protocol (TIFS 2022).

Keywords

• Multiparty Private Set Intersection
• unbalanced scenario
• ElGamal cryptography
• Shamir threshold key-sharing scheme
• Bloom filter