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 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.
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 .