Paper 2025/164

Multi-Authority Functional Encryption with Bounded Collusions from Standard Assumptions

Rishab Goyal, University of Wisconsin-Madison
Saikumar Yadugiri, University of Wisconsin-Madison
Abstract

Multi-Authority Functional Encryption ($\mathsf{MA}$-$\mathsf{FE}$) [Chase, TCC'07; Lewko-Waters, Eurocrypt'11; Brakerski et al., ITCS'17] is a popular generalization of functional encryption ($\mathsf{FE}$) with the central goal of decentralizing the trust assumption from a single central trusted key authority to a group of multiple, independent and non-interacting, key authorities. Over the last several decades, we have seen tremendous advances in new designs and constructions for $\mathsf{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 $\mathsf{MA}$-$\mathsf{FE}$ designs is rather limited, with positive results only known for (all-or-nothing) attribute-based functionalities, or need full power of general-purpose code obfuscation. This state-of-the-art in $\mathsf{MA}$-$\mathsf{FE}$ 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 $\mathsf{MA}$-$\mathsf{FE}$ scheme for circuits, even if the $\mathsf{MA}$-$\mathsf{FE}$ scheme is secure only in a bounded-collusion model, where at most two keys per authority get corrupted. In this work, we revisit the problem of $\mathsf{MA}$-$\mathsf{FE}$, and show that existing implication from $\mathsf{MA}$-$\mathsf{FE}$ to obfuscation is not tight. We provide new methods to design $\mathsf{MA}$-$\mathsf{FE}$ for circuits from simple and minimal cryptographic assumptions. Our main contributions are summarized below 1. We design a $\mathsf{poly}(\lambda)$-authority $\mathsf{MA}$-$\mathsf{FE}$ 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. 2. We design a $O(1)$-authority $\mathsf{MA}$-$\mathsf{FE}$ for circuits in the bounded-collusion model. Under the existence of 2/3-party non-interactive key exchange, we prove it to be adaptively simulation-secure. 3. We provide a new generic bootstrapping compiler for $\mathsf{MA}$-$\mathsf{FE}$ for general circuits to design a simulation-secure $(n_1 + n_2)$-authority $\mathsf{MA}$-$\mathsf{FE}$ from any two $n_1$-authority and $n_2$-authority $\mathsf{MA}$-$\mathsf{FE}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2024
DOI
10.1007/978-3-031-78020-2_1
Keywords
Functional EncryptionMulti-AuthorityEncryption
Contact author(s)
rishab @ cs wisc edu
saikumar @ cs wisc edu
History
2025-02-05: approved
2025-02-04: received
See all versions
Short URL
https://ia.cr/2025/164
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/164,
      author = {Rishab Goyal and Saikumar Yadugiri},
      title = {Multi-Authority Functional Encryption with Bounded Collusions from Standard Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/164},
      year = {2025},
      doi = {10.1007/978-3-031-78020-2_1},
      url = {https://eprint.iacr.org/2025/164}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.