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 \NC1 or even \TC0 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
obfuscation
Contact author(s)
benny applebaum @ gmail com
History
2013-10-28: received
Short URL
https://ia.cr/2013/699
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/699,
      author = {Benny Applebaum},
      title = {Bootstrapping Obfuscators via Fast Pseudorandom Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/699},
      year = {2013},
      url = {https://eprint.iacr.org/2013/699}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.