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 (ePrint 2013), and applying them to permutation branching programs. This yields an obfuscator for the complexity class $NC^1$. We then use homomorphic encryption to obtain an obfuscator for any polynomial-size circuit.Category / Keywords: secret-key cryptography / Obfuscation Date: received 4 Sep 2013, last revised 30 Sep 2013 Contact author: rothblum at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20130930:144231 (All versions of this report) Discussion forum: Show discussion | Start new discussion