- About
- Events
- Calendar
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- BOOM
- Spring 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2023 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Monday, May 17, 2021 - 16:00 to 17:00
Streaming via Zoom
Host:
Noah Stephens-Davidowitz
Categories:
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:
- the Learning With Errors (LWE) assumption with subexponential modulus-to-noise ratio,
- the Learning Parity with Noise (LPN) assumption with inverse polynomial error rate,
- the existence of a Boolean Pseudo-Random Generator (PRG) in NC0 with polynomial stretch,
- 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.