<p>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.</p>

<p>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".</p>

CC BY-SA 3.0
2011-05-25T03:30:09.120Z
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.
Sadeq Dousti
CC BY-SA 3.0
2011-05-25T03:30:46.327Z
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](http://dx.doi.org/10.1109/SFCS.1987.43) for more info.) Therefore, you cannot always assume that P is deterministic.
Sadeq Dousti
CC BY-SA 3.0
2011-05-25T02:20:52.587Z
2011-05-25T02:20:52.587Z
Tyson Williams
<p>The completeness and soundness in <a href="http://en.wikipedia.org/wiki/Interactive_proof_system" rel="nofollow">interactive proof systems</a> are informally defined as:</p>

<ul>
<li><p><strong>Completeness:</strong> If a statement is true, the <em>honest</em> prover can convince the <em>honest</em> verifier of this fact <a href="http://www.acronymfinder.com/With-High-Probability-%28WHP%29.html" rel="nofollow">w.h.p</a>.</p></li>
<li><p><strong>Soundness:</strong> If a statement is false, the <em>cheating</em> prover cannot convince the <em>honest</em> verifier (of the validity of the false statement) w.h.p.</p></li>
</ul>

<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.</p>

<p>The tricky part is how the probability is computed: In some sources, the probability is taken over the random coins of <strong>both</strong> 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."</p>

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

CC BY-SA 3.0
2011-05-11T00:54:06.490Z
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.
Marcos Villagra
CC BY-SA 3.0
2011-05-11T01:46:34.860Z
@Marcos: Take a look at the [original definition](http://portal.acm.org/citation.cfm?id=22178) 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](http://link.aip.org/link/?SMJCAT/18/186/1) 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?
Sadeq Dousti
CC BY-SA 3.0
2011-05-11T02:05:17.037Z
@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.
Marcos Villagra
CC BY-SA 3.0
2011-05-11T04:14:47.433Z
@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).
Sadeq Dousti
CC BY-SA 3.0
2011-05-11T04:18:03.393Z
(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?
Sadeq Dousti
CC BY-SA 3.0
2011-05-11T04:34:44.150Z
@Sadeq: Ahhh I see, that's a good point you've made.
Marcos Villagra
<cc.complexity-theory><interactive-proofs>
The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems
Incredible
# The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems

(Asked by: username_0 on 2011-05-10)

The completeness and soundness in [interactive proof systems](http://en.wikipedia.org/wiki/Interactive_proof_system) are informally defined as:

* **Completeness:** If a statement is true, the *honest* prover can convince the *honest* verifier of this fact [w.h.p](http://www.acronymfinder.com/With-High-Probability-%28WHP%29.html).
* **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?

**Tags:** cc.complexity-theory, interactive-proofs
> **Comments:**
> **username_1**: 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.  
> **username_2**: @Marcos: Take a look at the [original definition](http://portal.acm.org/citation.cfm?id=22178) 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](http://link.aip.org/link/?SMJCAT/18/186/1) 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?  
> **username_1**: @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.  
> **username_2**: @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).  
> **username_2**: (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?  
> **username_1**: @Sadeq: Ahhh I see, that's a good point you've made.  

---

## 1 answers

### Answer by username_3 on 2011-05-25. Score: 6

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".

> **Comments:**
> **username_2**: 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.  
> **username_2**: 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](http://dx.doi.org/10.1109/SFCS.1987.43) for more info.) Therefore, you cannot always assume that P is deterministic.  

---

