Zero-Knowledge Sudoku
Scientific American has been doing a lot about privacy, since that’s the theme of its latest issue. One of its posts today linked to this one from two years ago at a weblog that my old teacher Bill Gasarch has something to do with. It’s a pretty cogent explanation of zero-knowledge proofs, with a sudoku puzzle as the centerpiece.
A zero-knowledge proof is a way of convincing you that I know something without you getting any information about what that thing is. I know, it sounds like LitCrit, but this actually makes sense.
The classic motivating example is a cave with two entrances. Way back deep in the cave there’s a door with a combination lock I tell you I can open. I go into one of the cave entrances (you don’t see which, but if I can’t open the door I’m stuck in whichever one I picked). Then you come to the mouth(s) of the cave and yell out which entrance I should come out of.
If I can open the door, I can come out either entrance, so I come out the one you want. If I can’t open the door, then I can only come out the one you want if that’s the one I went in. Juggling the numbers a bit we can find that the probability I don’t know the combination given that I came out the correct entrance is 
This means that half the time I could have gotten the right answer by luck rather than by skill. That’s not very convincing, but we can repeat the experiment, and each run is independent of all the others. So if we go through the motions 
In a way it’s more like a physics “proof” than the ones mathematicians are used to. The hypothesis can be falsified at any step, and each confirmation just increases the probability that it’s accurate.
4 Comments »
Leave a Reply
RSS Feeds
Yes, that’s the classical example, which makes one wonder why the tester doesn’t require us to come out of the other entrance always and take the probability out of the picture.
My preferred example is about breaking a safe with a combination.
Koray: the point is that the verifier doesn’t know which entrance the prover went into.
Minor point: That $1/2^n$ isn’t the probability that you’re faking, given that you’ve succeeded; it’s the a priori probability that you’ll succeed, give that you’re faking. It’s easy enough to use Bayes’ theorem to show that the first quantity also decreases exponentially. However, the actual number of rounds to reach any level of certainty depends on how much the interrogator trusts you in the first place.
Okay, so it’s a multiplier against the initial trust. The reason I stated it like that is that while in this case you get the same 1/2 at each step for either question, the Sudoku version isn’t quite so symmetrical.