Efficient Unbalanced Private Set Intersection Protocol over Large-Scale Datasets Based on Bloom Filter

Private set intersection (PSI) is a special case of secure multiparty computation where participants can securely get their intersection without leaking additional information. Although many protocols have been proposed in recent years, they are still slightly inefficient when facing large-scale datasets in an unbalanced scenario. Client's running time of most PSI protocols is related to Server's set size, and it's very large when Client has a small set but Server has a large-scale set. In the paper, we propose an efficient unbalanced PSI protocol over large-scale datasets in the semi-honest model. By properly using the encrypted Bloom filter, randomized technique and multiply homomorphism of ElGamal cryptography, Client can get the intersection correctly and his running time is only linear with his set size and is independent of Server's set size. Thus, our protocol has a lightweight Client and performs better than other protocols when Server has a large-scale dataset. We also give a detailed experimental analysis with other related protocols, which shows our protocol is more efficient than others.