Paper 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.