Paper 2006/182

On the Limits of Point Function Obfuscation

Arvind Narayanan and Vitaly Shmatikov

Abstract

We study the problem of circuit obfuscation, ie, transforming the circuit in a way that hides everything except its input-output behavior. Barak et al. showed that a universal obfuscator that obfuscates every circuit class cannot exist, leaving open the possibility of special-purpose obfuscators. Known positive results for obfuscation are limited to point functions (boolean functions that return 1 on exactly one input) and simple extensions thereof in the random oracle model, ie, assuming black-box access to a true random function. It was also shown by Wee how to instantiate random oracles so as to achieve a slightly weaker form of point function obfuscation. Two natural questions arise: (i) what circuits have obfuscators whose security can be reduced in a black-box way to point function obfuscation? and (ii) for what circuits obfuscatable in the random oracle model can we instantiate the random oracles to build obfuscators in the plain model? We give partial answers to these questions: there is a circuit in AC^0 which can be obfuscated in the random oracle model, but not secure when random oracles are instantiated with Wee's construction. More generally, we present evidence for the impossibility of a black-box reduction of the obfuscatability of this circuit to point function obfuscation. Conversely, this result shows that to instantiate random oracles in general obfuscators, one needs to utilize properties of the instantiation that are not satisfied by point function obfuscators.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Under submission
Keywords
obfuscationrandom oracle modelsecurity reduction
Contact author(s)
arvindn @ cs utexas edu
History
2006-05-30: received
Short URL
https://ia.cr/2006/182
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/182,
      author = {Arvind Narayanan and Vitaly Shmatikov},
      title = {On the Limits of Point Function Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2006/182},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/182}},
      url = {https://eprint.iacr.org/2006/182}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.