On the impossibility of approximate obfuscation and applications to resettable cryptography
Nir Bitansky, Omer Paneth · 2013
The traditional notion of program obfuscation requires that an obfuscation ~Prog of a program Prog computes the exact same function as Prog, but beyond that, the code of ~Prog should not leak any information about Prog. This strong notion of virtual black-box security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain unobfuscatable function families. The same work raised the question of approximate obfuscation, where the obfuscated ~Prog is only required to approximate Prog; that is, ~Prog only agrees with Prog with high enough probability on some input distribution.