Black-box obfuscation

In cryptography, black-box obfuscation was a proposed cryptographic primitive which would allow a computer program to be obfuscated in a way such that it was impossible to determine anything about it except its input and output behavior.^[1] Black-box obfuscation has been proven to be impossible, even in principle.^[2]

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.^[2][3]

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{cases}\beta &{\text{if }}x=\alpha \\0&{\text{otherwise}}\end{cases}}}$

and the other program to one that computes

${\displaystyle 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, ${\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 },D'_{\alpha ,\beta }}$ of ${\displaystyle C_{\alpha ,\beta },D_{\alpha ,\beta }}$, then the attacker will find ${\displaystyle D'_{\alpha ,\beta }(C'_{\alpha ,\beta })=1}$ with probability 1, whereas the attacker will always find ${\displaystyle D'_{\alpha ,\beta }(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 },D'_{\alpha ,\beta })}$ from the pair ${\displaystyle (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.^[2][3]

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{cases}C_{\alpha ,\beta }(x)&{\text{if }}b=0\\D_{\alpha ,\beta }(x)&{\text{if }}b=1\\\end{cases}}.}$

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.^[2]

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

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

• 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

In their original paper exploring black-box obfuscation, Barak et al. defined two weaker notions of cryptographic obfuscation which they did not rule out: indistinguishability obfuscation and extractability obfuscation (which they called "differing-inputs obfuscation".) Informally, an indistinguishability obfuscator should convert input programs with the same functionality into output programs such that the outputs cannot be efficiently related to the inputs by a bounded attacker, and an extractability obfuscator should be an obfuscator such that if the efficient attacker could relate the outputs to the inputs for any two programs, then the attacker could also produce an input such that the two programs being obfuscated produce different outputs. (Note that an extractability obfuscator is necessarily an indistinguishability obfuscator.) ^[2][4]

As of 2020^[update], a candidate implementation of indistinguishability obfuscation is under investigation.^[5] In 2013, Boyle et al. explored several candidate implementations of extractability obfuscation.^[4]

References

1. Goldwasser, Shafi; Rothblum, Guy N. (2014-07-01). "On Best-Possible Obfuscation" (PDF). Journal of Cryptology. 27 (3): 480–505. doi:10.1007/s00145-013-9151-z. hdl:1721.1/129413. ISSN 1432-1378. S2CID 1186014.
2. Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (2012-05-03). "On the (im)possibility of obfuscating programs" (PDF). Journal of the ACM. 59 (2): 6:1–6:48. doi:10.1145/2160158.2160159. ISSN 0004-5411. S2CID 2409597.
3. "Cryptographic obfuscation and 'unhackable' software". A Few Thoughts on Cryptographic Engineering. 2014-02-21. Retrieved 2021-03-14.
4. Boyle, Elette; Chung, Kai-Min; Pass, Rafael (2013). "On Extractability (a.k.a. Differing-Inputs) Obfuscation". Cryptology ePrint Archive.
5. Klarreich, Erica (November 10, 2020). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine. Retrieved 2020-11-10.