Obfuscating Programs Against Algebraic Attacks

Computer Science/Discrete Mathematics Seminar I
Topic:Obfuscating Programs Against Algebraic Attacks
Speaker:Yael Tauman-Kalai
Affiliation:Microsoft Research New England
Date:Monday, October 14
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1014-YaelKalai

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.