Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a commitment of each vertex $v$, $\{\pi(\varphi(v))\}_k$ to Bob. Bob then randomly selects an edge of this graph to which Alice opens the commitment for the corresponding vertices. Finally Bob verifies that for edge $(i,j)$, $\pi(\varphi(i))\neq\pi(\varphi(j))$. They then iterate this process $|E|^2$ times until Bob is convinced with high probability that Alice indeed knows a 3-coloring of the graph.
This is shown in Goldreich, Micali, and Wigderson [1991] to satisfy Completeness, Soundness, and Zero-Knowledge. However, what is to stop a dishonest verifier from running a concurrent protocol much like a man-in-the-middle attack to convince some third-party that they know the coloring?
Suppose Alice is convincing Bob that she knows a 3-coloring, and Bob is convincing Charlie that he knows the same 3-coloring. Bob simply passes on each message received from Alice to Charlie and vice versa. The actions in order will look like:
- $A\rightarrow B: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$
- $B\rightarrow C: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$
- $C\rightarrow B: (i,j)$
- $B\rightarrow A: (i,j)$
- $A\rightarrow B: (k_i,k_j)$
- $B\rightarrow C: (k_i,k_j)$
So how is this not a violation of Soundness? Since Bob does not know a 3-coloring for $G(V,E)$ yet he is able to convince Charlie with high probability that he does. My thought is that zero-knowledge protocols should work like Deniable Authentication signatures, but I'm having difficulty finding literature addressing this type of attack on ZK protocols. If it's not a violation of Soundness, an explanation or citation as to why would be very helpful.