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. 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 𝒪, we have that P𝒪 ≠ NP𝒪 ∩ coNP𝒪. 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 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.
This joint work with Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, and Amit Sahai.
18 сен 2024
