Example of a good Zero Knowledge Proof. - MathOverflow

Example of a good Zero Knowledge Proof.

2010-04-26T17:35:21Z

I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't true.

Answer by Ryan O'Donnell for Example of a good Zero Knowledge Proof.

2010-04-26T18:12:33Z

The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green.

Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls.

By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than 1/2.

If you and your friend repeat this "proof" $t$ times (for large $t$), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most $2^{-t}$. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.

Answer by Reid Barton for Example of a good Zero Knowledge Proof.

2010-04-26T18:38:36Z

Demonstrating an attack on a cryptosystem is very similar to the colored balls example in Ryan's answer. Suppose Alice and Bob have a means of communicating messages and Eve wants to prove that it is insecure, without revealing the method used to exploit the system. Alice and Eve can simply agree that Alice will send a sequence of random messages to Bob. If Eve can tell Alice the contents of the messages, then with high probability Eve must have an attack on the cryptosystem.

Answer by gowers for Example of a good Zero Knowledge Proof.

2010-04-26T22:30:04Z

An example I like is this. I think I heard it from Avi Wigderson but I can't quite remember. (I don't know who actually thought of it.) You want to prove that a graph can be properly coloured with three colours. So you draw a picture of the graph and then make six copies of that picture. You then properly colour the vertices with red, blue and green, but you also colour the other five copies of the graph in the same way but permuting the colours (so, for instance, in one of them you colour all vertices red that you previously coloured blue and all vertices blue that you previously coloured red). You now repeatedly do the following. Randomly pick one of your pictures, cover each vertex with a coin (so that its colour cannot be seen) and allow the other person to pick an edge and remove the two coins at its end vertices. The other person will obtain from this the information that those two vertices are coloured differently, but will obtain no other information about the colouring.

Now if there is no proper colouring of the graph, and you keep presenting the other person with colourings of the graph, then they can randomly choose their edges, and sooner or later, with very high probability, they will hit an edge that has the same colour at each end. (For the probability to be high, you need to go for many more steps than there are edges in the graph.) So from the fact that this never happens, they can deduce that with extremely high probability you do in fact have a proper colouring of the graph.

Answer by Suresh Venkat for Example of a good Zero Knowledge Proof.

2010-04-27T03:47:43Z

An excellent example of such a proof is one based on Sudoku, and there's even a detailed demonstration for how to conduct it. I've done this in class a number of times to show ZKPs to students.

There's more as well, at Moni Naor's page: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku_abs.html

Answer by Rey for Example of a good Zero Knowledge Proof.

2010-11-14T02:52:07Z

An easy ZKP-based authentication scheme is one that uses a deck of shuffled playing cards and a paper bag:

Suppose Alice and Bob want to authenticate using the secret number "27". Alice takes the deck of cards, places her hands (with the cards) inside the bag and begins drawing card after card until she has reached the 27th card. She pulls this one card out of the bag and reveals it to herself and Bob.

Alice places the cards back on the deck in the same order she drew them (not destroying the original order).

Now it's Bob's turn. He is handed the deck of cards and hides his hands (and the counting of cards) in the paper bag. If he knows the secret number (27) then he should draw down to the 27th card and reveal the same card Alice did.

If Alice and Bob draw different cards then they did not draw the same number of cards.

One more:

Suppose Alice and Bob want to authenticate using the secret number of "27" but don't want to reveal it to one another. In this scenario they use a third party, Charlie.

Charlie randomly comes up with a number (any number will do) -- we'll say 15 -- and whispers it to Alice. Alice then adds the secret number (27) to Charlie's number (15) and whispers the total (42) to Bob.

Bob subtracts the secret number (27) from the total (42) and whispers the result (15) to Charlie.

If Charlie is read back his own number (15) then he can declare Alice and Bob have successfully authenticated.

Answer by Zsbán Ambrus for Example of a good Zero Knowledge Proof.

2010-11-14T12:14:10Z

Another classic example is this. There are two public graphs F and G. Alice knows an isomorphism from F to G. She wants to prove to Bob that F and G are isomorphic graphs, but does not wish to reveal the isomorphism. The procedure is the following. Alice permutes the labels of vertices F randomly, and reveals the graph H he's got that way. She can then compute an isomorphism from H to both F and G, but Bob can't. Bob then randomly chooses either F or G, then which Alice reveals the isomorphism from H to that graph. Repeat.

The problem with this method is that it can be used in practice only if one can generate graphs on which the graph isomorphism problem is hard to decide. That is not currently the case, and might not ever be, if eg. graph isomorphism can be decided efficiently.