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.
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
-
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},
note = {\url{https://eprint.iacr.org/2013/699}},
url = {https://eprint.iacr.org/2013/699}
}
