Paper 2025/330

(Multi-Input) FE for Randomized Functionalities, Revisited

Abstract

Randomized functional encryption (rFE) generalizes functional encryption (FE) by incorporating randomized functionalities. Randomized multi-input functional encryption (rMIFE) extends rFE to accommodate multi-input randomized functionalities. In this paper, we reassess the framework of rFE/rMIFE enhancing our understanding of this primitive and laying the groundwork for more secure and flexible constructions in this field. Specifically, we make three key contributions: - Stronger IND definition: We show the prevailing indistinguishability-based security definition protects only against malicious decryptors and leaves systems vulnerable to malicious encryptors -- a critical requirement for rFE/rMIFE since their inception. We then propose a refined IND notion that simultaneously handles both threats. - Separating counterexample: Illustrating this definitional gap, we meticulously craft an rFE scheme -- using standard tools (FE, PRF, PKE, simulation‑sound NIZK) -- that satisfies the old definition yet is blatantly insecure in practice (and where this insecurity would be precluded by our enhanced definition). - Adaptive, unbounded‑message rMIFE: The sole, viable prior rMIFE construction by Goldwasser et al. [EUROCRYPT 2014] permits only a fixed message bound per encryption slot and offers merely selective security. Leveraging sub‑exponentially secure indistinguishability obfuscation and techniques of Goyal et al. [ASIACRYPT 2016] built for deterministic MIFE, we give the first rMIFE scheme that supports an unbounded number of messages per slot and attains full adaptive security.