Abstract: Program obfuscation that makes computer programs unintelligible while preserving their functionality is a longstanding goal in cryptography. Recently, Garg et. al. (FOCS'13) proposed a beautiful candidate indistinguishability obfuscator (IO) for all polynomial-size circuits. Their candidate, as well as all follow up proposals, relies on the powerful tool of graded encoding schemes (a.k.a., approximate multilinear maps) that support computations of arbitrary polynomial degree.
In this work, we significantly weaken the requirement on underlying graded encoding schemes: We propose a new candidate IO for all polynomial-size circuits based on a graded encoding scheme supporting only constant degree computations, assuming the existence of a subexponentially secure pseudorandom generator computable by constant-degree arithmetic circuits, and the subexponential hardness of the Learning With Errors (LWE) problem.
Bio: Huijia (Rachel) Lin is an Assistant Professor in the Department of Computer Science at University of California, Santa Barbara (UCSB), where she co-leads the Cryptography Lab. Before joining UCSB, she was a post-doctoral researcher at MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and Department of Computer Science at Boston University. Earlier, she obtained a PhD in Computer Science from Cornell University. Her research interests are in Cryptography, and broadly its interplay with theory of computer science and security.