Welcome to the resource topic for 2005/001
Title:
On Obfuscating Point Functions
Authors: 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 nontrivial family of functions under general computational
assumptions. Our obfuscator is based on a probabilistic hash function
constructed from a very strong oneway permutation, and does
not require any setup assumptions. Our construction also yields
an obfuscator for point functions with multibit output. 
We show that such a strong oneway permutation  wherein any
polynomialsized 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 nonprogrammable 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 singlebit output
and in using nonuniform 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 multibit 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
nonstandard numbertheoretic assumptions [C97]. This work
represents the first effort to bridge the gap between the two for a
natural class of functionalities.
ePrint: https://eprint.iacr.org/2005/001
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .