8
$\begingroup$

Recently, there has been a major theoretical breakthrough in program obfuscation, in the area of indistinguishability obfuscation.

Background: Indistinguishability obfuscation is a form of program obfuscation, with the following security property: if $C_1,C_2$ are two different circuits that both compute the same function, then $\text{Obf}(C_1)$ should be indistinguishable from $\text{Obf}(C_2)$, where $\text{Obf}(C)$ is the obfuscation of the circuit $C$. In other words, if there are multiple ways to implement a particular functionality, the obfuscation of an implementation doesn't reveal anything about the implementation choices you made, though it might reveal the input-output function completely.

The recent breakthrough shows how to achieve indistinguishability obfuscation of any circuit in NC1. This is a huge step forward in the theory and foundations of obfuscation. Unfortunately, the construction is highly inefficient -- the obfuscated circuit is hugely slower than the original -- so the scheme described in this breakthrough paper is totally impractical. However, often in cryptography if we focus in on special classes of functions, we can come up with specialized schemes that perform a lot better.

My question: What functions do we know how to obfuscate (in the sense of indistinguishability obfuscation) efficiently? Are there classes of functions for which we can provide indistinguishability obfuscation, where the obfuscated circuit/program is efficient, and if so, what are they? I'm fine even if the scheme relies on non-standard hardness assumptions, or even a construction where we have no proof of security but where it seems plausible that it might be secure.

| improve this question | |
$\endgroup$
  • $\begingroup$ Note: The simplest one is a class that allows us to compute a normal form of a circuit efficiently. The class of log size circuits seems ok for iO without any assumptions. $\endgroup$ – xagawa Mar 16 '14 at 13:16
  • $\begingroup$ Thanks, @xagawa! On log-size circuits: What is the log of? i.e., log of which parameter? (presumably not the size of the input to the circuit) For normal forms: are there known classes of circuits that have a normal form? I know that BDDs can be put into normal form. That's all I know but I'm guessing probably more is known.... $\endgroup$ – D.W. Mar 16 '14 at 15:15
  • $\begingroup$ Note that "iO of BDDs" is not known to imply iO of circuits that are implementable as small BDDs. $\hspace{.42 in}$ The log is of the amount of work that the obfuscator is allowed to do. $\;$ $\endgroup$ – user991 Mar 16 '14 at 23:03
  • $\begingroup$ More powerfully (and illustratively), one can "trivially" achieve virtual black-box obfuscation of functions for which each output bit syntactically depends on at most logarithmically many input bits, since a nice-enough representation of such functions can be learned by querying sufficiently many random pairs of inputs that differ on exactly one bit, where "nice-enough" means someone with the original circuit can efficiently-and-deterministically test whether or not the representation computes the same function. $\;$ $\endgroup$ – user991 Mar 16 '14 at 23:06
6
$\begingroup$

Canetti ("Towards realizing random oracles," Crypto 1997) gave a reasonably efficient (very efficient, by the standards of most obfuscation work) "virtual black-box" obfuscator for "point functions," i.e., functions of the form $I_x(y) = 1$ if $x=y$, $0$ otherwise. Such functions can be used, e.g., for password checking.

Virtual black-box obfuscation implies indistinguishability obfuscation, and is impossible for general circuits, but seemingly possible for specialized functions (like point functions).

In Canetti's construction, evaluating an obfuscated point function requires only one call to a collision-resistant hash function, and one exponentiation. Its security relies on some strong, nonstandard, DDH-like assumption.

There are follow-up works by Wee and Canetti-Dakdouk, among others, on obfuscating point functions, hyperplanes, large-output functions, etc. etc. with VBB security.

Also, Lynn-Prabhakaran-Sahai ("Positive Results and Techniques for Obfuscation," Eurocrypt 2004) gave VBB obfuscators for certain classes of access-control functions, which I believe are not exceedingly inefficient. They work in the random oracle model, however.

These are just a few representative works from prior to the iO revolution, when people were mainly working on VBB obfuscation for specific classes of functions.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.