Paper 2017/943

When does Functional Encryption Imply Obfuscation?

Sanjam Garg, Mohammad Mahmoody, and Ameer Mohammed


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.

Available format(s)
Publication info
Published by the IACR in TCC 2017
Blackbox separationsFunctional EncryptionIndistinguishability Obfuscation
Contact author(s)
sanjamg @ berkeley edu
mahmoody @ gmail com
am8zv @ virginia edu
2017-09-27: received
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Mohammad Mahmoody and Ameer Mohammed},
      title = {When does Functional Encryption Imply Obfuscation?},
      howpublished = {Cryptology ePrint Archive, Paper 2017/943},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.