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

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
Indistinguishability ObfuscationGraded Encoding SchemeConstant DegreePRG
Contact author(s)
rachel lin @ cs ucsb edu
History
2016-03-08: received
Short URL
https://ia.cr/2016/257
License
Creative Commons Attribution
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.