Paper 2016/558

From Cryptomania to Obfustopia through Secret-Key Functional Encryption

Nir Bitansky, Ryo Nishimaki, Alain Passelègue, and Daniel Wichs

Abstract

Functional encryption lies at the frontiers of current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (\IO) while other variants have been constructed from standard assumptions such as \LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of \emph{secret-key functional encryption} with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key crypto, but on the other hand, we do no know how to construct it without the heavy hammers in obfustopia. In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia. On the technical side, our result relies on two main components. As our first contribution, we show how to use secret key functional encryption to get ``exponentially-efficient indistinguishability obfuscation'' (\XIO), a notion recently introduced by Lin et al. (PKC '16) as a relaxation of \IO. Lin et al. show how to use \XIO and the \LWE assumption to build \IO. As our second contribution, we improve on this result by replacing its reliance on the \LWE assumption with any plain public-key encryption scheme. Lastly, we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS '15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

Note: Correcting typos and adding some remarks for clarity (08/24/2016). This is the full version of the paper that appears at TCC 2016-B.