Using Where’s Waldo To Explain Zero-Knowledge Proof Cryptography

Where's waldo

“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)

About Andy

I'm an eternal optimist, follow a Buddhist philosophy, geek of many areas, learning the Chinese language, a die-hard sports fan, love politics and nuclear submarines.
Just geeky

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

*
To prove you're a person (not a spam script), type the security word shown in the picture. Click on the picture to hear an audio file of the word.
Anti-spam image