Paper 2020/1003

Indistinguishability Obfuscation from Well-Founded 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 well-founded assumptions. We prove: Theorem: 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, $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 modulus-to-noise 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 Pseudo-Random 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 Diffie-Hellman ($\mathsf{SXDH}$) assumption on asymmetric bilinear groups of order $p$. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.

Metadata
Available format(s)
PDF
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1003,
      author = {Aayush Jain and Huijia Lin and Amit Sahai},
      title = {Indistinguishability Obfuscation from Well-Founded Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1003},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1003}},
      url = {https://eprint.iacr.org/2020/1003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.