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

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?

-

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.

-
What are "commitments of the colors"? –  moose Jun 17 at 7:53
As I've asked how he can make sure that it is difficult to get a three coloring for this graph, I knew that the problem is in NPC. But that doesn't mean that every instance of the problem is hard to solve, no matter how big the graph is. For example: When you generate a random graph, you could also get a bipartite graph. When you have a bipartite graph, you can get a two-coloring in linear time. Or a big subgraph that is bipartite. Or another special case which is easy to solve. –  moose Jun 17 at 7:54
Commitments are cryptographic primitives, which can hide its content. Basically they are like locked boxes. And later they can be opened and reveal what was inside. The point is, that the verifier can decide which boxes should be opened, and the prover can not modify the boxes based on this decision. –  tylo Jun 17 at 11:48
@moose I am not entirely sure, how to solve that question but I think the random graph generation works. But I do not have any proofs or numbers to back this up. You would have to estimate the proportions between those special cases and the general case, and if the probability for a hard instance is an overwhelming function. Or equally, if the probability for special cases is negligible –  tylo Jun 17 at 11:59