Paper 2020/1003
Indistinguishability Obfuscation from WellFounded Assumptions
Aayush Jain, Huijia Lin, and Amit Sahai
Abstract
Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four wellfounded assumptions. We prove: Theorem: Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume subexponential security of the following assumptions, where $\lambda$ is a security parameter, $p$ is a $\lambda$bit prime, and the parameters $\ell,k,n$ are large enough polynomials in $\lambda$:  the Learning With Errors ($\mathsf{LWE}$) assumption over $\mathbb{Z}_p$ with subexponential modulustonoise ratio $2^{k^\epsilon}$, where $k$ is the dimension of the $\mathsf{LWE}$ secret,  the Learning Parity with Noise ($\mathsf{LPN}$) assumption over $\mathbb{Z}_p$ with polynomially many $\mathsf{LPN}$ samples and error rate $1/\ell^\delta$, where $\ell$ is the dimension of the $\mathsf{LPN}$ secret,  the existence of a Boolean PseudoRandom Generator ($\mathsf{PRG}$) in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$, where $n$ is the length of the $\mathsf{PRG}$ seed,  the Symmetric eXternal DiffieHellman ($\mathsf{SXDH}$) assumption on asymmetric bilinear groups of order $p$. Then, (subexponentially secure) indistinguishability obfuscation for all polynomialsize circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant publickey functional encryption for all polynomialsize circuits.
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
 20201112: revised
 20200819: received
 See all versions
 Short URL
 https://ia.cr/2020/1003
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1003, author = {Aayush Jain and Huijia Lin and Amit Sahai}, title = {Indistinguishability Obfuscation from WellFounded Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1003}, year = {2020}, url = {https://eprint.iacr.org/2020/1003} }