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 \alpha, \beta of a fixed, pre-determined length k, define one program to be one that computes C_{\alpha, \beta}(x) := \begin{cases} \beta & \text{if }x = \alpha\\ 0 & \text{otherwise} \end{cases} and the other program to one that computes D_{\alpha, \beta}(X) := \begin{cases} 1 & \text{if }X(\alpha) = \beta\text{ and }X\text{ runs in time}\leq\text{poly}(k)\\ 0 & \text{otherwise} \end{cases}. (Here, D_{\alpha, \beta} interprets its input as the code for a
Turing machine. The second condition in the definition of 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 \alpha, and so cannot distinguish the pair of programs from a pair where C_{\alpha, \beta} is replaced by some program Z that always outputs "0". However, if the attacker has access to any obfuscated implementations C'_{\alpha, \beta}, D'_{\alpha, \beta} of C_{\alpha, \beta}, D_{\alpha, \beta}, then the attacker will find D'_{\alpha, \beta}(C'_{\alpha, \beta}) = 1 with probability 1, whereas the attacker will always find D'_{\alpha, \beta}(Z) = 0 unless \beta = 0 (which should happen with negligible probability). This means that the attacker can always distinguish the pair (C'_{\alpha, \beta}, D'_{\alpha, \beta}) from the pair (Z, D'_{\alpha, \beta}) 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: F_{\alpha, \beta}(b, x):= \begin{cases} C_{\alpha, \beta}(x) &\text{if } b = 0\\ D_{\alpha, \beta}(x) &\text{if } b = 1\\ \end{cases}. Since equivalently efficient implementations of C_{\alpha, \beta}, D_{\alpha, \beta} can be recovered from one of F_{\alpha, \beta} by hardwiring the value of b, Barak et al. conclude that 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. == Weaker variants ==