# Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that $$i)$$ the output Obs(C) is a circuit with the same functionality as C and $$ii)$$ for any $$C_1$$ and $$C_2$$ with the same functionality, we have that Obs($$C_1$$) is indistinguishable from Obs($$C_2$$).

Has a similar notion (and candidate construction) for a similar concept where the security holds for $$C_1$$ and $$C_2$$ are almost the same (i.e., they agree on all except a negligible fraction of the inputs, and it is computationally hard to find the points where they differ).

• Wouldn't "regular" iO imply this? Since $\text{Obs}$ needs to be efficient, in particular we can't use its output to distinguish between "almost-the-same" $C_1,C_2$, and so the outputs $\text{Obs}(C_1)$ and $\text{Obs}(C_2)$ must still be (computationally) indistinguishable as well? Mar 5 '20 at 6:20
• Not by the (text-book) definition of iO. The security definition only asks that of C_1 and C_2 have the same functionality, their obfuscation are indistinguishable and if C_1 is not implementing the same function as C_2, anything could happen. Answering your comment, I just realized that maybe what I am asking is equivalent for Virtual Black Box obfuscation for evasive functions (what is known to be impossible in the most general case) Mar 6 '20 at 17:25
• I understand this is not guaranteed by the definition itself, but my point is that it could be implied by it — since $\textrm{Obs}$ is assumed efficient, it could otherwise be used to "break" the computational hardness of distinguishing $C_1$ and $C_2$. Otherwise: take $C_1\neq C_2$ (different functionality) computationally hard to distinguish. Pass them through $\textrm{Obs}$. If you can distinguish $\textrm{Obs}(C_1)$ from $\textrm{Obs}(C_2)$, then you have distinguished $C_1$ from $C_2$ (which was assumed hard). So $\textrm{Obs}(C_1)$, $\textrm{Obs}(C_2)$ must also be hard to distinguish. Mar 6 '20 at 18:16
• (Unless I am botching something here, possibly two different notions of distinguishability?) Mar 6 '20 at 18:19
• I can post a longer answer later, but a keyword you should look up for is differing input obfuscation. Mar 7 '20 at 1:07

The definition of diO tells us: if there's a non-uniform PPT adversary that can distinguish the obfuscations of two circuits with "almost same" functionalities Obf($$C_1$$) and Obf($$C_2$$), then there exists a non-uniform PPT extractor that can extract an input(witness) $$x$$ where $$C_1(x) \neq C_2(x)$$. (the formal definition is on page 11)
If there are only polynomially many inputs where their outputs are different evaluated on $$C_1, C_2$$, then the standard iO definition also implies diO, using a binary search argument on the input space.