Paper 2023/1972

Hard Languages in $\mathsf{NP}\cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness

Abstract

The existence of "unstructured" hard languages in $$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $$ is separated from $$ relative to a random oracle, a question that remained open ever since. While a hard language in $$ 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 $$ by showing that if $$, 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 $$, we have that $$. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in $$ from cryptographic hash functions. The above conditional separation builds on a new construction of 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 $$, 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.