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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
obfuscationsemantically securemultilinear encodings
Contact author(s)
sidtelang @ cs cornell edu
History
2014-07-23: last of 13 revisions
2013-11-25: received
See all versions
Short URL
https://ia.cr/2013/781
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/781,
      author = {Rafael Pass and Karn Seth and Sidharth Telang},
      title = {Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings},
      howpublished = {Cryptology ePrint Archive, Paper 2013/781},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/781}},
      url = {https://eprint.iacr.org/2013/781}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.