International Association
for Cryptologic Research

Multi-Authority Functional Encryption (MAFE) [\textit{Chase, TCC'07; Lewko-Waters, Eurocrypt'11; Brakerski et al., ITCS'17}] is a popular generalization of functional encryption (FE) with the central goal of decentralizing the trust assumption from a single central trusted key authority to a group of multiple, \emph{independent and non-interacting}, key authorities. Over the last several decades, we have seen tremendous advances in new designs and constructions for FE supporting different function classes, from a variety of assumptions and with varying levels of security. Unfortunately, the same has not been replicated in the multi-authority setting. The current scope of MAFE designs is rather limited, with positive results only known for certain attribute-based functionalities or from general-purpose code obfuscation. This state-of-the-art in MAFE could be explained in part by the implication provided by Brakerski et al. (ITCS'17). It was shown that a general-purpose obfuscation scheme can be designed from any MAFE scheme for circuits, even if the MAFE scheme is secure only in a bounded-collusion model, where at most \emph{two} keys per authority get corrupted. In this work, we revisit the problem of MAFE and show that existing implication from MAFE to obfuscation is not tight. We provide new methods to design MAFE for circuits from simple and minimal cryptographic assumptions. Our main contributions are summarized below- \begin{enumerate} \item We design a $\poly(\lambda)$-authority MAFE for circuits in the bounded-collusion model. Under the existence of public-key encryption, we prove it to be statically simulation-secure. Further, if we assume sub-exponential security of public-key encryption, then we prove it to be adaptively simulation-secure in the Random Oracle Model. \item We design a $O(1)$-authority MAFE for circuits in the bounded-collusion model. Under the existence of 2-party or 3-party non-interactive key exchange and public-key encryption, we prove it to be adaptively simulation-secure. \item We provide a new generic bootstrapping compiler for MAFE for general circuits to design a simulation-secure $(n_1 + n_2)$-authority MAFE from any two $n_1$-authority and $n_2$-authority MAFE. \end{enumerate}