Computer Sciences Colloquium: The Power of Unreadable Code

Abstract: 

The purpose of obfuscation is to recompile programs in a way that preserves their functionality but hides associated secret information, such as secret keys or passwords used by the programs. Envisioned by Diffie and Hellman already in the 70’s as a means of obtaining public-key encryption, it is known by now that this concept may have far reaching implications to cryptography and complexity theory. In particular, program obfuscation suggests (often exclusive) solutions to some of the most challenging privacy and security problems in the age of cloud computing and social networks. At the same time, program obfuscation has turned out to be an evasive goal to achieve, or to even meaningfully define. For a long time, solutions have been confined to heuristics, whereas attempts to achieve any sense of provable security have mostly led to impossibility results. This gloomy state dramatically changed in recent years, when it was shown that a relatively weak notion called indistinguishability obfuscation may be within reach (so far, based on strong computational assumptions) and still has the potential of realizing many dream applications. In this talk, I will review the different aspects of obfuscation, including central notions, limitations, and feasibility. As a demonstration of the power of obfuscation, I will present a recent implication [Bitansky-Paneth-Rosen, FOCS15] that goes beyond cryptography into a fundamental problem in complexity and algorithmic game theory --- the hardness of finding a Nash equilibrium. I will conclude with the main open problems and challenges in the area of obfuscation. Bio: Nir Bitansky is a postdoctoral associate at MIT CSAIL. He earned his Ph.D in computer science from Tel-Aviv University. His research is centered around cryptography and its interplay with complexity theory.