Paper 2016/147

Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13

Eric Miles, Amit Sahai, and Mark Zhandry

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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2016
Contact author(s)
amitsahai @ gmail com
History
2016-06-07: last of 2 revisions
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/147
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/147,
      author = {Eric Miles and Amit Sahai and Mark Zhandry},
      title = {Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13},
      howpublished = {Cryptology ePrint Archive, Paper 2016/147},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/147}},
      url = {https://eprint.iacr.org/2016/147}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.