Two-Client and Multi-client Functional Encryption for Set Intersection

We propose several functional encryption schemes for set intersection and variants on two or multiple sets. In these schemes, a party may learn the set intersection from the sets of two or more clients, without having to learn the plaintext set of each individual client. For the case of two clients, we construct efficient schemes for determining the set intersection and the cardinality of the intersection. To evaluate the cardinality of the intersection, no overhead is incurred when compared to operating on plaintext data. We also present other functionalities with a scheme for set intersection with data transfer and a threshold scheme that only discloses the intersection if both clients have at least t elements in common. Finally, we consider set intersection and set intersection cardinality schemes for the case of three or more clients from a theoretical perspective. Our proof-of-concept implementations show that the two-client constructions are efficient and scale linearly in the set sizes