Why are obfuscators generally defined to be probabilistic algorithms, rather than deterministic ones?

One possible explanation is, randomness is not going to hurt you, so might as well use it. Also, if we are hoping to prove impossibility, it only makes the result stronger.

One other explanation is if the obfuscators are defined to be deterministic, then to satisfy the strong virtual black-box definition (and the weaker indistinguishability obfuscation definition), it should be the case that all functionally equivalent circuits (that are of similar sizes) must be obfuscated to the same circuit, and this is difficult.

But, what if we are considering a class of circuits where no two circuits in the class are functionally the same? For example, a class of point circuits (where each circuit in the class evaluates to 1 on a specific point that is hard-wired in that circuit, and evaluates to 0 on all other points). Does it make sense to think of deterministic obfuscation in this case?

• Obfuscating "all functionally equivalent circuits" "to the same circuit" is in fact NP-hard. ​ (Just compare the obfuscation of an arbitrary circuit with the obfuscation of a circuit that always outputs False.) ​ ​ ​ ​ – user991 Jan 21 '16 at 0:26
• Sometimes in theory, randomness lets you skirt weird paradoxes that would otherwise render a definition useless, like in interactive proofs. Maybe something similar happens with obfuscation definitions? – pg1989 Jan 21 '16 at 2:28
• @RickyDemer, Yes, this is what I meant by "and this is difficult". Perhaps I should have been more clear. Please look at my reply to Yehuda Lindell's answer. – heisenberg Jan 22 '16 at 1:16

Let's consider the notion of IO (indistinguishability obfuscation). Informally, the definition states that for every two circuits $C_1$ and $C_2$ such that $C_1(x)=C_2(x)$ for every $x$, it holds that $IO(C_1)$ is computationally indistinguishable from $IO(C_2)$. That is, a distinguisher knowing $C_1$ and $C_2$ and given an obfuscation of one of them cannot guess which with probability greater than $1/2$.
Now, assume for a moment that $IO$ is a deterministic algorithm. In addition, assume that $IO$ does not map all equivalent $C_1,C_2$ to the same concrete output (if it could do this, then we would have an efficient way of determining that circuits compute the same function, which is co-NP complete). Then, the distinguisher could simply compute $IO(C_1)$ and $IO(C_2)$ and compare to the obfuscated program that it received. With this strategy it knows which circuit was obfuscated with probability 1. Thus, $IO$ cannot be deterministic.