Cryptology ePrint Archive: Report 2016/1003

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Daniel Apon and Nico Döttling and Sanjam Garg and Pratyay Mukherjee

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.

Category / Keywords:

Date: received 21 Oct 2016, last revised 18 Jun 2017

Contact author: pratyay85 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170619:052247 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]