DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2017.38

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Authors: Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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 (IO) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property for two single-input 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 NC1 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,'' (albeit somewhat artificially crafted) used to obtain obfuscations for all circuits (given an obfuscator for NC1 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.

Cite as

Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{apon_et_al:LIPIcs.ICALP.2017.38,
  author =	{Apon, Daniel and D\"{o}ttling, Nico and Garg, Sanjam and Mukherjee, Pratyay},
  title =	{{Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.38},
  URN =		{urn:nbn:de:0030-drops-73814},
  doi =		{10.4230/LIPIcs.ICALP.2017.38},
  annote =	{Keywords: Obfuscation, Multilinear Maps, Cryptanalysis.}
}

Search Results

Documents authored by Apon, Daniel

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Abstract

Cite as

Thanks for your feedback!

Could not send message