Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
, Cornell University
Date: Tuesday, March 18, 2014
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Host: Prof Silvio Micali
Contact: Holly A Jones, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/534
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
TALK: Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
The goal of program obfuscation is to "scramble" a computer program, hiding its implementation details while preserving functionality. Unfortunately, the "dream" notion of security, guaranteeing that obfuscated code does not reveal any information beyond black-box access to the original program, has run into strong impossibility results, and is known to be unachievable for general programs (Barak et al, JACM 2012). Recently, the first plausible candidate for general-purpose obfuscation was presented (Garg et al, FOCS 2013) for a relaxed notion of security, referred to as indistinguishability obfuscation; this notion, which requires that obfuscations of functionally equivalent programs are indistinguishable, still suffices for many important applications of program obfuscation.
We present a new hardness assumption---the existence of semantically secure multilinear encodings---which generalizes a multilinear DDH assumption and demonstrate the existence of indistinguishability obfuscation for all polynomial-size circuits under this assumption (and the LWE assumption). We rely on the beautiful candidate obfuscation constructions of Garg et al (FOCS13), Brakerski and Rothblum (TCC14) and Barak et al (EuroCrypt14) that were proven secure only in idealized generic multilinear encoding models, and develop new techniques for demonstrating security in the standard model, based on semantic security of multilinear encodings (which trivially holds in the generic multilinear encoding model).
Joint work with Karn Seth and Sidharth Telang
Created by Holly A Jones at Wednesday, March 12, 2014 at 12:38 PM.