Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes — they imply hard problems in NP$\cap$coNP and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer.
We show that the above primitives, and many others, do not imply hard problems in NP$\cap$coNP or SZK via black-box reductions. In fact, we first show that even the very powerful notion of Indistinguishability Obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO.Category / Keywords: Indistinguishability Obfuscation, Statistical Zero-knowledge, Structured Hardness, Collision-Resistant Hashing Date: received 3 Jun 2016, last revised 30 Nov 2016 Contact author: akshayd at mit edu Available format(s): PDF | BibTeX Citation Note: Fixed typo in Def 4.2. Version: 20161130:215655 (All versions of this report) Short URL: ia.cr/2016/574 Discussion forum: Show discussion | Start new discussion