Paper 2019/643

Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification

Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, 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. 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