Indistinguishability Obfuscation from Well-Founded Assumptions (via Zoom)

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 the subexponential hardness of four well-founded assumptions. We prove:

Theorem (Informal) Assume sub-exponential hardness of the following assumptions: 

  1. the Learning With Errors (LWE) assumption with subexponential modulus-to-noise ratio,
  2. the Learning Parity with Noise (LPN) assumption with inverse polynomial error rate,
  3. the existence of a Boolean Pseudo-Random Generator (PRG) in NC0 with polynomial stretch,
  4. the Decision Linear (DLIN) assumption on symmetric bilinear groups.

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.

Bio: Huijia (Rachel) Lin is an Associate Professor in the Paul G. Allen School of Computer Science and Engineering at the University of Washington, where she co-leads the Cryptography Lab. Before joining the University of Washington, she was an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. Earlier, she obtained a PhD in Computer Science from Cornell University, and was a post-doctoral researcher at MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and Department of Computer Science at Boston University.

Her research interests are in Cryptography, and broadly its interplay with theory of computer science and security. She is a recipient of a US National Science Foundation CAREER award, a Hellman Fellowship, a JP Morgan Faculty award, and a Microsoft Research PhD Fellowship. She won a best paper award honorable mention at Eurocrypt 2016, a best paper award at Eurocrypt 2018, and a best paper award at STOC 2021.