IACR News item: 08 March 2016
Huijia Lin
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.