Welcome to the resource topic for 2023/1972
Title:
Hard Languages in \mathsf{NP} \cap \mathsf{coNP} and NIZK Proofs from Unstructured Hardness
Authors: Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai
Abstract:The existence of “unstructured” hard languages in \mathsf{NP} \,\cap\,\mathsf{coNP} is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether \mathsf{P} is separated from \mathsf{NP} \cap \mathsf{coNP} relative to a random oracle, a question that remained open ever since. While a hard language in \mathsf{NP} \,\cap\,\mathsf{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 \mathsf{NP} \,\cap\,\mathsf{coNP} by showing that if \mathsf{UP} \not \subseteq \mathsf{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 \cal O, we have that \mathsf{P}^{\cal O} \neq \mathsf{NP}^{\cal O} \cap \mathsf{coNP}^{\cal O}. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in \mathsf{NP} \,\cap\,\mathsf{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 \mathsf{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.
ePrint: https://eprint.iacr.org/2023/1972
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .