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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. Black-box obfuscation has been proven to be impossible, even in principle.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1279426731 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.