Proofs in Computer Science (Optional) · Zero-Knowledge Proofs

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

In the popular puzzle “Where's Wally?”, a picture with many small details is given, and the task is to find Wally, who is wearing a hat and a sweater with red and white stripes.

Imagine that you have found Wally in this picture. How could you convince your friends of this? Of course, you could simply show them Wally. But how can you convince them that you have indeed found him without revealing his location?

(Note that if you tell your friends what you see near Wally, it will not convince them that you have found him.)