I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold.
Zero-knowledge-protocols in general
What are they good for? What is a typical scenario?
I think they are good for authentication (The verifier wants to authenticate the prover):
- The prover sends a graph for which he knows know a three-coloring to the verifier. They have to be sure that an attacker can't change this graph before the verifier gets it.
- When the verifier wants to authenticate the prover, she asks for the colors of the vertices of one edge:
- The prover chooses a permutation for colors
- The prover applies this permutation the his coloring
- The prover sends the permutated colors of the two vertices of one edge to the verifier
- The verifier repeats step 2 as often as she wants.
I've found a good interactive example where you can play this game. This site includeas another question:
[...] but also raises the question whether or not the prover is just outright cheating
How can I be sure that the prover actually has a three-coloring?
e.g. lets assume that the prover always answers (red, blue)
for any request of the verifier. What would go wrong?
(After reading this great example I think there has to be some probability-part that I currently miss)
Vertex 3-coloring
How can the prover efficiently generate a big graph with a valid three coloring? How can he make sure that it is actually difficult to get a three coloring for this graph?