Breaking the sub-exponential barrier in obfustopia

Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

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 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, 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 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: – We construct universal samplers based only on polynomially-secure public-key FE. As an application of this result, we construct a 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. – 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 sub-exponential strength. We proceed in two steps, first giving a construction requiring iO of polynomial strength, and then specializing the FE-to-iO conversion to our specific application. 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsJean-Sebastien Coron, Jesper Buus Nielsen
PublisherSpringer Verlag
Pages156-181
Number of pages26
ISBN (Print)9783319566160
DOIs
StatePublished - Jan 1 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10212 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Breaking the sub-exponential barrier in obfustopia'. Together they form a unique fingerprint.

  • Cite this

    Garg, S., Pandey, O., Srinivasan, A., & Zhandry, M. (2017). Breaking the sub-exponential barrier in obfustopia. In J-S. Coron, & J. B. Nielsen (Eds.), Advances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 156-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10212 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-56617-7_6