Cryptology ePrint Archive: Report 2013/781

Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings

Rafael Pass and Karn Seth and Sidharth Telang

Abstract: We define a notion of semantic security of multilinear (a.k.a. graded) encoding schemes, which generalizes a multilinear DDH assumption: roughly speaking, we require that if two constant-length sequences $\vec{m}_0$, $\vec{m}_1$ are \emph{pointwise statistically indistinguishable} by algebraic attackers $C$ (obeying the multilinear restrictions) in the presence of some other elements $\vec{z}$, then encodings of these sequences should be computationally indistinguishable. 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 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).

Category / Keywords: cryptographic protocols / obfuscation, semantically secure, multilinear encodings

Date: received 22 Nov 2013, last revised 12 Mar 2014

Contact author: sidtelang at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20140312:200411 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]