Obfuscators
Professor Rudich told me on Tuesday that he'd recently found a result in cryptography concerning obfuscators, or methods of making programs more difficult to understand. (This is a big deal, of course, in copyright and in DRM -- all sorts of software publishers go to great lengths to make their programs resistent to reverse engineering.) The conclusion reached by Rudich and his collaborators is that obfuscators don't exist, which is to say that a truly secure obfuscator is a theoretical impossibility. The paper announcing this is called "On the (Im)possibility of Obfuscating Programs", by Barak et al.
This doesn't mean that obfuscators can't make things hard to understand (so that someone would have to expend an extra effort to read them), just that they can't, in general, make things impossible to understand -- there is no algorithmic technique which can accomplish that. The abstract says that
an obfuscator O is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications [...] Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible.
