Score:5

Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

in flag

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?

baro77 avatar
gd flag
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)
Geoffroy Couteau avatar
cn flag
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.
Score:11
us flag

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.

in flag
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?
Yehuda Lindell avatar
us flag
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?
in flag
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?
Yehuda Lindell avatar
us flag
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.
in flag
Exactly, so I did understood correctly. Thank you very much, english isn't my native language but now everything's clear!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.