Qua locus

Keeping both eyes on the long game.

Where’s Wally? I know, and I can prove it without showing you…


This blog has been split in three and all content moved to the new blogs – Qua Locus LifeQua Locus Tech and Qua Locus Puzzle – comments are disabled here.

“Where’s Wally” is a well known children’s (and adult’s!) entertainment. There is a picture. Hidden, somewhere in that picture, is Wally. Alone or together one pores over the book, hunting desperately for the elusive little man. Sometimes people are in a race to find Wally, and the race is won by being the first to point to Wally.

But what if you had to prove that you had found Wally and won the race without pointing to Wally? Maybe your fellow competitor doesn’t want to miss out on the pleasure of finding him themselves. How could you prove to your friend that you had found Wally without them learning anything about where Wally was?

By the way, this is not a rhetorical question – please post in a comment how you would find Wally! I will post the solution that me and some friends came up with together in a week or so and a second, very similar, solution as well…

Also by the way, there is no “trick” to this and the answer is just as described: You must be able to prove that you definitely know where Wally is, and your competitor must learn nothing about where Wally is. The classic formulation of this problem involves an 8 year old girl proving it to her uncle, so no complex technology or mathematics is required!

Background: This might sound like an obscure problem, a non-problem or an irrelevant problem, but actually it’s a very interesting one and one which lies at the heart of what is known as zero-knowledge cryptography: technology which allows you to prove something to someone else but which does not convey any knowledge to them other than that what you claim is true. Thanks to Bob McGrew at Palantir for this thorny problem and a fascinating hours discussion over lunch!

Advertisements

Written by Christo Fogelberg

November 29, 02012 at 08:03

Posted in Puzzles

Tagged with

One Response

Subscribe to comments with RSS.

  1. Ah, it is boring to post solutions to my own problems with no intervening discussion from others! I will post a full solution at some later date, but for now a couple of hints:

    * In some sense, the two solutions are mirror images of each other…
    * In another formulation of is problem, the game is the same but being played by an uncle and his 8 year old niece: she has to prove to him that she has found Wally, and she can prove this without revealing any information to him about where in the picture Wally is
    * The 8 year old niece might need some extra equipment to do this, but it wouldn’t be anything that an 8 year old couldn’t use and understand

    Christo Fogelberg

    December 17, 02012 at 19:43


Comments are closed.

%d bloggers like this: