There was an elegant proof given at one of the HRL seminars last year
that any obfuscator can be beaten.
Are you speaking of the work by Boaz Barak et al. (http://www.wisdom.weizmann.ac.il/~boaz/Papers/obfuscate.ps)?
If so, your summary is a bit misleading: that fascinating work shows that there is no "universal" obfuscation procedure that can perfectly obfuscate any algorithm. It does show by showing that certain properties inherently "show through" any obfuscation [1], hence no obfuscation is perfect. However, this does not rule out the existence of "imperfect" or "selective" obfuscation that hides (other) specific properties, such as people's precious intellectual property.
Eran
[1] Informally, obfuscation here means that "for any function F, any property of F that can be efficiently learned from an obfuscated Turing machine implementing F can also be efficiently learned using just oracle access to F". This would be the ideal, since it means that that the obfuscated TM is essentially a black box -- the only power you get from seeing it is the ability to run it. The impossibility of such universal obfuscation follows from looking at properties such as "F(X)=1 whenever X is a description of a Turing machine implementing F". If you have a Turing machine implementing F then you can trivially find out if F has that property, but not so if you only have oracle access to F.
================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
