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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Indistinguishability ObfuscationBlack-Box Separations
Contact author(s)
mahmoody @ gmail com
History
2016-05-24: last of 2 revisions
2016-03-22: received
See all versions
Short URL
https://ia.cr/2016/316
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/316,
      author = {Mohammad Mahmoody and Ameer Mohammed and Soheil Nematihaji and Rafael Pass and abhi shelat},
      title = {A Note on Black-Box Separations for Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/316},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/316}},
      url = {https://eprint.iacr.org/2016/316}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.