Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness

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. While a hard language in NP ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an 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 NP ∩ coNP by showing that if UP ̸ ⊆ 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 O, we have that P O ̸ = NP O ∩ coNP O . Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in NP ∩ coNP from cryptographic hash functions.

The above conditional separation builds on a new construction of non-interactive zeroknowledge (NIZK) proofs, with a computationally unbounded prover, 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. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.