2014 | OriginalPaper | Chapter
Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
Authors : Zvika Brakerski, Guy N. Rothblum
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a new general-purpose obfuscator for all polynomial size circuits. The obfuscator uses graded encoding schemes, a generalization of multilinear maps. We prove that the obfuscator exposes no more information than the program’s black-box functionality, and achieves
virtual black-box security
, in the generic graded encoded scheme model. This proof is under the Bounded Speedup Hypothesis (BSH, a plausible worst-case complexity-theoretic assumption related to the Exponential Time Hypothesis), in addition to standard cryptographic assumptions. We also prove that it satisfies the notion of
indistinguishability obfuscation
without without relying on BSH (in the same generic model and under standard cryptographic assumptions).
Very recently, Garg et al. (FOCS 2013) used graded encoding schemes to present a candidate obfuscator for indistinguishability obfuscation. They posed the problem of constructing a provably secure indistinguishability obfuscator in the generic graded encoding scheme model. Our obfuscator resolves this problem (indeed, under BSH it achieves the stronger notion of virtual black box security, which is our focus in this work).
Our construction is different from that of Garg et al., but is inspired by it, in particular by their use of permutation branching programs. We obtain our obfuscator by developing techniques used to obfuscate d-CNF formulas (ITCS 2014), and applying them to permutation branching programs. This yields an obfuscator for the complexity class
$\mathcal{NC}^1$
. We then use homomorphic encryption to obtain an obfuscator for any polynomialsize circuit.