Paper 2020/1154

Functional Encryption for Set Intersection in the Multi-Client Setting

Kwangsu Lee and Minhye Seo

Abstract

Functional encryption for set intersection (FE-SI) in the multi-client environment is that each client $i$ encrypts a set $X_i$ associated with time $T$ by using its own encryption key and uploads it to a cloud server, and then the cloud server which receives a function key of the client indexes $i, j$ from a trusted center can compute the intersection $X_i \cap X_j$ of the two client ciphertexts. In this paper, we first newly define the concept of FE-SI suitable for the multi-client setting. Then, we propose an efficient FE-SI scheme in asymmetric bilinear groups and prove the static security of our scheme under newly introduced assumptions. In our FE-SI scheme, a ciphertext consists of $O(\ell)$ group elements, a function key consists of a single group element, and the decryption algorithm has $O(\ell^2)$ complexity where $\ell$ is the size of a set in the ciphertext. Next, we propose another FE-SI scheme with time-constrained keys that limits the ability of function keys to be valid only for a specified time period $T$, and proves the static security of our scheme. Finally, we prove that the two assumptions hold in the general group model to provide confidence in the two newly introduced assumptions.