Alice is busy trying to find Waldo in the picture above (or, Wally, for those outside of North America). After some time without success, she is doubtful that he is even in the image at all. Bob assures her that Waldo is there, since he already found him. However, this is not enough to satisfy Alice. She needs proof before spending any more time on the task. How is it possible for Bob to prove this to her, without giving the game away by pointing out his location?

Assuming that the picture is printed out on a sheet of paper, Bob could take a large piece of cardboard and cut out a small Waldo-shaped hole. Then, while keeping the hole covered, he slides the paper underneath and, after correctly positioning it, he uncovers the hole to reveal Waldo! Alice can look with her own eyes and see his face, which looks like this: . She agrees that Waldo is in the image but, since all of the rest of the picture is covered by the cardboard, Bob has not revealed the location. So, she continues with her task in the knowledge that, at least, it is possible.

What Bob has done here, is provided a zero-knowledge proof that Waldo is in the picture. That is, he did this while providing no information to Alice other than the fact that he is there. You could argue that he did provide some information. Specifically, he showed Alice the exact size and appearance of Waldo’s face. However, if we assume that this information is no secret and is already publicly known, then it is true that Bob did manage to prove Waldo’s existence in the image without revealing any other previously unknown information. Continue reading “Zero Knowledge Proofs” →