3
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – Clement C. Mar 5 '20 at 6:20
  • $\begingroup$ 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) $\endgroup$ – Alex Grilo Mar 6 '20 at 17:25
  • $\begingroup$ 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. $\endgroup$ – Clement C. Mar 6 '20 at 18:16
  • $\begingroup$ (Unless I am botching something here, possibly two different notions of distinguishability?) $\endgroup$ – Clement C. Mar 6 '20 at 18:19
  • 1
    $\begingroup$ I can post a longer answer later, but a keyword you should look up for is differing input obfuscation. $\endgroup$ – Geoffroy Couteau Mar 7 '20 at 1:07
4
$\begingroup$

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

Improve this answer
$\endgroup$

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.