How do zero knowledge protocol with vertex-3-coloring work?

Question

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):

1. 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.
2. When the verifier wants to authenticate the prover, she asks for the colors of the vertices of one edge:
   1. The prover chooses a permutation for colors
   2. The prover applies this permutation the his coloring
   3. The prover sends the permutated colors of the two vertices of one edge to the verifier
3. 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?

Answer 1

Zero knowledge in general

What are they good for? What is a typical scenario?

This is an interesting question. One application is authentication: You can choose the secret yourself and not even the server will know it, and it will never be transmitted in any way. You just prove you know the secret again and again. However, in practice this is rarely used. Another application is.... security theory. If a protocol can be shown to hold some zero knowledge property, you are sure the correct protocol execution will not reveal any information about the secrets.

Vertex 3-coloring

How can I be sure that the prover actually has a three-coloring?

You mixed up two essential steps in your description: The color permutation is chosen and applied FIRST, and then the verifier chooses the edge. And therefore, the prover has to send the entire graph with commitments of the colors to the verifier first (or he could still be cheating).

How can he make sure that it is actually difficult to get a three coloring for this graph?

He can make sure that it's difficult to find a coloring if the graph is huge. It's an NP problem, so it can be solved in exponential time. But if the parameter $n$ is small, then $x^n$ is still manageable.

How can the prover efficiently generate a big graph with a valid three coloring?

You should not use the word "efficient" with this problem/proof at all. That is not possible. The main problem is that the probability of detecting cheating is $1/e$, where $e$ is the number of edges.Therefore, with $n$ rounds the probability of successful cheating is $(\frac{e-1}{e})^n$. It does go towards 0, but VERY slowly in a big graph. A common goal for error in cryptography is around $(\frac{1}{2})^{80}$, which would imply an incredibly huge amount of rounds.

About generating a 3-colored graph: Start with 1 node and then add random nodes and edges in a way, which doesn't break the 3 coloring. This should take $O(n)$ time.

Answer 2

How can I be sure that the prover actually has a three-coloring?

Prover responds with colors of just one single edge chosen by Verifier. In case he has valid coloring, his response is consistent with commitments with probability $1$; if not - he errs with a small probability, as answered by tylo. I'm writing this to stress that Prover is given an unpredictable challenge, the edge to open, and this is the most important part of the whole idea.

A real interesting point is

You should not use the word "efficient" with this problem/proof at all. That is not possible. The main problem is that the probability of detecting cheating is 1/e, where e is the number of edges.

Yes, we have low probability to detect cheating with this classical protocol (interactive proof system). Still one could use another challenge type to get overwhelming probability of cheating detection for a variation of this problem (directed graphs). In a few words, assign each edge a linear polynomial with coefficient from a large field representing colors. Assign per-edge product of such polynomials to the whole graph. This polynomial is of maximal degree iff graph is properly colored. In a field, an inverse of this coefficient (remember, polynomial degree is number of edges) always exists, and is known to Prover. To demonstrate valid coloring, run a Schnorr-like protocol, an extension to higher powers in challenge. Probability for cheating detection follows from estimate of upper bound of roots divided by challenge space (that is, field size in denominator, which is also group order). For details, see a report at MFCS 2012.