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

Speaker: Mark Zhandry

Date: Friday, April 01, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: MIT, Hewlett G882, 32 Vassar St, Gates Tower

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Mark Zhandry: Title: Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13

Abstract: In this work, we put forward a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks on GGH13 generally required the availability of low-level encodings of zero. Most significantly, such attacks were not applicable to candidate indistinguishability obfuscation (iO) schemes.

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. We also show that annihilation attacks are applicable to candidate Order Revealing Encryption schemes built over GGH13.

* Joint work with Eric Miles and Amit Sahai

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Wednesday, March 02, 2016 at 8:23 AM.