1
$\begingroup$

The question is fairly simple and is actually stated in the title although I will elaborate a bit further on it. Also, I'm not really sure if this belongs here or it partly belongs to cstheory.stackexchange.com.

Currently I'm trying to understand ZKP as a class of problems. I have read that IP=PSPACE and that ZKP exists under the assumption of OWF, and it basically is IP with the extra property of zero knowledge. I also have read that any NP problem has a ZKP, so NP $\subseteq$ ZKP. What do we know about IP and ZKP?

Edit : I haven't seen any classification diagrams with ZKP mentioned. Is there any resource available for this?

$\endgroup$

2 Answers 2

1
$\begingroup$

It is known that $\mathsf{IP} = \mathsf{PSPACE} = \mathsf{CZK}$ assuming the existence of one-way functions, see here.

The existence of one-way functions is necessary, since it is already known that one-way functions are (essentially - there are minor caveats) necessary to prove that $\mathsf{CZK}$ contains $\mathsf{NP}$. See here and here.

Of course, the first equality is for $\mathsf{CZK}$ with an all powerful prover. In cryptography, we are typically interested in zero-knowledge proofs where the prover is efficient given a witness. Having a witness for the language implies that the language is in $\mathsf{NP}$; it is known that, assuming one-way functions, all languages in $\mathsf{NP}$ have a zero-knowledge proofs with an efficient prover (see here), and as I said above, one-way functions are necessary for this.

$\endgroup$
0
$\begingroup$

Not sure, but I think I found the answer, I would really like to hear if this is actually correct.

The site complexityzoo.net mentions the following :

Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).

I'm not really sure I can understand the last sentence, IP=ZK under the assumption of OWF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.