In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem.

The context:

  • both know the graph (the prover and the verifier)

  • the prover solves a 3-coloring of the graph

  • repeat:

    *the prover randomly permutes the colors

    *the verifier asks for the coloring of an edge

    *if the colors are different the process continues, and the verifier is more convinced that the prover actually solved the 3-coloring, if not, the verifier knows that the prover did not solve the 3-coloring

My question is: why couldn't a false prover (someone that does not know how to solve for the coloring) just always provide 2 different random colors?


1 Answer 1


Your misunderstanding stems from stating a wrong protocol for ZK 3-color verification. In fact the protocol is a bit more complex:

The prover first "commits" to colors. This means that he cannot change its commitment afterwards, but at the same time, he does not reveal the colors themselves.

Then, once the verifier asks for an edge, the prover "opens" its commitment, revealing the colors of that edge alone.

Since its commitment is binding, the prover cannot change the colors after committing to them. So if the prover does not have a legal coloring, he must commit to some invalid coloring of at least one edge, and will be found with some small probability.

This is repeated, each time with a new permutation of the colors, and new commitments.

  • $\begingroup$ I did not emphasize the fact that the prover commits to a coloring, and then, after each permutation, the permutations are done on the original coloring. Yes, I think that was the part you corrected. But my point is that if another false prover also can do a 4-coloring the false prover use the same protocol. In the end, if we accept that someone can solve an NP-c, why not that another can do it also? Or the point is that only one can solve the 4-coloring? $\endgroup$
    – Rafael
    Commented May 10, 2021 at 15:18
  • 1
    $\begingroup$ No, if the prover has a 4-coloring, some of its colors will be outside the set {0,1,2} and it will be caught. $\endgroup$
    – Ran G.
    Commented May 10, 2021 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.