Cryptology ePrint Archive: Report 2015/632

More on Impossibility of Virtual Black-Box Obfuscation in Idealized Models

Mohammad Mahmoody and 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 as well assuming the existence of trapdoor permutations (TDPs). On the other hand, the works of Barak et al. (Crypto'14) and Brakerski-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 extend the above two impossibly results for general VBB obfuscation in idealized models. In particular we prove the following two results both assuming the existence of TDPs:

* There is no general VBB obfuscation in the generic group model of Shoup (Eurocrypt'97) for {any abelian} group. By applying our techniques to the setting of Pass and Shelat we extend their result to any (even noncommutative) finite {ring}.

* There is no general VBB obfuscation even in the {random trapdoor permutation oracle} model. Our proof extends to any number of levels of hierarchical trapdoors.

Category / Keywords: Virtual Black-Box Obfuscation, Idealized Models, Graded Encoding, Random Oracles

Date: received 25 Jun 2015

Contact author: mahmoody at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150630:190055 (All versions of this report)

Short URL: ia.cr/2015/632

Discussion forum: Show discussion | Start new discussion