Paper 2023/1972

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

Riddhi Ghosal, University of California, Los Angeles
Yuval Ishai, Technion – Israel Institute of Technology
Alexis Korb, University of California, Los Angeles
Eyal Kushilevitz, Technion – Israel Institute of Technology
Paul Lou, University of California, Los Angeles
Amit Sahai, University of California, Los Angeles

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.

Available format(s)
Publication info
Published elsewhere. Major revision. STOC 2023
unstructured hardnessnon interactive zero knowledgerandom oraclesseparating complexity classes
Contact author(s)
riddhi @ cs ucla edu
yuvali @ cs technion ac il
alexiskorb @ cs ucla edu
eyalk @ cs technion ac il
pslou @ cs ucla edu
sahai @ cs ucla edu
2023-12-31: approved
2023-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai},
      title = {Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1972},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.