Skip to main content

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

Author(s): Miles, Eric; Sahai, Amit; Zhandry, Mark

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1w55n
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMiles, Eric-
dc.contributor.authorSahai, Amit-
dc.contributor.authorZhandry, Mark-
dc.date.accessioned2021-10-08T19:48:09Z-
dc.date.available2021-10-08T19:48:09Z-
dc.date.issued2016en_US
dc.identifier.citationMiles, Eric, Amit Sahai, and Mark Zhandry. "Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13." In Annual International Cryptology Conference (2016): pp. 629-658. doi:10.1007/978-3-662-53008-5_22en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttps://www.cs.princeton.edu/~mzhandry/docs/papers/Annihilate.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1w55n-
dc.description.abstractIn 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.en_US
dc.format.extent629 - 658en_US
dc.language.isoen_USen_US
dc.relation.ispartofAnnual International Cryptology Conferenceen_US
dc.rightsAuthor's manuscripten_US
dc.titleAnnihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13en_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-662-53008-5_22-
dc.identifier.eissn1611-3349-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
CryptanalysisIndistinguishabilityObfuscation.pdf241.24 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.