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 of a fixed, pre-determined length , define one program to be one that computes

and the other program to one that computes

(Here, interprets its input as the code for a Turing machine. The second condition in the definition of 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 , and so cannot distinguish the pair of programs from a pair where is replaced by some program that always outputs "0". However, if the attacker has access to any obfuscated implementations of , then the attacker will find with probability 1, whereas the attacker will always find unless (which should happen with negligible probability). This means that the attacker can always distinguish the pair from 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 can be recovered from one of by hardwiring the value of , Barak et al. conclude that 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]

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, 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. 1 2 3 4 5 6 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. 1 2 "Cryptographic obfuscation and 'unhackable' software". A Few Thoughts on Cryptographic Engineering. 2014-02-21. Retrieved 2021-03-14.
  4. 1 2 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.