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, that we call a 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:
\begin{itemize}
\item Subexponentially secure LWE
\item Bilinear Maps
\item $\poly(\lambda)$-secure 3-block-local PRGs
\item $(1-1/\poly(\lambda))$-secure $\Delta\mathsf{RG}$s
\end{itemize}
Category / Keywords: Indistinguishability Obfuscation Date: received 17 Jun 2018, last revised 24 Dec 2018 Contact author: prabhanjan va at gmail com,aayushjainiitd@gmail com,sahai@cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20181225:014335 (All versions of this report) Short URL: ia.cr/2018/615