Paper 2020/1003
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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Indistinguishability Obfuscation
- Contact author(s)
- aayushjain @ cs ucla edu,rachel @ cs washington edu,sahai @ cs ucla edu
- History
- 2020-11-12: revised
- 2020-08-19: received
- See all versions
- Short URL
- https://ia.cr/2020/1003
- License
-
CC BY