<p>I think the notion you're looking for is differing-inputs indistinguishability obfuscation(diO), or originally called extractability iO:
<a href="https://eprint.iacr.org/2013/650.pdf" rel="nofollow noreferrer">https://eprint.iacr.org/2013/650.pdf</a></p>

<p>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(<span class="math-container">$C_1$</span>) and Obf(<span class="math-container">$C_2$</span>), then there exists a non-uniform PPT extractor that can extract an input(witness) <span class="math-container">$x$</span> where <span class="math-container">$C_1(x) \neq C_2(x)$</span>.
(the formal definition is on page 11)</p>

<p>If there are only <strong>polynomially</strong> many inputs where their outputs are different evaluated on <span class="math-container">$C_1, C_2$</span>, then the standard iO definition also implies diO, using a binary search argument on the input space.</p>

<p>If there are negligible(in ratio) but exponentially many different outputs , then diO is a stronger assumption than standard iO. There are some negative results on the possibility of its existence in certain cases:</p>

<p><a href="https://eprint.iacr.org/2016/162.pdf" rel="nofollow noreferrer">https://eprint.iacr.org/2016/162.pdf</a></p>

<p><a href="https://eprint.iacr.org/2013/860.pdf" rel="nofollow noreferrer">https://eprint.iacr.org/2013/860.pdf</a></p>

CC BY-SA 4.0
2020-03-08T21:43:57.570Z
2020-03-08T21:43:57.570Z
Biu
<p>In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that <span class="math-container">$i)$</span> the output Obs(C) is a circuit with the same functionality as C and <span class="math-container">$ii)$</span> for any <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> with the same functionality, we have that Obs(<span class="math-container">$C_1$</span>) is indistinguishable from Obs(<span class="math-container">$C_2$</span>).</p>

<p>Has a similar notion (and candidate construction) for a similar concept where the security holds for <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> 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).</p>

CC BY-SA 4.0
2020-03-05T06:20:02.913Z
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?
Clement C.
CC BY-SA 4.0
2020-03-06T17:25:13.377Z
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)
Alex Grilo
CC BY-SA 4.0
2020-03-06T18:16:33.293Z
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.
Clement C.
CC BY-SA 4.0
2020-03-06T18:19:55.863Z
(Unless I am botching something here, possibly two different notions of distinguishability?)
Clement C.
CC BY-SA 4.0
2020-03-07T01:07:47.380Z
I can post a longer answer later, but a keyword you should look up for is differing input obfuscation.
Geoffroy Couteau
<obfuscation><cryptography>
Is there a notion of indistinguishability obfuscation for almost equivalent circuits?
Alex Grilo
# Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

(Asked by: username_0 on 2020-03-05)

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).

**Tags:** obfuscation, cryptography
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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)  
> **username_1**: 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.  
> **username_1**: (Unless I am botching something here, possibly two different notions of distinguishability?)  
> **username_2**: I can post a longer answer later, but a keyword you should look up for is differing input obfuscation.  

---

## 1 answers

### Answer by username_3 on 2020-03-08. Score: 4 | Accepted answer

I think the notion you're looking for is differing-inputs indistinguishability obfuscation(diO), or originally called extractability iO:
<https://eprint.iacr.org/2013/650.pdf>

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.

If there are negligible(in ratio) but exponentially many different outputs , then diO is a stronger assumption than standard iO. There are some negative results on the possibility of its existence in certain cases:

<https://eprint.iacr.org/2016/162.pdf>

<https://eprint.iacr.org/2013/860.pdf>


---

