Huijia (Rachel) Lin: Indistinguishability Obfuscation from Well-Founded Assumptions

Speaker: Huijia (Rachel) Lin

Date: Tuesday, November 17, 2020

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Zoom Link: https://mit.zoom.us/meeting/register/tJIlceuqrzMoGdyQJAyITXLXnN6t5C1ZEDnf

Event Type:

Room Description:

Host: Yael Kalai

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
Head shot

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

Reminder Subject: TALK: Huijia (Rachel) Lin: Indistinguishability Obfuscation from Well-Founded Assumptions

Pre Registration for seminar mandatory, please register at least 24 hours prior to seminar.
Abstract:
Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions.

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:

Theorem (Informal) Let p be a prime of magnitude \Theta(2^n), where n is the security parameter. Assume sub-exponential security of the following assumptions:

the Learning With Errors (LWE) assumption over Z_p with subexponential modulus-to-noise ratio,

the Learning Parity with Noise (LPN) assumption over Z_p with polynomially many LPN samples and inverse polynomial error rate,

the existence of a Boolean Pseudo-Random Generator (PRG) in NC0 with polynomial stretch,

the Symmetric eXternal Diffie-Hellman (SXDH) assumption on asymmetric bilinear groups of order p.

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.

Joint work with Aayush Jain and Amit Sahai at UCLA.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2020.

Created by Deborah Goodwin Email at Wednesday, November 11, 2020 at 1:27 PM.