The Unapologetic Mathematician

Mathematics for the interested outsider

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 \frac{1}{2}.

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 n times and I’ve met your challenge every single time, then the probability that I’ve just been lucky is \frac{1}{2^n}, which gets very small very quickly. After a while you’ll be sufficiently convinced that I know the answer.

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.


August 20, 2008 Posted by | Cryptography | 4 Comments