International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Prabhanjan Ananth
Aayush Jain
Huijia Lin
Christian Matt
Amit Sahai
DOI: 10.1007/978-3-030-26954-8_10 (login may be required)
Search ePrint
Search Google
Abstract: The existence of secure indistinguishability obfuscators ( $$i\mathcal {O}$$ ) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing $$i\mathcal {O}$$ 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 $$i\mathcal {O}$$ for general circuits. Unlike all previously known realizations of $$i\mathcal {O}$$ , 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 ( $$\varDelta $$ RG) and pseudo flawed-smudging generator ( $$\mathrm {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 $$i\mathcal {O}$$ for general circuits assuming:Subexponentially secure LWEBilinear Maps $$\mathrm {poly}(\lambda )$$ -secure 3-block-local PRGs $$\varDelta $$ RGs or $$\mathrm {PFG}$$ s
Video from CRYPTO 2019
  title={Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Prabhanjan Ananth and Aayush Jain and Huijia Lin and Christian Matt and Amit Sahai},