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 far-reaching 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 degree-3 polynomials over $\mathbb{Z}$. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming 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 3-block-local PRGs \item $(1-1/\poly(\lambda))$-secure $\Delta\mathsf{RG}$s \end{itemize}

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Indistinguishability Obfuscation
Contact author(s)
prabhanjan va @ gmail com
aayushjainiitd @ gmail com
sahai @ cs ucla edu
History
2018-12-25: last of 7 revisions
2018-06-22: received
See all versions
Short URL
https://ia.cr/2018/615
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.