Research Article
Efficient Unbalanced Private Set Intersection Protocol over Large-Scale Datasets Based on Bloom Filter
@INPROCEEDINGS{10.1007/978-3-031-64954-7_15, author={Ou Ruan and Chaohao Ai and Changwang Yan}, title={Efficient Unbalanced Private Set Intersection Protocol over Large-Scale Datasets Based on Bloom Filter}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part II}, proceedings_a={SECURECOMM PART 2}, year={2024}, month={10}, keywords={private set intersection unbalanced scenario large-scale datasets Bloom filter ElGamal cryptography}, doi={10.1007/978-3-031-64954-7_15} }- Ou Ruan
Chaohao Ai
Changwang Yan
Year: 2024
Efficient Unbalanced Private Set Intersection Protocol over Large-Scale Datasets Based on Bloom Filter
SECURECOMM PART 2
Springer
DOI: 10.1007/978-3-031-64954-7_15
Abstract
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.
