Wednesday, February 16, 2011

Applied Kid Cryptography

``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?

No comments: