Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so called structured) complexity classes such as NP$\cap$coNP or statistical zero-knowledge (SZK).

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.

The abstract was formatted incorrectly.

Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so called structured) complexity classes such as NP$\cap$coNP or statistical zero-knowledge (SZK).

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.
We study the relationship between two structured complexity classes, statistical zero-knowledge (SZK) and NP$\cap$coNP, and cryptography. To frame the question in a meaningful way, we rely on the language of black-box constructions and separations.
Our results are the following:
1. Cryptography vs. Structured Hardness: Our two main results show that there are no black-box constructions of hard problems in SZK or NP$\cap$coNP starting from one of a wide variety of cryptographic primitives such as one-way and trapdoor functions, one-way and trapdoor permutations (in the case of SZK), public-key encryption, oblivious transfer, deniable encryption, functional encryption, and even indistinguishability obfuscation;
2. Complexity-theoretic Implications: As a corollary of our result, we show a separation between SZK and NP$\cap$coNP and the class PPAD that captures the complexity of computing Nash Equilibria; and
3. Positive Results: We construct collision-resistant hashing from a strong form of SZK-hardness and indistinguishability obfuscation. It was previously known that indistinguishability obfuscation by itself does not imply collision-resistant hashing in a black-box way; we show that it does if one adds SZK-hardness as a “catalyst”.
Our black-box separations are derived using indistinguishability obfuscation as a “gateway”, by first showing a (separation) result for indistinguishability obfuscation and then leveraging on the fact that indistinguishability obfuscation can be used to construct the above variety of cryptographic primitives and hard PPAD instances in a black-box manner.
Keywords: Indistinguishability Obfuscation, Statistical Zero-knowledge, NP ? coNP, Structured Hardness, Collision-Resistant Hashing.

Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, discrete logarithms, and approximate shortest and closest vectors in lattices all have considerable algebraic structure. This structure, on the one hand, enables useful applications such as public-key and homomorphic encryption, but on the other, also puts their hardness in question. Their structure is exactly what puts them in low complexity classes such as SZK or NP$\cap$coNP, and is in fact the reason behind (sub-exponential or quantum) algorithms for these problems. The question is whether such structure is inherent in different cryptographic primitives, deeming them inherently easier.
We study the relationship between two structured complexity classes, statistical zero-knowledge (SZK) and NP$\cap$coNP, and cryptography. To frame the question in a meaningful way, we rely on the language of black-box constructions and separations.
Our results are the following:
1. Cryptography vs. Structured Hardness: Our two main results show that there are no black-box constructions of hard problems in SZK or NP$\cap$coNP starting from one of a wide variety of cryptographic primitives such as one-way and trapdoor functions, one-way and trapdoor permutations (in the case of SZK), public-key encryption, oblivious transfer, deniable encryption, functional encryption, and even indistinguishability obfuscation;
2. Complexity-theoretic Implications: As a corollary of our result, we show a separation between SZK and NP$\cap$coNP and the class PPAD that captures the complexity of computing Nash Equilibria; and
3. Positive Results: We construct collision-resistant hashing from a strong form of SZK-hardness and indistinguishability obfuscation. It was previously known that indistinguishability obfuscation by itself does not imply collision-resistant hashing in a black-box way; we show that it does if one adds SZK-hardness as a “catalyst”.
Our black-box separations are derived using indistinguishability obfuscation as a “gateway”, by first showing a (separation) result for indistinguishability obfuscation and then leveraging on the fact that indistinguishability obfuscation can be used to construct the above variety of cryptographic primitives and hard PPAD instances in a black-box manner.
Keywords: Indistinguishability Obfuscation, Statistical Zero-knowledge, NP ? coNP, Structured Hardness, Collision-Resistant Hashing.

Fixed typos.

Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, discrete logarithms, and approximate shortest and closest vectors in lattices all have considerable algebraic structure. This structure, on the one hand, enables useful applications such as public-key and homomorphic encryption, but on the other, also puts their hardness in question. Their structure is exactly what puts them in low complexity classes such as SZK or NP$\cap$coNP, and is in fact the reason behind (sub-exponential or quantum) algorithms for these problems. The question is whether such structure is inherent in different cryptographic primitives, deeming them inherently easier.
We study the relationship between two structured complexity classes, statistical zero-knowledge (SZK) and NP$\cap$coNP, and cryptography. To frame the question in a meaningful way, we rely on the language of black-box constructions and separations.
Our results are the following:
1. Cryptography vs. Structured Hardness: Our two main results show that there are no black-box constructions of hard problems in SZK or NP$\cap$coNP starting from one of a wide variety of cryptographic primitives such as one-way and trapdoor functions, one-way and trapdoor permutations (in the case of SZK), public-key encryption, oblivious transfer, deniable encryption, functional encryption, and even indistinguishability obfuscation;
2. Complexity-theoretic Implications: As a corollary of our result, we show a separation between SZK and NP$\cap$coNP and the class PPAD that captures the complexity of computing Nash Equilibria; and
3. Positive Results: We construct collision-resistant hashing from a strong form of SZK-hardness and indistinguishability obfuscation. It was previously known that indistinguishability obfuscation by itself does not imply collision-resistant hashing in a black-box way; we show that it does if one adds SZK-hardness as a “catalyst”.
Our black-box separations are derived using indistinguishability obfuscation as a “gateway”, by first showing a (separation) result for indistinguishability obfuscation and then leveraging on the fact that indistinguishability obfuscation can be used to construct the above variety of cryptographic primitives and hard PPAD instances in a black-box manner.
Keywords: Indistinguishability Obfuscation, Statistical Zero-knowledge, NP ? coNP, Structured Hardness, Collision-Resistant Hashing.