Akshay Degwekar: Structure vs Hardness Through the Obfuscation Lens

Speaker: Akshay Degwekar, MIT

Date: Friday, September 30, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 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: Akshay Degwekar: Structure vs Hardness Through the Obfuscation Lens

Abstract: Most of modern Cryptography (especially public-key encryption and beyond) is based on the hardness of structured algebraic problems like factoring. While structure enables these fantastic applications, it also (sometimes) enables faster quantum and sub-exponential time algorithms. This structure also puts the problems in low (and so called structured) complexity classes such as NP?co-NP and Statistical Zero Knowledge (SZK).

Is this structure really necessary? As an evidence for/against necessary structure, we ask: do cryptographic primitives imply hard problems in these structured complexity classes? Some cryptographic primitives such as one-way permutations and homomorphic encryption do while one way functions do not (at least in a black-box fashion). Yet for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not know the answer.

We show that most primitives (including the ones in the list above) do **not** imply hard problems in NP?co-NP or SZK via black-box reductions. In fact, we first show that even the apparently all-powerful Indistinguishability Obfuscation (IO) does not imply such hard problems and then deduce the same for all the other primitives in the list, since IO can construct all of them.

Joint work with Nir Bitansky and Vinod Vaikuntanathan

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 Monday, September 26, 2016 at 7:05 AM.