A mid-tech solution
Let us first slightly violate our low-tech requirement by assuming that Alice and Bob have access to a photocopy machine. In this case, Alice and Bob can perform a very simple protocol: they photocopy the specific ``Where's Waldo?'' puzzle in question. Alice now cuts out Waldo's image from that copy while Bob is not looking and then shows Bob the image (after hiding or destroying the leftovers). Her ability to do so is certainly a proof that she knows where Waldo is. On the other hand Bob learns almost nothing from the piece he sees (since he is already familiar with Waldo's image).
The obvious disadvantage of this solution (apart from requiring a photocopy machine) is the danger that Alice will cheat by hiding an additional image of Waldo (taken from a different picture) and showing this image (instead of the one in the original picture) to Bob. One way to combat this danger is to require Alice to enter an empty room with nothing on her apart of the picture, scissors, and a match-box. The version for paranoids is to also require a full cavity search.
There is a less invasive method to mend this solution, using interaction: after photocopying the picture, Bob prints a random pattern on its back. Now Alice will be required to show (within a reasonably short time limit) Waldo's image with that specific pattern on its back (a pattern she could not have guessed in advance). Alice should make sure the pattern is regular, so as not to reveal information about the location.
Back to the puzzle
Back to the Puzzler page