Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

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

Paper 2016/1003

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Daniel Apon, Nico Döttling, 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 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 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 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): pratyay85 @ gmail com
History: 2017-06-19: last of 6 revisions; 2016-10-26: received; See all versions
Short URL: https://ia.cr/2016/1003
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1003,
      author = {Daniel Apon and Nico Döttling and Sanjam Garg and Pratyay Mukherjee},
      title = {Cryptanalysis of Indistinguishability Obfuscations of Circuits over {GGH13}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1003},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1003}
}