Cryptology ePrint Archive: Report 2016/316

A Note on Black-Box Separations for Indistinguishability Obfuscation

Mohammad Mahmoody and Ameer Mohammed and Soheil Nematihaji and 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.

Category / Keywords: foundations / Indistinguishability Obfuscation, Black-Box Separations

Date: received 19 Mar 2016, last revised 24 May 2016

Contact author: mahmoody at gmail com

Available format(s): PDF | BibTeX Citation

Note: This is a more polished version.

Version: 20160524:215155 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]