Paper 2025/025

Chosen-Ciphertext Security for Functional Encryption with Multiple Users: Definitions and Generic Concrete Constructions

Abstract

Functional Encryption (FE) is a powerful cryptographic primitive that allows for fine- grained computation over encrypted data. In the age of modern computing in complex environments, where data comes from multiple independent sources to be later jointly analysed in a fine-grained computation manner, the notion of multi-user functional encryption is becoming increasingly important. In particular, since their introduction (Goldwasser et al. at Eurocrypt’14; Chotard et al. at Asiacrypt’18), Multi-Client and Multi-Input FE become the subjects of a plethora of works, which study on concrete function classes, improving security, and more. Among many properties, one of the most important security property for Multi-Client/Multi-Input FE is the confidentiality of users’ encrypted data. Due to the complexity of these primitives, modeling a strong security notion and at the same time providing efficient constructions is a challenging task. However, all security notions considered so far for Multi-Client/Multi-Input FE are in the chosen- plaintext setting, whereas it is long settled that the chosen-ciphertext setting is the most relevant for practical security in classical public-key encryption. For FE, the only known works are on single-user context, namely by Benhamouda et al. (PKC’17), Gay (PKC’20), Castagnos et al. (TCS’22). This leaves open the questions, both conceptually and constructively, of attaining chosen-ciphertext security in the multi-user setting, notably for Multi-Client and Multi-Input FE. This work tackles the above questions of chosen-ciphertext security in multi-user context for FE for the first time: - We propose a new security notion for Multi-Client FE, and Multi-Input FE, in the chosen- ciphertext setting. Our notions extend the single-user notion that is studied in previous works and is robust against strong adversaries. - For the class computing inner products, we demonstrate the feasibility of our new notions by providing nouvel generic constructions for Multi-Client FE and Multi-Input FE. Surprisingly, our contruction for Multi-Input FE attains the same efficiency as in the public key single-client setting of previous works, and can be instantiated from the Decisional Diffie-Hellman or Decision Composite Residuosity assumptions. On the other hand, our contruction for Multi-Client FE enjoys an orignal toolkit of techniques that is developed to bootstrap a MCFE with chosen- plaintext security to chosen-ciphertext security, in its secret key setting, and can be instantiated from Symmetric eXternal Diffie-Hellman and Decision Linear assumptions.

Note: Fixed typos in title ; Updates in related works ; (February 21, 2025) Extended abstract, reorganized overviews