Obfuscating Programs Against Algebraic Attacks

Obfuscating Programs Against Algebraic Attacks - Yael Tauman-Kalai

Yael Tauman-Kalai
Microsoft Research New England
October 14, 2013

The goal of (general-purpose) program obfuscation is to make an arbitrary computer program "unintelligible" while preserving its functionality. The problem of program obfuscation is well studied both in theory and in practice. Though despite its importance, until very recently, even heuristic constructions for general-purpose obfuscation were not known.
In FOCS 2013, Garg et. al. gave the first candidate construction for general-purpose obfuscation. We improve upon this result, by providing a simpler construction, and proving its security against algebraic attacks. This improves a very recent work of Brakerski and Rothblum (eprint 2013), who gave such a result under a strengthening of the Exponential Time Hypothesis.
This is joint work with Boaz Barak, Sanjam Garg, Omer Paneth and Amit Sahai.