Cryptology ePrint Archive: Report 2018/615

Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness

Prabhanjan Ananth and Aayush Jain 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 \emph{$d$-linear maps} which allow the encoding of elements from a large domain, evaluating degree $d$ polynomials on them, and testing if the output is zero. While secure \emph{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 \emph{weak} pseudorandom object exists, that we call a \emph{perturbation resilient generator} ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps $n$ integers to $m$ integers, and has the property that for any sufficiently short vector $a \in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and $\Delta\mathsf{RG}(s)+a$, with at least some probability that is inverse polynomial in the security parameter. $\Delta\mathsf{RG}s$ have further implementability requirements; most notably they must be computable by a family of degree-3 polynomials over $\mathbb{Z}$. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. In particular, we obtain a new security amplification theorem for functional encryption.

As a result, we obtain iO for general circuits assuming:

- Subexponentially secure LWE

- Bilinear Maps

- $poly(\lambda)$-secure 3-block-local PRGs

- $(1-1/poly(\lambda))$-secure $\Delta\mathsf{RG}s$

Category / Keywords: Indistinguishability Obfuscation

Date: received 17 Jun 2018, last revised 5 Nov 2018

Contact author: prabhanjanva at gmail com, aayushjainiitd@gmail com, sahai@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20181105:211616 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]