5
$\begingroup$

As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the complexity class of interactive proof systems that was originally introduced for them? I mean, isn't the proof mechanism interactive in ZKPs between Prover and Verifier? Then why are we talking about NP problems, which are the opposite of interactive?

$\endgroup$
2
  • $\begingroup$ As far as I known 1) proving ZKP for a specific NP-complete problem as G3C, you have proved it for every NP-complete problem (and I don't know if something similar exist in the wider sense of IP) 2) In cryptography NP problems are of great interest because, in layman terms, for a verifier they are difficult to calculate but easy to verify. 3) From a general point of view, in cryptography interactiveness is not so desirable because it forces the parties to be online at the same time: as far as I know often the flavours of ZKP are NI ones obtained introducing further models (e.g. ROM or CRS) $\endgroup$
    – baro77
    Oct 21 at 6:21
  • $\begingroup$ Actually, there is an easy reduction from ZK for NP to ZK for all of IP (well, not so easy because it builds on the proof IP = PSPACE, but easy given this proof). I agree with all other points, though. $\endgroup$ Oct 21 at 7:42
11
$\begingroup$

The reason is that essentially, the class of languages in $\mathcal IP$ that are not in $\mathcal NP$ cannot be proven with an efficient prover. Since we are typically interested in the cryptographic context with efficient provers, the study of ZK typically focuses on $\mathcal NP$. (Note that when studying complexity and often in foundations of cryptography, we are certainly interested in inefficient provers.)

In order to see why outside of $\mathcal NP$ the prover cannot be efficient, note that any interactive proof with an efficient prover (given a witness) can be emulated by a machine who receives the witness and runs the proof locally, testing if the result is accept or reject. This is exactly the class of languages $\mathcal MA$. Under standard derandomization assumptions, $\mathcal MA = NP$. Thus, under these assumptions, any language that is not in $\mathcal NP$ can only be run with an inefficient prover (even giving it some witness). As such, it is of less interest when constructing protocols and the like.

$\endgroup$
5
  • $\begingroup$ Thank you very much, I accepted your answer. However, I don't understand why if the prover is inefficient or not it makes a difference somehow. Especially if it has a witness, I always thought that was the relevant part. I mean, when you said "under these assumptions, any language that is not in NP can only be run with an inefficient prover (even giving it some witness)", if an inefficient prover still has a witness, what difference can it make for an algorithm or a complexity class despite a efficient one? and why? $\endgroup$ Oct 22 at 21:55
  • $\begingroup$ We want the prover to be efficient with a witness. What I meant to say is that if we are not in NP (or actually MA), then the prover cannot be efficient in any case (i.e., you cannot make the prover efficient by giving it a witness). Does this answer your question? $\endgroup$ Oct 24 at 7:39
  • $\begingroup$ Actually, I understood that part, thanks. But why do you need a prover to be also efficient if it already has a witness? I thought the efficient part was only to guarantee a more security level when analyzing a protocol (for example, the different levels of zero knowledge, computational, statistic or perfect), but why do we need the prover to be efficient if it already has a witness? Doesn't he just need to use the witness to prove a statement and send the response to the verifier? Maybe the answer is that to calculate the response for the statement the prover still needs computational power? $\endgroup$ Oct 24 at 17:00
  • $\begingroup$ I'm sorry but I'm having a hard time understanding the question. We need the prover to be efficient if we want to use the ZK proof in a cryptographic protocol - since in such a context, all parties must be polynomial time. I don't understand your question at the end "Doesn't he just need to use the witness to prove a statement". The prover indeed uses the witness but this doesn't mean that it's necessarily an efficient (i.e., polynomial time) process. $\endgroup$ Oct 25 at 5:40
  • $\begingroup$ Exactly, so I did understood correctly. Thank you very much, english isn't my native language but now everything's clear! $\endgroup$ Oct 25 at 6:24

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.