The Problem
A friend of mine gave me a riddle this morning regarding “Where’s Waldo?”. The riddle is as follows:
You and a friend play “Where’s Waldo?”. You solve the puzzle before your friend, and you want to prove to your friend you solved the puzzle, without giving him any hints. How do you do this?
Obviously, this is of course very reminiscent of zero knowledge proofs. A good zero knowledge proof will allow your friend to be convinced before he found Waldo himself, and even if he never finds him at all. A somewhat less interesting solution is a solution that will allow your friend to be convinced if and when he finds Waldo himself and can then verify your proof.
There are obviously many “intuitive” solutions, and I will not write them here… I will write here the second solution I thought of, but I consider it to be the more interesting one. However, this solution doesn’t solve the original problem – it only allows your friend to verify your solution once he solved it himself.
The Solution
Take a sheet of paper of identical dimensions to the picture, and mark a spot on it in the position where Waldo would have been on that sheet of paper. Fold that sheet of paper to some kind of origami animal, and give it to your friend. Once he solves the puzzle, he can open the folding, and see for himself that the point was marked correctly.
This is obviously not a very good solution. It is just a glorified note – you write down your solution on a note, and ask your friend not to peek until he solves it himself. So I came up with an improvement:
Agree beforehand with your friend on some (large) origami folding (such as a beetle). He shouldn’t know the instructions to fold it. Take a sheet of paper, and mark Waldo’s position on it (with a dot). Hold the paper above the fold, and mark on the fold (with another dot) the projection of the original dot on the folding. Now unfold the origami – you have a crease pattern. Give the crease pattern to your friend. When he solves the puzzle, refold the origami, and prove to your friend that the projection of the dot on the fold coincides with the dot on the picture. As an added bonus – your friend just learned how to fold another origami beast!
Of course, this solution isn’t water-tight. It also relies on crease patterns being hard to solve. It is mostly security by obscurity – but this time, ‘security by obscurity’ becomes ‘security by origami’. I just found that fascinating – that origami may be considered a function that is ‘hard to reverse engineer’ (even if it is not so) – such as a hash function. Origami does behave a little bit like a hash…
Tell me your original solutions to the problem.
This solution requires technology and you and your friend are still on the “honor system” because the proofs could cross paths in the air.
Each friend picks a word or passphrase. When you’ve found Waldo, you use the colors of the five closest people, or the x,y coordinates of Waldo’s hat or something like that – something that explains where he is. When you’ve found Waldo, you append your public key (the agreed upon word) to the coordinates or other distinguishing characteristic, then calculate a hash for that (MD5, SHA-1, SHA-256 – depends on how important the game is). Give the hash to your friend. When your friend finds Waldo, they use the agreed upon characteristics (location works better) and your password, then calculates the hash in the same way. If they match, then you solved it first.
The biggest downside to this is that your friend MUST find Waldo in order to prove that you found him first.
Suppose we agree on coordinates of the tip of Waldo’s hat as the objective. And my public word is SYLVAN.
When I find Waldo, he’s at X 8.75cm (round to the nearest cm – 9) and Y 4.1cm (rounded to 4cm). So I calculate:
MD5(‘SYLVAN:9:4’) and pass that to my friend. When my friend finds Waldo (at the same coordinates), he has enough information to calculate the same hash – neither of us can calculate it without finding Waldo.
This solution was the first solution I thought about. It works, but we (me and the guy who gave me the riddle, henceforth ‘the riddler’) discounted it as ‘too obvious’ :). Also – The ‘riddler’ also suggested that it might be faster for the guy who didn’t find Waldo to brute-force the (discrete) coordinates then try and find Waldo. A possible improvement might be to give the hash of coordinates and some redundant information. For example – hashing the coordinates to x digits after the decimal point.
There are also some possible proofs before the the guy finds Walso himself. For example, we take a black board with a small hole in it, and align the board such that a part of Waldo is underneath the hole. It still relies on you being able to give a part of the picture of Waldo, without giving any hints, just like the solution of cropping out everything besides Waldo, that appeared in Securiteam blogs.
@lorg
I had also considered that if you’re rounding to the nearest centimeter (or some measurement), it might be easier to brute-force the solution. I picked the nearest centimeter because the two books would have to have been printed and bound exactly the same in order to get the measurements of a single point very exact. As long as it’s okay for the proof to come after both parties have found Waldo, it’s okay for the measurements to be exact so long as the first person can explain the coordinates used to gen the hash – the hash is only used as a way to keep the coordinate secret while the slower party finishes.
I talked again with the guy who gave me this riddle – Nadav Sherman. His solution to the problem seemed to be very similar to mine – use a cover with a hole right over Waldo’s face. According to him this solution is problematic – I can cheat and plant another picture of Waldo underneath the cover. To make it work, he suggested adding another cover above the holed cover, this time complete. Now, in the manner of other zero-knowledge proof, the guy who didn’t find Waldo can choose – either remove the upper cover – thus showing a part of Waldo, proving that I know where he is, or remove both of them – this showing the complete picture – proving I didn’t cheat.
It is important to note that this solution is a solution to the more interesting problem – of proving I found Waldo even if the other guy didn’t find him himself.