## Cryptology ePrint Archive: Report 2013/781

Obfuscation from Semantically-Secure Multi-linear Encodings

Rafael Pass and Sidharth Telang and Karn Seth

Abstract: We define a notion of semantic security of multi-linear (a.k.a. graded) encoding schemes: roughly speaking, we require that if an algebraic attacker (obeying the multi-linear restrictions) cannot tell apart two constant-length sequences $\vec{m}_0$, $\vec{m}_1$ in the presence of some other elements $\vec{z}$, then encodings of these sequences should be indistinguishable. Assuming the existence of semantically secure multi-linear 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 (ePrint'13) 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 multi-linear encoding (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 10 Feb 2014

Contact author: sidtelang at cs cornell edu, rafael@cs cornell edu, karn@cs cornell edu

Available format(s): PDF | BibTeX Citation

[ Cryptology ePrint archive ]