Cryptology ePrint Archive: Report 2016/257

Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes

Huijia Lin

Abstract: We construct a general-purpose indistinguishability obfuscation (IO) scheme for all polynomial-size circuits from {\em constant-degree} graded encoding schemes in the plain model, assuming the existence of a subexponentially secure Pseudo-Random Generator (PRG) computable by constant-degree arithmetic circuits (or equivalently in $\NC^0)$, and the subexponential hardness of the Learning With Errors (LWE) problems. In contrast, previous general-purpose IO schemes all rely on polynomial-degree graded encodings.

Our general-purpose IO scheme is built upon two key components:

\begin​{itemize} \item a new bootstrapping theorem that subexponentially secure IO for a subclass of {\em constant-degree arithmetic circuits} implies IO for all polynomial size circuits (assuming PRG and LWE as described above), and

\item a new construction of IO scheme for any generic class of circuits in the ideal graded encoding model, in which the degree of the graded encodings is bounded by a variant of the degree, called type degree, of the obfuscated circuits. \end{itemize}

In comparison, previous bootstrapping theorems start with IO for $\NC^1$, and previous constructions of IO schemes require the degree of graded encodings to grow polynomially in the size of the obfuscated circuits.

Category / Keywords: Indistinguishability Obfuscation, Graded Encoding Scheme, Constant Degree, PRG

Original Publication (with major differences): IACR-EUROCRYPT-2016

Date: received 7 Mar 2016, last revised 7 Mar 2016

Contact author: rachel lin at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20160308:201051 (All versions of this report)

Short URL: ia.cr/2016/257