### 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 = {To appear in TCC'2016},
year = {2016},
}
```

### Abstract

Indistinguishability obfuscation (iO for short) has become a central cryptographic primitive with numerous applications. Known constructions of iO are based on multi-linear 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 black-box 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 black-box construction of iO from (exponentially secure) collision-resistant hash functions unless the polynomial hierarchy collapses. Our result extends to (separate iO from) any primitive implied by a random oracle in a black-box 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 black-box construction of iO from $P$ is \emph{as hard as} basing public-key cryptography on one-way functions.

We present a constructive procedure that takes any black-box construction of iO from $P$ and turns it into a construction of semantically secure public-key encryption from any one-way functions. Our separations hold even if the construction of iO from $P$ is \emph{semi-}black-box (Reingold, Trevisan, and Vadhan, TCC’04) and the security reduction could access the adversary in a non-black-box way.