“Where’s Waldo?” is a puzzle book where each page contains a very detailed picture with many different characters. The goal is to find Waldo in that picture. As the following true story will reveal, in these pictures also lies an interesting cryptographic problem.
Below is a story involving two characters to explain the problem to be solved; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob.
One day, while Alice and Bob were playing ‘Where’s Waldo?’, Alice suddenly claimed: “I know where Waldo is!”. Bob responded with a baffling riddle: “Alice, do you know what a liar is?”. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: “How can I prove to Bob that I know where Waldo is without revealing his location?”
Aye, there’s the conundrum in Zero-Knowledge Proof cryptography: How can you prove you know the answer without revealing the secret?
Here are some answers using a low tech and mid tech solution as proposed in the paper “Applied Kid Cryptography or how to convince your children you are not cheating“. This is a fascinating example to use in explaining and simplifying the problem.
Link to the paper (pdf)