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.

Available format(s)
Publication info
Keywords
Blackbox separationsFunctional EncryptionIndistinguishability Obfuscation
Contact author(s)
sanjamg @ berkeley edu
mahmoody @ gmail com
am8zv @ virginia edu
History
Short URL
https://ia.cr/2017/943

CC BY

BibTeX

@misc{cryptoeprint:2017/943,
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{https://eprint.iacr.org/2017/943}},
url = {https://eprint.iacr.org/2017/943}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.