Welcome to the resource topic for 2019/643
Title:
Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification
Authors: Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, 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. 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. We consider two related variants of these objects, which we call perturbation resilient generator ($\Delta$RG) and pseudo flawed-smudging generator (PFG), respectively. At a high level, both objects are polynomially expanding functions whose outputs partially hide (or smudge) small noise vectors when added to them. We further require that they are computable by a family of degree-3 polynomials over \mathbb{Z}. We show how they can be used to construct functional encryption schemes with weak security guarantees. Finally, we use novel amplification techniques to obtain full security. As a result, we obtain iO for general circuits assuming: - Subexponentially secure LWE - Bilinear Maps - \textrm{poly}(\lambda)-secure 3-block-local PRGs - $\Delta$RGs or PFGs
ePrint: https://eprint.iacr.org/2019/643
Talk: https://www.youtube.com/watch?v=_Rr_m9RxG7U
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 .