Paper 2017/943

When does Functional Encryption Imply Obfuscation?

Sanjam Garg, Mohammad Mahmoody, and Ameer Mohammed

Abstract

Realizing indistinguishablility obfuscation (IO) based on well-understood computational assumptions is an important open problem. Recently, realizing functional encryption (FE) has emerged as promising directing towards that goal. This is because: (1) compact single-key FE (where the functional secret-key is of length double the ciphertext length) is known to imply IO [Anath and Jain, CRYPTO 2015; Bitansky and Vaikuntanathan, FOCS 2015] and (2) several strong variants of single-key FE are known based on various standard computation assumptions. In this work, we study when FE can be used for obtaining IO. We show any single-key FE for function families with ``short'' enough outputs (specifically the output is less than ciphertext length by a value at least $\omega(n + k)$, where $n$ is the message length and $k$ is the security parameter) is insufficient for IO even when non-black-box use of the underlying FE is allowed to some degree. Namely, our impossibility result holds even if we are allowed to plant FE sub-routines as gates inside the circuits for which functional secret-keys are issued (which is exactly how the known FE to IO constructions work). Complementing our negative result, we show that our condition of ``short'' enough is almost tight. More specifically, we show that any compact single-key FE with functional secret-key output length strictly larger than ciphertext length is sufficient for IO. Furthermore, we show that non-black-box use of the underlying FE is necessary for such a construction, by ruling out any fully black-box construction of IO from FE even with arbitrary long output.