What is Black-Box Obfuscation?

Question

I understand black-box obfuscation at some intuitive level as- "an adversary can learn nothing more from an obfuscated program/circuit/function than he or she can from a black-box access to the same program/circuit/function." But I am failing at grasping it formally.

I got the following description from this site:

Black-box obfuscation: For every adversary $A$, there is a simulator $S$ such that for every program $f$ and distinguisher $D$:

$$Pr(D(A(O(f)))) ≈ Pr(D(S^{f}(|f|)))$$

I understand most of it, but I don't get what a/the simulator $S$ is and what it is for in the definition. In other words, what has the existence of the simulator to do with?

Answer 1

The simulator is just an algorithm. The idea is that for any adversary $A$, you can create an algorithm $S$ that can "simulate" $A$, that is, that has the same output as $A$.

The notation $S^{f}$ means that the algorithm $S$ does not have direct access to $f$, but just oracle access, i.e., every time $S$ wants to evaluate $f$ at an input $x$, it just sends $x$ to the oracle and gets $f(x)$. This formalizes the notion of "$S$ learns nothing about $f$ but pairs of input-output $(x, f(x))$". The actual input of $S$ is just the "size of the program". That is why we write $S^f(|f|)$.

On the other side, we have an adversary (also an algorithm) that has as input an obfuscation of the function, i.e., $O(f)$, and can evaluate the obfuscated function by itself, obtaining $O(f)(x) = f(x)$ for any $x$. But more than that, it can actually analyze $O(f)$ to try to extract extra information about $f$.

Now, when we say that these two probability distributions are the same (or are indistinguishable), we are saying that both $S^f$ and $A$ behave in the same manner, i.e., the values output by them are the same. In particular, if $A$ can output some information about $f$, so can $S^f$. But then that information can be learned from the input-output pairs, since that is all that $S^f$ has, which means that the obfuscation $O(f)$ is not leaking extra information about $f$, as intended.

Answer 2

1. You have a polynomial black box attacker, who is able to make polynomially many requests to the oracle.

2. You have an exponential black box attacker, who is able to make exponentially many requests to the oracle.

3. You have a polynomial white box attacker, who has access to the (obfuscated) representation and can do more than just query the oracle, but must work in polynomial time.

Virtual black box property says that the attacker 3 is equivalent to the attacker 1. If the attacker 3 gains powers of the attacker 2, the obfuscation is broken.