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


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

Available format(s)
Publication info
Published by the IACR in CRYPTO 2019
Contact author(s)
prabhanjan @ csail mit edu
aayushjain @ cs ucla edu
rachel @ cs washington edu
cm @ concordium com
sahai @ cs ucla edu
2019-09-16: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Aayush Jain and Huijia Lin and Christian Matt and Amit Sahai},
      title = {Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification},
      howpublished = {Cryptology ePrint Archive, Paper 2019/643},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.