Two-client and multi-client functional encryption for set intersection (Q2183919)

In this paper, the authors propose several functional encryption schemes for set intersection and variants on two or multiple sets. In functional encryption (FE) schemes, decryption keys are associated with a functionality \(f\) and the decryption of an encrypted message \(m\) returns the image \(f(m)\), instead of the original message \(m\). More in general, in multi-client functional encryption (MC-FE) schemes, decryption keys are associated with an \(n\)-ary function \(f\) and the output of the decryption is \(f(x_1,\ldots, x_n)\) corresponding to \(n\) encrypted values \(x_1, \ldots , x_n\). More precisely, the inputs for the \(n\)-ary function \(f\) are given by \(n\) distinct parties, named clients. Each client encrypts their input using their own encryption key and a session identifier. Another party, named evaluator, having a decryption key and receiving these encrypted sets, can evaluate an \(n\)-ary set operation \(f\) over the clients' inputs. To evaluate a function \(f\) using the corresponding decryption key, all the inputs of \(f\) need to be associated with the same identifier or otherwise decryption will fail. Starting from the formal definition of Multi-client Functional Encryption for Set Operations, the authors propose the following four two-client functional encryption schemes, two of which are generalized to the multi-client case, and prove their security under the decisional Diffie Hellman (DDH) assumption, using the indistinguishability-based security notion for MC-FE from Sect. 3.2 in [\textit{S. Goldwasser} et al., Lect. Notes Comput. Sci. 8441, 578--602 (2014; Zbl 1327.94048)]. Two-client set intersection cardinality. The two clients encrypt each set element individually using a pseudorandom function (PRF) under the same key. Since a PRF has a deterministic output, the evaluator can use any algorithm for determining the cardinality of the intersection \(|S_a\cap S_b |\), where \(S_\gamma\) is the set belonging to client \(\gamma\). This scheme is generalized to the multi-client case. Two-client set intersection. The set element is encrypted under a key derived from the message itself and the encryption key is secret shared. If both clients encrypted the same message, the decryption key can be recovered from the secret shares and the ciphertext can be decrypted. To encrypt the set element itself, an authenticated encryption (AE) scheme is used. This scheme is generalized to the multi-client case. Two-client set intersection with data transfer or projection. The two-client set intersection scheme can be extended into a two-client set intersection scheme with data transfer, where the common set elements are shared with associated data (i.e., \(\{ (x_j, \phi_a(x_j), \phi_b(x_j)) \mid x_j \in S_a\cap S_b \}\), where \(\phi_\gamma(x_j)\) is the data associated with \(x_j\) by client \(\gamma\). Instead of only encrypting the set element \(x_j\) itself, it is also possible to choose to encrypt both the element itself and the data associated. The security of the scheme is the same as before since it relies on the security of the AE scheme. Two-client threshold set intersection. This scheme is designed for allowing the evaluator only the set elements in the intersection if the clients have at least \(t\) set elements in common. It can be achieved by encrypting the share of the decryption key for the AE ciphertext using another encryption key. For the entire collection see [Zbl 1428.68026].