Cryptology ePrint Archive: Report 2017/943

When does Functional Encryption Imply Obfuscation?

Sanjam Garg and 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.

Category / Keywords: Blackbox separations, Functional Encryption, Indistinguishability Obfuscation

Original Publication (in the same form): IACR-TCC-2017

Date: received 25 Sep 2017

Contact author: mahmoody at gmail com, sanjamg@berkeley edu, am8zv@virginia edu

Available format(s): PDF | BibTeX Citation

Version: 20170927:140416 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]