Black-box obfuscation

Impossibility

The unobfuscatable programs

Barak et al. constructed a family of unobfuscatable programs, for which an efficient attacker can always learn more from any obfuscated code than from black-box access.

Broadly, they start by engineering a special pair of programs that cannot be obfuscated together. For some randomly selected strings ${\displaystyle \alpha ,\beta }$ of a fixed, pre-determined length ${\displaystyle k}$, define one program to be one that computes

${\displaystyle C_{\alpha ,\beta }(x):=\{\begin{array}{ll}\beta & \text{if }x=\alpha \\ 0& \text{otherwise}\end{array}}$

and the other program to one that computes

${\displaystyle D_{\alpha ,\beta }(X):=\{\begin{array}{ll}1& \text{if }X(\alpha )=\beta \text{ and }X\text{ runs in time}\le \text{poly}(k)\\ 0& \text{otherwise}\end{array}.}$

(Here, ${\displaystyle D_{\alpha ,\beta }}$ interprets its input as the code for a Turing machine. The second condition in the definition of ${\displaystyle D_{\alpha ,\beta }}$ is to prevent the function from being uncomputable.)

If an efficient attacker only has black-box access, Barak et al. argued, then the attacker only has an exponentially small chance of guessing the password ${\displaystyle \alpha }$, and so cannot distinguish the pair of programs from a pair where ${\displaystyle C_{\alpha ,\beta }}$ is replaced by some program ${\displaystyle Z}$ that always outputs "0". However, if the attacker has access to any obfuscated implementations ${\displaystyle C_{\alpha ,\beta }^{\prime },D_{\alpha ,\beta }^{\prime }}$ of ${\displaystyle C_{\alpha ,\beta },D_{\alpha ,\beta }}$, then the attacker will find ${\displaystyle D_{\alpha ,\beta }^{\prime }(C_{\alpha ,\beta }^{\prime })=1}$ with probability 1, whereas the attacker will always find ${\displaystyle D_{\alpha ,\beta }^{\prime }(Z)=0}$ unless ${\displaystyle \beta =0}$ (which should happen with negligible probability). This means that the attacker can always distinguish the pair ${\displaystyle (C_{\alpha ,\beta }^{\prime },D_{\alpha ,\beta }^{\prime })}$ from the pair ${\displaystyle (Z,D_{\alpha ,\beta }^{\prime })}$ with obfuscated code access, but not black-box access. Since no obfuscator can prevent this attack, Barak et al. conclude that no black-box obfuscator for pairs of programs exists.

To conclude the argument, Barak et al. define a third program to implement the functionality of the two previous:

${\displaystyle F_{\alpha ,\beta }(b,x):=\{\begin{array}{ll}{C}_{\alpha ,\beta }(x)& \text{if }b=0\\ D_{\alpha ,\beta }(x)& \text{if }b=1\end{array}.}$

Since equivalently efficient implementations of ${\displaystyle C_{\alpha ,\beta },D_{\alpha ,\beta }}$ can be recovered from one of ${\displaystyle F_{\alpha ,\beta }}$ by hardwiring the value of ${\displaystyle b}$, Barak et al. conclude that ${\displaystyle F_{\alpha ,\beta }}$ cannot be obfuscated either, which concludes their argument.

Impossible variants of black-box obfuscation and other types of unobfuscatable programs

In their paper, Barak et al. also prove the following (conditional to appropriate cryptographic assumptions):

• There are unobfuscatable circuits.
• There is no black-box approximate obfuscator.
• There are unobfuscatable, secure, probabilistic private-key cryptosystems.
• There are unobfuscatable, secure, deterministic digital signature schemes.
• There are unobfuscatable, secure, deterministic message authentication schemes.
• There are unobfuscatable, secure pseudorandom functions.
• For many protocols that are secure in the random oracle model, the protocol becomes insecure if the random oracle is replaced with an artificial cryptographic hash function; in particular, Fiat-Shamir schemes can be attacked.
• There are unobfuscatable circuits in TC0 (that is, constant-depth threshold circuits).
• There are unobfuscatable sampling algorithms (in fact, these cannot be obfuscated approximately).
• There is no secure software watermarking scheme.