Akshay Degwekar: Structure vs Hardness Through the Obfuscation Lens
Akshay Degwekar, MIT
Date: Friday, September 30, 2016
Time: 10:30 AM to 12:00 PM
Location: Hewlett, G882
Host: Vinod Vaikuntanathan
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
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
Created by Deborah Goodwin at Monday, September 26, 2016 at 7:05 AM.