International Association
for Cryptologic Research

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 {\\em virtual black-box security}, in the generic graded encoded scheme model. This proof is under a plausible worst-case complexity-theoretic assumption related to the Exponential Time Hypothesis, in addition to standard cryptographic assumptions.

Very recently, Garg et al.~(FOCS 2013) used graded encoding schemes to present a candidate obfuscator for the weaker notion of \\emph{indistinguishability obfuscation}, without a proof of security. They posed the problem of constructing a provably secure indistinguishability obfuscator in the generic model. Our obfuscator, which achieves the stronger guarantee of virtual black-box security, resolves this problem (under the complexity assumptions).

Our construction is different from that of Garg et al., but it is inspired by their use of permutation branching programs. We obtain our obfuscator by developing techniques used to obfuscate $d$-CNF formulas (ePrint 2013), and applying them to permutation branching programs. This yields an obfuscator for the complexity class NC1. We then use homomorphic encryption to obtain an obfuscator for any polynomial-size circuit.