Indistinguishability Obfuscation from Well-Founded Assumptions

URL: https://dl.acm.org/doi/10.1145/3406325.3451093 Authors: Aayush Jain, Huijia Lin, Amit Sahai

Abstract

In this work, we show how to construct indistinguishability obfuscation (iO) from the sub-exponential security of four well-studied hardness assumptions: the Learning With Errors (LWE) assumption, the Learning Parity with Noise (LPN) assumption, an assumption about the existence of a Boolean Pseudorandom Generator (PRG) in ${\mathsf{NC}}^1$, and the decision Diffie-Hellman (DDH) assumption over specific groups. This gives the first construction of iO from assumptions that do not involve multilinear maps or other newly-introduced objects.