Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings

Speaker: Rafael Pass , 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

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Prof Silvio Micali

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/534

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, toc@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: 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 (FOCS’13), Brakerski and Rothblum (TCC’14) and Barak et al (EuroCrypt’14) 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

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Holly A Jones at Wednesday, March 12, 2014 at 12:38 PM.