Paper 2025/412

Decentralized Multi-Authority Functional Encryption with Malicious Authorities from Standard Assumptions

Abstract

We design decentralized multi-authority functional encryption (MAFE) for $\mathsf{P/Poly}$ circuits from minimal assumptions in both the bounded-collusion and fully collusion-resistant models, i.e., from public-key encryption and from functional encryption, respectively. Prior constructions required sub-exponentially hard public-key encryption with random oracles (bounded collusion) or sub-exponentially-hard obfuscation (collusion-resistant). Under the additional assumption of SXDH or LWE, our constructions remain secure against an adversary that corrupts any $k$ of the $n$ local authorities, provided $\binom{n}{k} = \mathsf{poly}(\lambda)$, covering, for example, $k = O(1)$ and $n = \mathsf{poly}(\lambda)$ or $k = O(\log \lambda)$ and $n = O(\log \lambda)$. Complementing this, we show that any MAFE scheme that tolerates corruption of more than $\chi = O(\log \lambda)$ authorities and remains non-trivially compact (i.e., parameter sizes scale sub-linearly in $2^{\chi}$) implies indistinguishability obfuscation. Thus, our scheme is essentially optimal across a wide parameter regime. Along the way, we introduce two abstractions, MAFE with $\textit{synchronous setup}$ and $\textit{synchronous key generation} $ that provide a path to constructing multi-authority encryption schemes from their centralized counterparts, and may be useful for designing other multi-authority encryption systems.

Note: Prior version included an incorrect result about multi-authority attribute-based encryption.