Rafael Pass guest speaker

Tuesday, March 18, 2014 - 4:15pm to 5:15pm

Refreshments:

3:45pm in 32-G449 (Patil/Kiva)

Location:

32-G449 (Patil/Kiva)

Speaker:

Rafael Pass, Cornell University

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