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] 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
of a fixed, pre-determined length
, define one program to be one that computes
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}}.}
interprets its input as the code for a Turing machine.
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
However, if the attacker has access to any obfuscated implementations
with probability 1, whereas the attacker will always find
(which should happen with negligible probability).
This means that the attacker can always distinguish the pair
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:
Since equivalently efficient implementations of
, Barak et al. conclude that
cannot be obfuscated either, which concludes their argument.
[2] In their paper, Barak et al. also prove the following (conditional to appropriate cryptographic assumptions):[2] 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.