Paper 2005/001

On Obfuscating Point Functions

Hoeteck Wee

Abstract

We study the problem of obfuscation in the context of point functions (also known as delta functions). A point function is a Boolean function that assumes the value 1 at exactly one point. Our main results are as follows: - We provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation - wherein the size of the simulator has an inverse polynomial dependency on the distinguishing probability - which is nonetheless impossible for general circuits. This is the first known construction of obfuscators for a non-trivial family of functions under general computational assumptions. Our obfuscator is based on a probabilistic hash function constructed from a very strong one-way permutation, and does not require any set-up assumptions. Our construction also yields an obfuscator for point functions with multi-bit output. - We show that such a strong one-way permutation - wherein any polynomial-sized circuit inverts the permutation on at most a polynomial number of inputs - can be realized using a random permutation oracle. We prove the result by improving on the counting argument used in [GT00]; this result may be of independent interest. It follows that our construction yields obfuscators for point functions in the non-programmable random permutation oracle model (in the sense of [N02]). Furthermore, we prove that an assumption like the one we used is necessary for our obfuscator construction. - Finally, we establish two impossibility results on obfuscating point functions which indicate that the limitations on our construction (in simulating only adversaries with single-bit output and in using non-uniform advice in our simulator) are in some sense inherent. The first of the two results is a consequence of a simple characterization of functions that can be obfuscated against general adversaries with multi-bit output as the class of functions that are efficiently and exactly learnable using membership queries. We stress that prior to this work, what is known about obfuscation are negative results for the general class of circuits [BGI01] and positive results in the random oracle model [LPS04] or under non-standard number-theoretic assumptions [C97]. This work represents the first effort to bridge the gap between the two for a natural class of functionalities.