Abstract
The existence of ``unstructured'' hard languages in NP ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NP ∩ coNP relative to a random oracle, a question that remained open ever since. We give the first evidence for the existence of unstructured hard languages in NP ∩ coNP by showing that if UP is not contained in RP -- which follows from the existence of injective one-way functions -- then the answer to Bennett and Gill's question is affirmative: with probability 1 over a random oracle O, we have that P^O is not equal to NP^O ∩ coNP^O. The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, which we use to convert a hard promise problem into a hard language. We obtain such NIZK proofs for NP, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle.