How indistinguishability obfuscation implies unintelligibility of a program?

Question

Given an obfuscator $O$ that takes as input a circuit $C$ and outputs its obfuscated version $O(C)$, we expect, informally, that the obfuscated version should be somehow "unintelligible" for anyone who sees or runs it. In other words, it should be able to hide secrets.

My understanding is:

• The strongest notion of Virtual Black Box security for an obfuscator was proven impossible by BGI+01
• BGI+01 also provided a weaker notion of indistinguishability obfuscation (iO) such that given the obfuscator $O$ and two circuits $C1$ and $C2$ with equivalent functionalities, the two distributions of obfuscations $O(C1)$ and $O(C2)$ should be computationally indistinguishable.
• From the Best-Possible Obfuscation definition of GR07, the obfuscated circuit leaks less information than any other circuit (of a similar size) computing the same function.

How this security definition implies the unintelligibility of the obfuscated program?.

A possible explanation is given by GGH+13 using the two-key technique. In practice, they start with two programs $P1$ and $P2$ with the same functionalities, where $P1$ has a secret $sk_1$ inside (but not $sk_2$), and $P2$ has a secret $sk_2$ inside (but not $sk_1$). Since the obfuscations of the two programs $O(P1)$ and $O(P2)$ are indistinguishable, neither program leaks either secret.

I am still struggling to understand why this guarantees the unintelligibility of the secret. It seems to me that it only guarantees the unintelligibility in a 50% chance game: sure the adversary cannot distinguish which secret is hardcoded inside an obfuscated program. Still, it must be one of the two (either $sk_1$ or $sk_2$).

Answer 1

The answer is that it doesn't (necessarily). As GGH+13 states (p1):

We note that if the circuit class C has efficiently computable canonical forms, then the computation of that canonical form would already be an indistinguishability obfuscator [BGI+12, GR07].

The real question is "Why is the definition of iO useful?" Indeed, this is what the authors go on to discuss (p4):

Now that we have constructed an indistinguishability obfuscator, we are faced with the question: what good is an indistinguishability obfuscator? The definition of indistinguishability obfuscation does not make clear what, if anything, an indistinguishability obfuscator actually hides about a circuit. In particular, if the circuit being obfuscated was already in an obvious canonical form, then we know that the indistinguishability obfuscator would not need to hide anything.

The authors then construct Functional Encryption for all circuits from iO (although this particular scheme is broken -- see Are Graded Encoding Schemes Broken Yet?). So it clearly is useful!

The point is that a "secure" indistinguishability obfuscator doesn't appear that useful a primitive on its own, but it can be used to construct things that are useful in the right context.