Skip to main content

Breaking the Sub-Exponential Barrier in Obfustopia

Author(s): Garg, Sanjam; Pandey, Omkant; Srinivasan, Akshayaram; Zhandry, Mark

To refer to this page use:
Abstract: Indistinguishability obfuscation ( π‘–ξˆ» ) has emerged as a surprisingly powerful notion. Almost all known cryptographic primitives can be constructed from general purpose π‘–ξˆ» and other minimalistic assumptions such as one-way functions. A major challenge in this direction of research is to develop novel techniques for using π‘–ξˆ» since π‘–ξˆ» 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 π‘–ξˆ» from simpler assumptions would also require a sub-exponential loss, even if the π‘–ξˆ» -to-application security proof incurred a polynomial loss. Functional encryption (  ) is known to be equivalent to π‘–ξˆ» up to a sub-exponential loss in the  -to- π‘–ξˆ» security reduction; yet, unlike π‘–ξˆ» ,  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  as the starting point, rather than π‘–ξˆ» , 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  . 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  . This improves upon the recent result of Bitansky, Paneth, and Wichs (TCC 2016) which requires π‘–ξˆ» of sub-exponential strength. We proceed in two steps, first giving a construction requiring π‘–ξˆ» of polynomial strength, and then specializing the  -to- π‘–ξˆ» conversion to our specific application. Many of the techniques that have been developed for using π‘–ξˆ» , including many of those based on the β€œpunctured programming” approach, become inapplicable when we insist on polynomial reductions to  . As such, our results above require many new ideas that will likely be useful for future works on basing security on  .
Publication Date: 2017
Citation: Garg, Sanjam, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry. "Breaking the Sub-Exponential Barrier in Obfustopia." In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2017): pp. 156-181. doi:10.1007/978-3-319-56617-7_6
DOI: 10.1007/978-3-319-56617-7_6
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 156 - 181
Type of Material: Conference Article
Journal/Proceeding Title: Annual International Conference on the Theory and Applications of Cryptographic Techniques
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.