International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the Limits of Point Function Obfuscation

Authors:
Arvind Narayanan
Vitaly Shmatikov
Download:
URL: http://eprint.iacr.org/2006/182
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21675,
  title={On the Limits of Point Function Obfuscation},
  booktitle={IACR Eprint archive},
  keywords={obfuscation, random oracle model, security reduction},
  url={http://eprint.iacr.org/2006/182},
  note={Under submission arvindn@cs.utexas.edu 13298 received 30 May 2006},
  author={Arvind Narayanan and Vitaly Shmatikov},
  year=2006
}