Paper 2015/632

On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models

Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji

Abstract

The celebrated work of Barak et. al (Crypto'01) ruled out the possibility of virtual black-box (VBB) obfuscation for general circuits. The recent work of Canetti, Kalai, and Paneth (TCC'15) extended this impossibility to the random oracle model, assuming the existence of trapdoor permutations (TDPs). On the other hand, the works of Barak et. al (Crypto'14) and Brakerski and Rothblum (TCC'14) showed that general VBB obfuscation is indeed possible in idealized graded encoding models. The recent work of Pass and Shelat (Cryptology ePrint 2015/383) complemented this result by ruling out general VBB obfuscation in idealized graded encoding models that enable evaluation of constant-degree polynomials in finite fields. In this work, we extend the above two impossibility results for general VBB obfuscation in idealized models. In particular we prove the following two results both assuming the existence of trapdoor permutations: * There is no general VBB obfuscation in the generic group model of Shoup (Eurocrypt'97) for any abelien group. By applying our techniques to the setting of Pass and Shelat we extend their result to any (even non-commutative) finite ring. * There is no general VBB obfuscation in the random trapdoor permutation oracle model. Note that as opposed to the random oracle which is an idealized primitive for symmetric primitives, random trapdoor permutation is an idealized public-key primitive.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Virtual Black-Box ObfuscationIdealized ModelsGraded EncodingRandom Oracles
Contact author(s)
mahmoody @ gmail com
History
2016-06-30: revised
2015-06-30: received
See all versions
Short URL
https://ia.cr/2015/632
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/632,
      author = {Mohammad Mahmoody and Ameer Mohammed and Soheil Nematihaji},
      title = {On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models},
      howpublished = {Cryptology ePrint Archive, Paper 2015/632},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/632}},
      url = {https://eprint.iacr.org/2015/632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.