International Association
for Cryptologic Research

Mahmoody et al. (TCC 2016-A) showed that basing indistinguishability obfuscation (IO) on a wide range of primitives in a semi-black-box way is as hard as basing public-key cryptography on one-way functions. The list included any primitive $P$ that can be realized relative to random trapdoor permutations or degree-$O(1)$ graded encoding model for any finite ring secure against computationally unbounded polynomial-query attackers.

In this note, we rely on the recent result of Brakerski, Brzuska, and Fleischhacker (ePrint 2016/226) and rule out fully black-box constructions of IO from any such primitive $P$, assuming the existence of one-way functions and $\mathbf{NP} \not \subseteq \mathbf{coAM}$. At a technical level, we show that attacks in idealized (randomized) oracle models that succeed with constant advantage over the trivial bound (e.g., guessing the obfuscated circuit with probability $1/2+1/10$) would remain successful for an infinite sequence of security parameters for a non-zero measure of the oracles.