4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) ​ ​ ​ ​ $\endgroup$ – user991 Jan 21 '16 at 0:26
  • $\begingroup$ 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? $\endgroup$ – pg1989 Jan 21 '16 at 2:28
  • $\begingroup$ @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. $\endgroup$ – heisenberg Jan 22 '16 at 1:16
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Unless P=NP. Yes, I think this precisely what my second paragraph states. As Ricky Demer mentioned above, if efficient deterministic VBB obfuscators (or even indistinguishability obfuscators) exist, then P=NP. However, what if we are want to obfuscate a class of circuits where no two circuits compute the same functionality? This is what my third paragraph asks. $\endgroup$ – heisenberg Jan 22 '16 at 1:09
  • 1
    $\begingroup$ @heisenberg I have edited to fix my answer. Regarding your question, we know of classes that you provable CANNOT VBB obfuscate. Your question is whether it is possible to VBB any non-trivial class in a provably secure way. There is some work on point obfuscation... $\endgroup$ – Yehuda Lindell Jan 22 '16 at 5:41
  • $\begingroup$ I meant: whether there exists some non-trivial class that can be obfuscated in a provably secure way. $\endgroup$ – Yehuda Lindell Jan 22 '16 at 8:28

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.