Cryptology ePrint Archive: Report 2013/699

Bootstrapping Obfuscators via Fast Pseudorandom Functions

Benny Applebaum

Abstract: We show that it is possible to upgrade an obfuscator for a weak complexity class $\weak$ into an obfuscator for arbitrary polynomial size circuits, assuming that the class $\weak$ can compute pseudorandom functions. Specifically, under standard intractability assumptions (e.g., hardness of factoring, Decisional Diffie–-Hellman, or Learning with Errors), the existence of obfuscators for $\NC^1$ or even $\TC^0$ implies the existence of general-purpose obfuscators for $\classP$. Previously, such a bootstrapping procedure was known to exist under the assumption that there exists a fully-homomorphic encryption whose decryption algorithm can be computed in $\weak$. Our reduction works with respect to virtual black-box obfuscators and relativizes to ideal models.

Category / Keywords: foundations / obfuscation

Date: received 26 Oct 2013

Contact author: benny applebaum at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20131028:201133 (All versions of this report)

Short URL: ia.cr/2013/699

Discussion forum: Show discussion | Start new discussion