Efficient Private Set Intersection Based on Functional Encryption

Private Set Intersection (PSI) is a protocol that allows two parties (sender and receiver) to communicate and calculate the intersection of their sets without revealing any other information about their sets. In a typical case, PSI protocol runs on the unbalanced setting where the size of one party's set far exceeds that of the other. In this paper, we focus on the scenario of the receiver having a more extensive set with more substantial arithmetic power, which is essential in disease close contact tracing. In contrast, most of the current work focuses on the opposite scenario. We propose a PSI protocol that can compute efficiently in the unbalanced setting, and the communication only increases with the size of the smaller set owned by the sender. Specifically, to implement the PSI protocol, we construct a functional encryption scheme for the equivalence testing function. Then use cuckoo hash to optimize the comparison operation between elements. The benchmarks show that the PSI protocol takes 46 seconds and 20MB communication cost to compute the intersection with 16 million elements in the receiver's set and 5,000 elements in the sender's set. It achieves 1.93 × reduction in communication cost and 2.57 × reduction in computation cost compared to prior work.