Cryptology ePrint Archive: Report 2019/643

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

Prabhanjan Ananth and Aayush Jain and Huijia Lin and 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

Category / Keywords: Obfuscation

Original Publication (in the same form): IACR-CRYPTO-2019

Date: received 2 Jun 2019

Contact author: prabhanjan at csail mit edu, aayushjain@cs ucla edu, rachel@cs washington edu, cm@concordium com, sahai@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20190603:091759 (All versions of this report)

Short URL: ia.cr/2019/643


[ Cryptology ePrint archive ]