Paper 2018/615
Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness
Prabhanjan Ananth, Aayush Jain, and Amit Sahai
Abstract
The existence of secure indistinguishability obfuscators (iO) has farreaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing iO rely on $d$linear maps which allow the encoding of elements from a large domain, evaluating degree $d$ polynomials on them, and testing if the output is zero. While secure bilinear maps are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood. We propose a new approach to constructing iO for general circuits. Unlike all previously known realizations of iO, we avoid the use of $d$linear maps of degree $d \ge 3$. At the heart of our approach is the assumption that a new weak pseudorandom object exists, that we call a perturbation resilient generator ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps $n$ integers to $m$ integers, and has the property that for any sufficiently short vector $a \in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and ($\Delta\mathsf{RG}(s)+a$), with at least some probability that is inverse polynomial in the security parameter. $\Delta\mathsf{RG}$s have further implementability requirements; most notably they must be computable by a family of degree3 polynomials over $\mathbb{Z}$. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but nonoverwhelming distinguishing advantage. In particular, we obtain a new security amplification theorem for functional encryption. As a result, we obtain iO for general circuits assuming: \begin{itemize} \item Subexponentially secure LWE \item Bilinear Maps \item $\poly(\lambda)$secure 3blocklocal PRGs \item $(11/\poly(\lambda))$secure $\Delta\mathsf{RG}$s \end{itemize}
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Indistinguishability Obfuscation
 Contact author(s)

prabhanjan va @ gmail com
aayushjainiitd @ gmail com
sahai @ cs ucla edu  History
 20181225: last of 7 revisions
 20180622: received
 See all versions
 Short URL
 https://ia.cr/2018/615
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/615, author = {Prabhanjan Ananth and Aayush Jain and Amit Sahai}, title = {Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness}, howpublished = {Cryptology ePrint Archive, Paper 2018/615}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/615}}, url = {https://eprint.iacr.org/2018/615} }