**Indistinguishability Obfuscation from Well-Founded Assumptions**

*Aayush Jain and Huijia Lin and Amit Sahai*

**Abstract: **In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:
Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $\lambda$:

- The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^\lambda)$,

- The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^\epsilon}$, where $k$ is the dimension of the LWE secret,

- The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^\delta$, where $\ell$ is the dimension of the LPN secret,

- The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$,

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

**Category / Keywords: **foundations / Indistinguishability Obfuscation

**Date: **received 18 Aug 2020

**Contact author: **aayushjain at cs ucla edu,rachel@cs washington edu,sahai@cs ucla edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20200819:105437 (All versions of this report)

**Short URL: **ia.cr/2020/1003

[ Cryptology ePrint archive ]