The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way from a {\em one-way permutation}, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an {\em injective one-way function}, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.

We give the first evidence for the existence of unstructured hard languages in $\text{NP}\cap\text{coNP}$ by showing that if $\text{UP} \not \subseteq \text{RP}$, which follows from the existence of injective one-way functions, the answer to Bennett and Gill's question is affirmative: with probability 1 over a random oracle $\cal O$, we have that $\text{P}^{\cal O} \neq \text{NP}^{\cal O} \cap \text{coNP}^{\cal O}$. Our proof gives a constructive {\em non-black-box} approach for obtaining candidate hard languages in $\text{NP}\cap\text{coNP}$ from cryptographic hash functions.

The above conditional separation builds on a new construction of {\em non-interactive zero-knowledge} (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for $\text{NP}$, with a {\em uniformly random} reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other {\em structured} primitives, as well as with (computationally sound) NIZK {\em arguments} in the random oracle model.