Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Cryptographer Matthew Green wrote a blog about this recently. He also uses 3-coloring. (Oh, and time machines.) blog.cryptographyengineering.com/2014/11/… –  StackzOfZtuff Dec 7 at 13:28

2 Answers 2

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.

share|improve this answer
    
What are "commitments of the colors"? –  moose Jun 17 '13 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 '13 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 '13 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 '13 at 11:59

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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