Akshay Degwekar: Structure vs Hardness Through the Obfuscation Lens
Friday, September 30, 2016 - 10:30am to 12:00pm
Location:
MIT, Hewlett G882, 32 Vassar St, Gates Tower
Speaker:
Akshay Degwekar, MIT
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.
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