Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13

Eric Miles, Amit Sahai, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

Abstract

In this work, we present a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks on GGH13 were “zeroizing” attacks that generally required the availability of low-level encodings of zero. Most significantly, such zeroizing attacks were not applicable to candidate indistinguishability obfuscation (iO) schemes. iO has been the subject of intense study. To address this gap, we introduce annihilation attacks, which attack multilinear maps using non-linear polynomials. Annihilation attacks can work in situations where there are no low-level encodings of zero. Using annihilation attacks, we give the first polynomial-time cryptanalysis of candidate iO schemes over GGH13. More specifically, we exhibit two simple programs that are functionally equivalent, and show how to efficiently distinguish between the obfuscations of these two programs. Given the enormous applicability of iO, it is important to devise iO schemes that can avoid attack. We discuss some initial directions for safeguarding against annihilating attacks.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings
EditorsMatthew Robshaw, Jonathan Katz
PublisherSpringer Verlag
Pages629-658
Number of pages30
ISBN (Print)9783662530078
DOIs
StatePublished - Jan 1 2016
Event36th Annual International Cryptology Conference, CRYPTO 2016 - Santa Barbara, United States
Duration: Aug 14 2016Aug 18 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9815
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other36th Annual International Cryptology Conference, CRYPTO 2016
CountryUnited States
CitySanta Barbara
Period8/14/168/18/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13'. Together they form a unique fingerprint.

  • Cite this

    Miles, E., Sahai, A., & Zhandry, M. (2016). Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In M. Robshaw, & J. Katz (Eds.), Advances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings (pp. 629-658). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9815). Springer Verlag. https://doi.org/10.1007/978-3-662-53008-5_22