# The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems

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?

• 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. May 11, 2011 at 0:54
• @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? May 11, 2011 at 1:46
• @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. May 11, 2011 at 2:05
• @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). May 11, 2011 at 4:14
• (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? May 11, 2011 at 4:18