Welcome to the resource topic for 2018/615
Title:
Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness
Authors: Prabhanjan Ananth, Aayush Jain, 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}
ePrint: https://eprint.iacr.org/2018/615
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .