Paper 2016/102

Breaking the Sub-Exponential Barrier in Obfustopia

Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry

Abstract

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. A major challenge in this direction of research is to develop novel techniques for using \io\ since \io\ by itself offers virtually no protection for 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 {\em sub-exponential} loss in the security reduction. Unfortunately, this scenario is becoming more and more common and appears to be a fundamental barrier to many current techniques. A parallel research challenge is building obfuscation from simpler assumptions. Unfortunately, it appears that such a construction would likely incur an exponential loss in the security reduction. Thus, achieving any application of \io\ from simpler assumptions would also require a sub-exponential loss, \emph{even if the \io-to-application security proof incurred a polynomial loss}. Functional encryption (\fe) is known to be equivalent to \io\ up to a sub-exponential loss in the \fe-to-\io\ security reduction; yet, unlike \io, \fe\ \emph{can} be achieved from simpler assumptions (namely, specific multilinear map assumptions) with only a polynomial loss. In the interest of basing applications on weaker assumptions, we therefore argue for using \fe\ as the starting point, rather than \io, and restricting to reductions with only a polynomial loss. By significantly expanding on ideas developed by Garg, Pandey, and Srinivasan (CRYPTO 2016), we achieve the following early results in this line of study: \begin{itemize} \item We construct {\em universal samplers} based only on polynomially-secure public-key \fe. As an application of this result, we construct a {\em non-interactive 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. \item We also construct trapdoor one-way permutations (OWP) based on polynomially-secure public-key \fe. This improves upon the recent result of Bitansky, Paneth, and Wichs (TCC 2016) which requires \io\ of \emph{sub-exponential strength}. We proceed in two steps, first giving a construction requiring \io\ of \emph{polynomial strength}, and then specializing the \fe-to-\io\ conversion to our specific application. \end{itemize} Many of the techniques that have been developed for using \io, including many of those based on the ``punctured programming'' approach, become inapplicable when we insist on polynomial reductions to \fe. As such, our results above require many new ideas that will likely be useful for future works on basing security on \fe.