Paper 2016/1003 Original: eprint.iacr.org/2016/1003 ↗

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Abstract

Annihilation attacks, introduced in the work of Miles, Sahai, and Zhandry (CRYPTO 2016), are a class of polynomial-time attacks against several candidate indistinguishability obfuscation ($i\mathcal{O}$) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property of two branching programs, called ``partial inequivalence'', which we show is sufficient for our variant of annihilation attacks on several obfuscation constructions based on GGH13 multilinear maps. We give examples of pairs of natural $\mathsf{NC}^1$ circuits, which -- when processed via Barrington's Theorem -- yield pairs of branching programs that are partially inequivalent. As a consequence we are also able to show examples of ``bootstrapping circuits,'' used to obtain obfuscations for all circuits (given an obfuscator for $\mathsf{NC}^1$ circuits), in certain settings also yield partially inequivalent branching programs. Prior to our work, no attacks on any obfuscation constructions for these settings were known.