The paper On Best-Possible Obfuscation defines what is calls "best-possible obfuscation",
and proves (propositions 3.4 and 3.5) that efficient best-possible
obfuscators are exactly efficient indistinguishability obfuscators.

However, it is not clear to me that their definition corresponds to their name.
Inspired by the paper On the (Im)possibility of Obfuscation (though obviously not
using that paper's definition), I define the "better obfuscator hypothesis" as follows:

There exists a probabilistic polynomial-time algorithm $\operatorname{Obf}$ such that,
with all probabilities involving $\operatorname{Obf}$ implicitly taken over $\operatorname{Obf}$'s randomness in
addition to what is indicated explicitly in the subscript, one has the following:

$\;$ for all circuits $C$, $\;\; \operatorname{Prob}\left(\operatorname{Obf}(C\hspace{.03 in}) \text{ is a circuit that computes the same function as } C\right) \: = \: 1$


$\;$ for all families of polynomial-size circuits $\mathcal{F}\hspace{-0.02 in}_0$ and $\mathcal{F}\hspace{-0.03 in}_1$, if
$\;$ $\;$ for all adversaries $\mathcal{B}$ that are restricted to polynomially-many
$\;$ $\;$ oracle queries but are (otherwise) computationally unbounded,
$\;$ $\;$ $\left|\hspace{.02 in}\operatorname{Prob}_{C\leftarrow \mathcal{F}_0}\hspace{-0.05 in}\left(\mathcal{B}^C\hspace{-0.03 in}(\operatorname{size}(C\hspace{.03 in})) = 1\hspace{-0.02 in}\right)-\operatorname{Prob}_{C\leftarrow \mathcal{F}_1}\hspace{-0.05 in}\left(\mathcal{B}^C\hspace{-0.03 in}(\operatorname{size}(C\hspace{.03 in})) = 1\hspace{-0.02 in}\right)\right| \;$ is negligible
$\;$ then
$\;$ $\;$ for all feasible adversaries $\mathcal{A}$,
$\;$ $\;$ $\left|\operatorname{Prob}_{C\leftarrow \mathcal{F}_0}\hspace{-0.05 in}(\mathcal{A}(\operatorname{Obf}(C\hspace{.03 in})) = 1)-\operatorname{Prob}_{C\leftarrow \mathcal{F}_1}\hspace{-0.05 in}(\mathcal{A}(\operatorname{Obf}(C\hspace{.03 in})) = 1)\right| \;$ is negligible


(With respect to non-uniform adversaries, indistinguishability obfuscation
is equivalent to replacing "families" with "sequences" in that definition.)

Is the "better obfuscator hypothesis" known to be false?
Is the "better obfuscator hypothesis" known to be equivalent to the existence
of an efficient best-possible obfuscator, as defined on page 7 of paper #1?

  • $\begingroup$ Another confusion I have is how how you pick a circuit $C$ from a family $\mathcal{F}_i$? Since you say "families of polynomial size circuits", then the family must be infinite, so how do you pick a random circuit? Do you fix the size and the statements must hold for every size? $\endgroup$ – Sasho Nikolov Feb 4 '14 at 17:09
  • $\begingroup$ I use distribution ensembles. $\:$ (I suppose I could edit that fact into the question.) $\hspace{1.03 in}$ $\endgroup$ – user6973 Feb 4 '14 at 20:05
  • $\begingroup$ It's not clear to me why this isn't equivalent to VBB. It seems your goal is to make the obfuscator produce something that "acts as if" the evaluator has oracle access to the circuit. Since we know VBB is impossible, do you have any example or property that separates "better obfuscation" from VBB (even intuitively)? $\endgroup$ – Daniel Apon Feb 5 '14 at 9:02
  • $\begingroup$ For instance, like VBB, your definition would appear to allow ("full") obfuscation of cryptographic functions (since loosely, $A^{PRF_{K_1}}(1^\lambda) \stackrel{c}{\approx} A^{PRF_{K_2}}(1^\lambda)$). This stands in contrast to impossibility results related to superpolynomial pseudoentropy circuit families, e.g. eprint.iacr.org/2013/665.pdf $\endgroup$ – Daniel Apon Feb 5 '14 at 9:41
  • $\begingroup$ The property is "computational security": the impossibility proof for VBB uses encryption that is only computationally secure, which may allow $\mathcal{B}$ to distinguish the two cases using only black-box access. $\:$ Similarly, I imagine that most useful-on-their-own cryptographic functions can heuristically be expected to "be trivial" to adversaries like $\mathcal{B}$. $\:$ (I think the main exceptions would be those that $\mathcal{B}$ can't distinguish from being constant, such as verifications algorithms and some decryption algorithms.) $\;\;\;\;$ $\endgroup$ – user6973 Feb 5 '14 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy