Breaking the Sub-Exponential Barrier in Obfustopia.
Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, Mark Zhandry · IACR Cryptology ePrint Archive · 2016
Indistinguishability obfuscation (iO) has emerged as a surprisingly powerful notion. Almost all known cryptographic primitives can be constructed from general purpose iO and other minimalistic assumptions such as one-way functions. The primary challenge in this direction of research is to develop novel techniques for using iO since iO by itself offers virtually no protection to secret information in the underlying programs. When dealing with complex situations, often these techniques have to consider an exponential number of hybrids (usually one per input) in the security proof. This results in a sub-exponential loss in the security reduction. Unfortunately, this scenario is becoming more and more common and appears to be a fundamental barrier to current techniques. In this work, we explore the possibility of getting around this sub-exponential loss barrier in constructions based on iO as well as the weaker notion of functional encryption (FE). Towards this goal, we achieve the following results: 1. We construct trapdoor one-way permutations from polynomially-hard iO (and standard one-way permutations). This improves upon the recent result of Bitansky, Paneth, and Wichs (TCC 2016) which requires iO of sub-exponential strength. 2. We present a different construction of trapdoor one-way permutations based on standard, polynomially-secure, public-key functional encryption. This qualitatively improves upon our first result since FE is a weaker primitive than iO — it can be based on polynomiallyhard assumptions on multi-linear maps whereas iO inherently seems to requires assumptions of sub-exponential strength. 3. We present a construction of universal samplers also based only on polynomially-secure public-key FE . Universal samplers, introduced in the work of Hofheinz, Jager, Khurana, Sahai, Waters and Zhandry (EPRINT 2014), is an appealing notion which allows a single trusted setup for any protocol. As an application of this result, we construct a noninteractive multiparty key exchange (NIKE) protocol for an unbounded number of users without a trusted setup. Prior to this work, such constructions were only known from indistinguishability obfuscation. In obtaining our results, we build upon and significantly extend the techniques of Garg, Pandey, and Srinivasan (EPRINT 2015) introduced in the context of reducing PPAD-hardness to polynomially-secure iO and FE . ∗Research supported in part from DARPA Safeware Award W911NF15C0210, AFOSR Award FA955015-1-0274, and NSF CRII Award 1464397. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government. †University of California, Berkeley, [email protected] ‡Drexel University, [email protected] §University of California, Berkeley, [email protected] ¶MIT, [email protected]