Paper 2013/781

Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings

Rafael Pass, Karn Seth, and Sidharth Telang

Abstract

We define a notion of semantic security of multilinear (a.k.a. graded) encoding schemes, which stipulates security of class of algebraic ``decisional'' assumptions: roughly speaking, we require that for every nuPPT distribution $D$ over two \emph{constant-length} sequences $\vec{m}_0,\vec{m}_1$ and auxiliary elements $\vec{z}$ such that all arithmetic circuits (respecting the multilinear restrictions and ending with a zero-test) are \emph{constant} with overwhelming probability over $(\vec{m}_b, \vec{z})$, $b \in \{0,1\}$, we have that encodings of $\vec{m}_0, \vec{z}$ are computationally indistinguishable from encodings of $\vec{m}_1, \vec{z}$. Assuming the existence of semantically secure multilinear encodings and the LWE assumption, we demonstrate the existence of indistinguishability obfuscators for all polynomial-size circuits. We additionally show that if we assume subexponential hardness, then it suffices to consider a \emph{single} (falsifiable) instance of semantical security (i.e., that semantical security holds w.r.t to a particular distribution $D$) to obtain the same result. We rely on the beautiful candidate obfuscation constructions of Garg et al (FOCS'13), Brakerski and Rothblum (TCC'14) and Barak et al (EuroCrypt'14) that were proven secure only in idealized generic multilinear encoding models, and develop new techniques for demonstrating security in the standard model, based only on semantic security of multilinear encodings (which trivially holds in the generic multilinear encoding model). We also investigate various ways of defining an ``uber assumption'' (i.e., a super-assumption) for multilinear encodings, and show that the perhaps most natural way of formalizing the assumption that ``any algebraic decision assumption that holds in the generic model also holds against nuPPT attackers'' is false.