Title :
On the impossibility of obfuscation with auxiliary input
Author :
Goldwasser, Shafi ; Kalai, Yael Tauman
Author_Institution :
Weizmann Inst., Rehovot, Israel
Abstract :
Barak et al. formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed how to obfuscate point functions, under various complexity assumptions. Thus, it would seem possible that most programs of interest can be obfuscated even though in principle general purpose obfuscators do not exist. We show that this is unlikely to be the case. In particular; we consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some additional a priori information. This is essentially the case of interest in any usage of obfuscation we can imagine. We prove that there exist many natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated. We also give a positive result. In particular; we show that any obfuscator for the class of point functions is also an obfuscator with independent auxiliary input.
Keywords :
programming theory; additional a priori information; complexity assumption; contrived function class; independent auxiliary input; obfuscate point function; obfuscated circuit; obfuscation impossibility; obfuscation notion; point function class; principle general purpose obfuscator; Boolean functions; Circuits; Context modeling; History; Polynomials; Protocols; Security;
Conference_Titel :
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Print_ISBN :
0-7695-2468-0
DOI :
10.1109/SFCS.2005.60