## 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 times and I’ve met your challenge every single time, then the probability that I’ve just been lucky is , 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.

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.

Comment by Koray | August 20, 2008 |

Koray: the point is that the verifier doesn’t know which entrance the prover went into.

Comment by John Armstrong | August 20, 2008 |

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.

Comment by Chad Groft | August 21, 2008 |

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.

Comment by John Armstrong | August 21, 2008 |