Lower Bounds on Assumptions behind Indistinguishability Obfuscation
@inproceedings{MMNPS16,
title = {Lower Bounds on Assumptions behind Indistinguishability Obfuscation},
author = {Mohammad Mahmoody and Ameer Mohammed and Soheil Nematihaji and Rafael Pass and abhi shelat},
booktitle = {TCC'2016 and eprint/2015/1062},
year = {2016},
}
Abstract
Indistinguishability obfuscation (iO for short) has become a central cryptographic primitive with numerous applications. Known constructions of iO are based on multilinear maps (Garg \etal Eurocrypt'13) and their idealized formulation as the graded encoding model.
Basing iO on standard assumptions remains an elusive open question.
In this work we prove lower bounds on the assumptions that imply iO in a blackbox way. Note that any lower bound for iO must rely on computational assumptions because if $P = NP$ then statistically secure iO exists unconditionally. Our results are twofold:

There is no fully blackbox construction of iO from (exponentially secure) collisionresistant hash functions unless the polynomial hierarchy collapses. Our result extends to (separate iO from) any primitive implied by a random oracle in a blackbox way.

Let $P$ be any primitive that exists relative to random trapdoor permutations, the generic group model for any finite abelian group, or degree$O(1)$ graded encoding model for any finite ring. We show that achieving a blackbox construction of iO from $P$ is \emph{as hard as} basing publickey cryptography on oneway functions.
We present a constructive procedure that takes any blackbox construction of iO from $P$ and turns it into a construction of semantically secure publickey encryption from any oneway functions. Our separations hold even if the construction of iO from $P$ is \emph{semi}blackbox (Reingold, Trevisan, and Vadhan, TCC'04) and the security reduction could access the adversary in a nonblackbox way.