# Dishonest verifier running a concurrent zero-knowledge protocol

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:

1. $$A\rightarrow B: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$$
2. $$B\rightarrow C: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$$
3. $$C\rightarrow B: (i,j)$$
4. $$B\rightarrow A: (i,j)$$
5. $$A\rightarrow B: (k_i,k_j)$$
6. $$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.