11
$\begingroup$

The completeness and soundness in interactive proof systems are informally defined as:

  • Completeness: If a statement is true, the honest prover can convince the honest verifier of this fact w.h.p.

  • Soundness: If a statement is false, the cheating prover cannot convince the honest verifier (of the validity of the false statement) w.h.p.

The term "w.h.p." is either interpreted as "with probability greater than (say) 2/3," or "with probability greater than the reciprocal of any polynomial." It seems immaterial to the following discussion as what interpretation of "w.h.p." to choose.

The tricky part is how the probability is computed: In some sources, the probability is taken over the random coins of both the prover and the verifier. In other sources, the probability is only computed over the random coins of the verifier. The latter is usually justified as: "whatever the random coins of the prover are, the verifier makes the right decision."

To me, both definitions of probability seem equivalent; yet I can't prove this. Am I right? Can you prove them equivalent?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ you should also consider if you are referring to "public" coins or "private" coins. In the public coin setting both prover and verifier know the outcomes of the random choices, and for private coins, the prover doesn't know the random choices of the verifier. In this latter case, you only care about what the verifier do without looking at the prover because the prover simply doesn't know the random coin tosses. $\endgroup$ – Marcos Villagra May 11 '11 at 0:54
  • $\begingroup$ @Marcos: Take a look at the original definition of interactive proofs, which is "private" coin in nature. The last sentence of the first column on page 293, which is underlined, states that "the probabilities are taken only over B's own coin tosses." (Here, B is the verifier.) On the other hand, the journal version of the aforementioned paper allows the probabilities to be taken over the coin tosses of both parties. This might be the source of confusion, right? $\endgroup$ – M.S. Dousti May 11 '11 at 1:46
  • $\begingroup$ @Sadeq: I see, I didn't knew about that difference between the journal and the conference versions. Still, for private coins, I don't see the point in taking into account the prover coin tosses, because he could decide not to tell the verifier about it. The verifier is the one in charge of deciding acceptance or rejection, and he may not know what the prover is doing. $\endgroup$ – Marcos Villagra May 11 '11 at 2:05
  • 1
    $\begingroup$ @Marcos: You're right, but the same reasoning holds for public-coin proofs; since in those systems the prover coin tosses are still private (only the verifier's coin's are public). In general, one can consider a deterministic prover: Since the prover is all-powerful, he does not need randomness and can choose the optimal answer deterministically. Yet this type of reasoning does not work if we consider zero-knowledge systems, in which the prover's strategy should be probabilistic (otherwise, his knowledge would leak). $\endgroup$ – M.S. Dousti May 11 '11 at 4:14
  • 2
    $\begingroup$ (Cont'd) If prover is randomized, then I think the proper formulation is to compute the probability over both coin tosses of the prover and the verifier: While as Marcos said, the verifier is in charge of the final decision, her decision is made (among the others) based on the messages coming from the prover. Given the fact that the prover is randomized, his coin tosses certainly affect the messages he sends. Therefore, the prover's coin tosses affect the probability of acceptance. Am I right? $\endgroup$ – M.S. Dousti May 11 '11 at 4:18
6
$\begingroup$

The prover is "all-powerful and possesses unlimited computational resources" so it has no need of random bits. Thus the only randomness is the randomness of the verifier.

If the prover uses random bits, it should replace them with the random bit string that is most likely to make the verifier accept (this is true for both the honest and any dishonest prover). Furthermore, the prover can determine this optimal bit string because the prover is "all-powerful".

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ As I said in a comment above, this is only true when you consider interactive proofs alone. However, things are very different if you take into account other properties, such as "zero knowledge" which is naturally connected to interactive proofs. $\endgroup$ – M.S. Dousti May 25 '11 at 3:30
  • 1
    $\begingroup$ Cont'd: Specifically, Oren proved the following: "...under the auxiliary-input definition of zero-knowledge, randomness of the prover is essential to the non-triviality of zero-knowledge proof systems. In other words, any language which has an auxiliary-input zero-knowledge proof system in which the prover is deterministic to BPP." (See section 4.5 of Oren for more info.) Therefore, you cannot always assume that P is deterministic. $\endgroup$ – M.S. Dousti May 25 '11 at 3:30

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.