Zero Knowledge Proofs

> 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.

Here's my alternative zero-knowledge proof that Peggy knows the word:

Victor observes Peggy walk down tunnel A. He stands at the entrance. A short while later, Peggy emerges from tunnel B. Since we know the only way to go down tunnel A and come out tunnel B is by going through the door with the secret word, Peggy must know the word.

Is there something wrong with that? Assuming what I wrote is correct, I think the hamiltonian cycle example further down the page is a much better one.

EDIT: Perhaps Peggy and Victor would have to walk down tunnel A together at the start, so that Victor can observe that the door really is shut. I don't think that invalidates my proposal though.

http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf

This is a good start, but I want more! :)

It's a bit silly to hear people way that college curriculum is irrelevant and then spend a drawn out period of time cobbling together a college curriculum.