A functional encryption (FE) is a versatile encryption, where the functional key \(\textsf{sk}_\textbf{v}\) decrypts a ciphertext to the function \(\textbf{v}(\textbf{m})\) evaluated on the plaintext \(\textbf{m}\). The security requires that even when an adversary colludes multiple functional keys, it learns only the evaluations but nothing more about the plaintext. This work considers the adversary obtaining an unbounded number of colluded keys, a natural setting for many FE applications. We aim to understand which cryptographic primitives are sufficient to construct an unbounded-collusion FE.
This work proves negative results: we separate unbounded-collusion FEs from many encryption primitives that are “all-or-nothing”. Introduced by Garg, Mahmoody and Mohammed (CRYPTO ’17), an all-or-nothing encryption scheme allows an adversary to learn either the whole plaintext if the authorized secret key is given; otherwise, the adversary learns nothing. Hence, we rule out such FE construction from fully homomorphic encryption (FHE), attribute-based encryption (ABE), and predicate encryptions (PE). Our impossibility holds for private-key and selectively secure FEs for an minimal function class, inner products, making the impossibility stronger. Our separation is in the “monolithic model”, similar to the black-box model, but the primitive is allowed to evaluate a circuit that queries the primitive itself as an oracle.
Our result extends the beautiful work of Hajiabadi et al. (TCC ’24), which separated inner-product functional encryption (IPFE) from any primitives that exist in the random oracle model. Our result is perhaps surprising as IPFE was proposed by Abdalla et al. (PKC ’15) to be easier to construct, and indeed there are several IPFEs based on standard algebraic assumptions, such as Decisional Diffie-Hellman or Learning-with-Errors. Moreover, bounded-collusion FEs for all circuits are constructed in a black-box way from minimal assumptions, i.e., public-key FE from public-key encryption, and secret-key FE from one-way functions, by Ananth and Vaikuntanathan (TCC ’19).
