### 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.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
Contact author(s)
rachel lin @ cs ucsb edu
History
Short URL
https://ia.cr/2016/257

CC BY

BibTeX

@misc{cryptoeprint:2016/257,
author = {Huijia Lin},
title = {Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes},
howpublished = {Cryptology ePrint Archive, Paper 2016/257},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/257}},
url = {https://eprint.iacr.org/2016/257}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.