You are looking at a specific version 20200917:121314 of this paper. See the latest version.

Paper 2015/025

Obfuscating Circuits via Composite-Order Graded Encoding

Benny Applebaum and Zvika Brakerski

Abstract

We present a candidate obfuscator based on composite-order Graded Encoding Schemes (GES), which are a generalization of multilinear maps. Our obfuscator operates on circuits directly without converting them into formulas or branching programs as was done in previous solutions. As a result, the time and size complexity of the obfuscated program, measured by the number of GES elements, is directly proportional to the circuit complexity of the program being obfuscated. This improves upon previous constructions whose complexity was related to the formula or branching program size. Known instantiations of Graded Encoding Schemes allow us to obfuscate circuit classes of polynomial degree, which include for example families of circuits of logarithmic depth. We prove that our obfuscator is secure against a class of generic algebraic attacks, formulated by a generic graded encoding model. We further consider a more robust model which provides more power to the adversary and extend our results to this setting as well. As a secondary contribution, we define a new simple notion of \emph{algebraic security} (which was implicit in previous works) and show that it captures standard security relative to an ideal GES oracle.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2015
Keywords
ObfuscationGraded Encoding Schemes
Contact author(s)
benny applebaum @ gmail com
History
2020-09-17: last of 2 revisions
2015-01-14: received
See all versions
Short URL
https://ia.cr/2015/025
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.