Paper 2016/316

A Note on Black-Box Separations for Indistinguishability Obfuscation

Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat

Abstract

Mahmoody et al. (TCC 2016-A) showed that basing indistinguishability obfuscation (IO) on a wide range of primitives in a black-box way is \emph{as hard as} basing public-key cryptography on one-way functions. The list included any primitive $P$ that could be realized relative to random trapdoor permutation or degree-$O(1)$ graded encoding oracle models in a secure way against computationally unbounded polynomial-query attackers. In this work, relying on the recent result of Brakerski, Brzuska, and Fleischhacker (ePrint 2016/226) in which they ruled out statistically secure approximately correct IO, we show that there is no fully black-box constructions of IO from any of the primitives listed above, assuming the existence of one-way functions and $NP \not \subseteq coAM$. At a technical level, we provide an alternative lemma to the Borel-Cantelli lemma that is useful for deriving black-box separations. In particular, using this lemma we show that attacks in idealized models that succeed with only a \emph{constant} advantage over the trivial bound are indeed sufficient for deriving fully black-box separations from primitives that exist in such idealized models unconditionally.

Note: This is a more polished version.