Welcome to the resource topic for 2016/257
Title:
Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes
Authors: 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.
ePrint: https://eprint.iacr.org/2016/257
Talk: https://www.youtube.com/watch?v=h7YrCU1ge3Q
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .