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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
Indistinguishability ObfuscationFunctional EncryptionTrapdoor PermutationUniversal SamplerNon-Interactive Key ExchangePolynomial Security Loss
Contact author(s)
sanjamg @ berkeley edu
omkant @ drexel edu
akshayaram @ berkeley edu
mzhandry @ gmail com
History
2017-02-13: last of 2 revisions
2016-02-08: received
See all versions
Short URL
https://ia.cr/2016/102
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/102,
      author = {Sanjam Garg and Omkant Pandey and Akshayaram Srinivasan and Mark Zhandry},
      title = {Breaking the Sub-Exponential Barrier in Obfustopia},
      howpublished = {Cryptology ePrint Archive, Paper 2016/102},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/102}},
      url = {https://eprint.iacr.org/2016/102}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.