Abstract:
At least since the initial public proposal of public-key cryptography based on computational hardness conjectures (Diffie and Hellman, 1976), cryptographers have contemplated the possibility of a “one-way compiler” that translates computer programs into “incomprehensible” but equivalent forms. And yet, the search for such a “one-way compiler” remained elusive for decades.
In this talk, we look back at our community’s attempts to formalize the notion of such a compiler, culminating in our 2001 work with Barak, Goldreich, Impagliazzo, Rudich, Vadhan, and Yang, which proposed the notion of indistinguishability obfuscation (iO). Roughly speaking, iO requires that the compiled versions of any two equivalent programs (with the same size and running time) be indistinguishable to any efficient adversary. The notion of punctured programming, introduced in our work with Waters in 2013, spawned an area of research dedicated to exploring the remarkable power of iO.
We’ll then discuss the intense effort that recently culminated in our 2020 work with Jain and Lin, finally showing how to construct iO in such a way that, for the first time, we can prove the security of our iO scheme based on well-studied computational hardness conjectures in cryptography.

Bio: 
Amit Sahai is a Professor of Computer Science and (by courtesy) Mathematics at UCLA, and the incumbent of the Symantec Endowed Chair in Computer Science. He also serves as an Advisor to the Prison Mathematics Project. His primary research interests are in cryptography, coding theory, complexity theory, and security. He is the co-inventor of attribute-based encryption, functional encryption, and indistinguishability obfuscation. He was an invited lecturer at the 2022 International Congress of Mathematicians (ICM 2022, Special Sectional Lecture), and received the 2022 National Academy of Sciences Held Prize for his role in the development of indistinguishability obfuscation. His research works have been recognized by four Test of Time Awards (FOCS 2023, Eurocrypt 2023, Eurocrypt 2020, ACM CCS 2016) and a STOC 2021 Best Paper Award. For his teaching, he was given the 2016 Lockheed Martin Excellence in Teaching Award from the Samueli School of Engineering at UCLA. Many years ago, he was a member of the 1996 World Champion ACM ICPC Team from UC Berkeley. He is also a Simons Investigator (2021), Fellow of the ACM (2018), Fellow of the IACR (2019), and Fellow of the AMS (2024).