Where’s Waldo? I dunno.
English Edition by Sellers Publishing Inc.
An interactive proof, informally, is a two-party protocol where an actor (the prover) can convince someone else (the verifier) of the validity of some statement. (The prover should be able to do so if and only if the proposition is indeed valid.)
The interactive proof system is zero-knowledge if the proofs, possibly in a convenient, polynomial-time, given by the Prover have the remarkable property of being both convincing and yielding nothing except that the assertions are indeed valid.
Let’s give a simple example that is not complex as the Feige-Fiat-Shamir Zero Knowledge Proof, let’s talk about Waldo.
Waldo, created by illustrator Martin Handford in 1987, is the figurine present in the kid’s puzzle book, where each page is a crowd of different characters. The idea is to find Waldo, wherever he is hidden.
Since we deal with a lot of data, and a true statement, in Waldo’s book lies an interesting cryptographic problem.
So we have two actors, Alice the prover and Bob, the verifier.
Alice and Bob are playing the quiz book “Where is Waldo?” and Alice shouts: “Waldo, here you are!”
Bob is not convinced. Wasn’t he able to find Waldo for himself? So he asks Alice to prove her bold statement without revealing the location of the character. In fact, he wants to find it also for himself, later.
Alice comes up with this simple zero-knowledge protocol.
She will take a picture of the book and with the aid of an app, will crop the picture of Waldo out of it, and show it to Bob. The cropping is needed since she doesn’t want to give out any information, like colors or shapes, surrounding Waldo.
That would be proof she knows where Waldo is and, Bob will gain no other knowledge outside of it.
The problem with this one-step protocol is clear. Would Alice be able to hide in her phone a picture of Waldo and show it to Bob without finding the character, maybe a pre-cropped picture of it?
One way to avoid this problem would be a search of her phone, or maybe using a freshly bought phone. But, maybe, a better protocol can be used.
Before asking Alice to crop the picture, he will use his phone to generate a random pattern, like a circle, or a square, and ask her to use it in the cropping. In this way, Alice would no be able to pre-crop any image of Waldo.
This protocol has the nuance of being, in nature, being interactive, and could be played on the wire.
The only problem that could arise is if Alice decides not to crop the given picture but use a pre-known picture of another Waldo’s book. Bob could not check if there was a switch or not. In this case, I am afraid we need a third party. That would be an independent actor, who accepts the picture from Bob and the random shape on one side, and the coordinates of Alice on the other.
Another low-tech proof could be arranged with large cardboard with a hole in it, and Alice should be able to move the book slowly letting Waldo peek from the hole.
At the end, all these versions of the protocol are zero-knowledge since they satisfy three properties:
- Completeness: if the statement is true, Bob will be convinced of this fact by Alice.
- Soundness: if the statement is false, Alice cannot convince Bob that it is true, except with some small probability.
- Zero-knowledge: if the statement is true, Bob learns anything other than the fact that Alice knows where Waldo is.
