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

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 PO ≠ NPO ∩ coNPO . 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 zero-knowledge (NIZK) proofs, with a computa-
tionally unbounded prover, to convert a hard promise problem into
a hard language. We obtain such NIZK proofs for NP, with a uni-
formly 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.

Join Zoom Meeting
https://mit.zoom.us/j/99316064630