Paper 2021/1011

A Fast and Flexible Multi-Client Functional Encryption for Set Intersection

Mojtaba Rafiee

Abstract

A Multi-Client Functional Encryption (MCFE) scheme for set intersection is a cryptographic primitive that enables an evaluator to learn the intersection from all sets of a pre-determined number of clients, without need to learn the plaintext set of each individual client. In this paper, we propose a flexible version of the MCFE schemes for the set intersection, called Flexible Multi-Client Functional Encryption for Set Intersection (FMCFE). In our FMCFE scheme, the evaluator can learn the intersection from any flexible choice of sets (instead of all sets). In this regard, we redefine syntax and security notions of the MCFE schemes for the FMCFE schemes. In the literature, solving multi-client set intersection problem in polynomial time, such that only the intersection result is revealed (without additional information), is an open problem. In this paper, we propose a relaxed solution using FMCFE schemes to solve secure set intersection in polynomial time. We analyze that for practical use of secure multi-client set intersection, this relaxation is necessary. We also show that our scheme has the adaptive indistinguishability-based security under passive corruption. Our proof relies on the Symmetric eXternal Diffie-Hellman (SXDH) assumption in the standard model.