# FC08 Assignment 5

### Problem 1: The role of randomness in interactive proofs.

(a) Prove that if $L$ has an interactive proof system in which the verifier is deterministic, then $L\in NP$.

(b) Prove that if $L$ has an interactive proof system, then it has one in which the prover is deterministic.

(c) Prove that if $L$ has an interactive proof system in which the verifier never (not even with negligible probability) accepts a string not in the language $L$, then $L\in NP$.

### Problem 2: Zero-knowledge proofs.

Considier the following proof for 3COL (the language of all 3-colorable graphs):

(1) The verifier sends commitments to $t$ random edges $(i_1,j_1),...,(i_t,j_t)$.

(2) The prover sends commitments to $t$ colorings of the graph, where each coloring is a random permutation of her original coloring at hand.

(3) The verifier reveals the $t$ edges she committed to in round (1).

(4) For each $\ell=1,...,t$, the prover reveals the $\ell$'th coloring of the vertices $i_\ell,j_\ell$

(5) The verifer accepts if and only if all the colors are legal.

Prove that this is a zero-knowledge argument system with perfect completeness and negligible soundness (assuming $t\geq n^3$).

(Recall that an argument system is similar to a proof system, but where soundness is required to hold only against non-uniform PPT cheating provers.)