Dishonest verifier running a concurrent zero-knowledge protocol

Question

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.

Answer 1

The definition of soundness for an interactive (zero-knowledge) proof says that no prover can convince a verifier of a false statement (i.e., one not in the language in question), except with tiny probability. In your “Bob in the middle” scenario the statement is true—the graph is 3-colorable—so there is no violation of soundness if “Bob” proves it by relaying messages (or any other strategy).

A separate but related property is proof of knowledge, which informally says that any prover that succeeds in convincing the verifier (with large enough probability) must “know” a witness for the statement being proved—in this case, a 3-coloring for the graph in question. (This “knowing” is formalized by designing an extractor for the prover.) Importantly, in the formalization of this property, the prover can interact only with the verifier; it can’t “phone a friend” for help. So, Bob alone would not be considered a prover that on its own can convince the verifier, and therefore there is no requirement on what we can extract from Bob. By contrast, Bob together with Alice as a “joint entity” would qualify as a successful prover, but that joint entity does indeed know a witness, so there is no contradiction with the definition.

There are stronger notions of soundness and proof of knowledge that allow provers to have more powers, e.g., the ability to interact with other entities about other statements, the ability to “reset” the verifier, etc. These go by various names like concurrency, non-malleability, and resettable soundness. Your scenario is most related to non-malleability, except that Bob isn’t changing the relayed messages at all, which is something we can never prevent. Non-malleability basically says that such direct copying is the only way an adversary can succeed.