``Where's Waldo?'' is
a puzzle book where each page contains a very detailed picture with many
different characters (click here for
``Where's Waldo?'' on the WEB). The goal is to find Waldo, a predefined
character . As the
following true story will reveal, in these pictures also lies an interesting
cryptographic problem.
Our story involves two characters; 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?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Click here for discussion and pointers to solutions.