How do I explain zero knowledge proof to my 7 year old cousin? [duplicate]

Question

How do I explain zero knowledge proof to my 7 year old cousin?

Answer 1

I will use Bertie Bott's Every Flavour Beans from Harry Potter in my explanation. If your cousin has not read Harry Potter, you can refer to Jelly Beans instead.

So let's assume there are two beans which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at the beans. You don't believe him, but he doesn't want to tell you which one is which, so there is still a chance that you eat the spinach one.

Instead you hide them both behind your back and randomly choose one of them and show it to your cousin. You then put it back and choose randomly again in a way that allows you to know whether you picked the same bean or not (like swapping the beans x times). You then again show it to your cousin who will have to tell you whether it's the same bean as the one you showed before. Repeat this process until you are sure that he is indeed able to distinguish the beans (or that he's not).

You now know that your cousin is able to tell the beans apart while you still do not know which bean is the tasty one.

Finally, there are two side-channel attacks in this scenario:

1. He may be able to count how often you swapped the beans, so don't make it too obvious.
2. You could offer him one of the beans and when he refuses, it's probably the spinach one.

Answer 2

There is a riddle that I was given a few years ago which, in my opinion, explains the concept quite well - and it can be easily understood by a 7 year old.

Suppose we have, say, a hundred open locks, numbered from 1 to 100. The riddle is the following: I hold a key which opens one of the locks. However, the keys are numbered as well: if I show you the key, and show you that I can use it to open a lock, you will know exactly which key I own.

How can I convince you that I hold a key opening one of the locks, but without revealing to you which key it is? And even more, without revealing anything at all, except that I can open at least one of the locks?

The solution is as follows:

• you create two intertwined "circles of 50 locks". Namely, you attach lock 1 to lock 2, which you also attach to lock 3... which you attach to lock 49, which you attach to lock 50, which you attach to lock 1. This gives you a circle of 50 locks in a chain. You do exactly the same thing with the locks 51 to 100, except that the circle goes through the first circle of locks.
• You hand me the intertwined circle of locks, and leave me for some time. To convince you, I must hand you back the two circles of locks, but separated.

It is easy to observe that if I hold the key for one of the locks, whichever it is, I can open this lock and separate the circles. Hence, this demonstrates that I can open at least one of the locks, but does not reveal anything about which one.

Answer 3

This question has been asked on Information Security StackExchange a couple of years back and I will bring you Rahil Arora's answer (the accepted one), because I think it does an excellent job at explaining.

I heard this example during one of the guest lectures back in my grad school. I think it is simple enough since I've myself used it many times, to explain ZKP to people with almost Zero Knowledge of crypto/math.

Let's say that I want to convince you that I have a superpower to count the exact number of leaves on a tree, within a few seconds. I want to convince you without actually revealing that exact number and without revealing my superpower. I can devise a simple protocol:

I'll close my eyes and will give you a choice to pull off a leaf from that tree. Since it is just a choice, you will either pull it off or you wont. I have no other way of knowing whether you did it or not than quickly counting the leaves again with my superpower. Now when I'll look at the tree, you'll ask me if you actually pulled it off or not.

If I give you a wrong answer, you'll immediately know that my superpower is fake and so is my knowledge. However, if my answer is right, you might think that I just got lucky. In which case we can repeat the above steps. We can keep on repeating these steps to the point where you're satisfied with the fact that I actually posses the superpower and that I know the exact number.

Answer 4

Consider a "Where's Wally" (or "Where's Waldow?") book.

This is a children's book in which every page displays a chaotic, very dense illustration of many persons and items. (See example here, click "Look inside")

The goal of the reader is to find Wally, a specific character.

Suppose Alice knows where Wally is in a specific picture, and she wants to prove it to Bob without revealing Wally's locations.

To do so, Alice takes a large piece of cardboard, at least twice bigger then the book in any dimension. She cuts a tiny hole in the middle of the cardboard, just as big as Wally. When Bob is not looking, she places the book behind the cardboard in such a way that Wally is seen through the hole.

Obviously, in order to do so she has to know where's Wally, and Bob cannot know where Wally is in the page.

Alice can cheat by bringing another Wally illustration and put it behind the cardboard. In order to prevent it bob can search her before the experiment to make sure she does not carry tiny Wally images with her.

Source: www.wisdom.weizmann.ac.il/~naor/PUZZLES/waldo.html

Answer 5

I find Ali Baba's Cave case to be good example to explain zero knowledge proof: https://youtu.be/0Sy6nb72gCk?t=3m46s

There is good summary on Wikipedia: https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_Baba_cave

[...] In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general. They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would become vanishingly small (about one in a million). Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude that it is very probable—astronomically probable—that Peggy does in fact know the secret word. [...]

-- Image by Dake~commonswiki

Answer 6

The simplest example of zero knowledge proof I know of is for graph isomorphism. It's somewhat less interesting following Babai's quasi polynomial result, but for educational purpose we will ignore that. The zero knowledge proof still stands. I'm not sure it is simple enough for a 7 year old but here goes:

We have two graphs where the nodes have different names, we want to prove they are essentially the same graph. Meaning there is a one to one mapping between the nodes of the graphs which preserves the edges. Or alternatively we can rename the nodes of one graph to recieve the second. We want to prove the existence of such a mapping without revealing it.

This can be done by taking one of the graphs and renaming the nodes to random names(providing edges in random order). We send this new graph to a verifier who asks to reveal a mapping between it and one of the two originals of his choice. The prover provides such a mapping. Repeat until desired confidence is reached.

It probably is not simple enough for a a seven year old but simpler than most alternatives as it doesn't use any cryptographic primitives.

Answer 7

Disclaimer. This is not intended to be a canned answer that you can reheat and serve to your cousin as is; that's not how teaching works, especially at that age. You should be able to adapt it to his or her personality and abilities, and answer any question he or she may have (and which it would be futile to try to predict). This means in particular that you need to understand the subject yourself; you cannot hope to explain what you don't understand yourself by simply repeating what you have been told.

---

Most answers here fail to explain the crucial property of zero-knowledge proofs, which differentiates them from ordinary proofs. That property is that of simulatability, which means that even someone who cannot prove the truth of the statement through the prescribed proof protocol can nevertheless produce, in some other way, something that is indistinguishable from an actual proof. One exposition that does explain this is given by Goldreich in his seminal book and goes as follows (paraphrased from memory because I do not have the book at hand right now).

Peggy wants to prove to Victor that there is a path between the two extremities of her labyrinth (more precisely, that every point of her labyrinth can be accessed from either extremity), but without revealing that path to him (so this rules out, for example, just guiding him through it). They proceed as follows. Peggy magically teleports to a random location inside the labyrinth, and Victor (from outside the labyrinth) instructs her to exit it through one extremity chosen by him at random. If Peggy does exit the labyrinth through the extremity designated by Victor, Victor is convinced that a path exists.

This protocol has the three desired properties:

• Completeness. If a path does indeed exist, then no matter where Peggy is teleported in the labyrinth and no matter which exit Victor chooses, Peggy will always be able to exit as instructed.
• Soundness. If a path does not exist, then the location where Peggy is teleported will be connected to exactly one exit. Thus, with probability $1/2$ (if Victor chooses the other exit) Peggy will not be able to exit as instructed.
• Simulatability. If there is a path through the labyrinth, Victor (or anybody else, for that matter) can do something that "looks like" what Peggy does during the protocol even without knowing the path, by proceeding as follows. Victor first chooses an exit at random, enters the labyrinth through that exit, and takes a random walk inside, using a thread to mark his path. If his walk is sufficiently long, he will arrive at a random location, and then he can exit by following his thread, thus "simulating" a proof.

The crucial idea is that Peggy does not reveal, during the protocol, any information about the path (or anything else), because what she does (going from a random location to a random exit) can be done even without knowing the path.

Answer 8

Peggy can tie pretty bows, like no-one else

Peggy knows how to tie very pretty bows. If you give any piece of string to Peggy, she will tie a bow for you, and give it back to you.

Everyone knows that Peggy can tie pretty bows, and they also know that the bows will look the same, every time. No matter what kind of string you give to Peggy, the bow will look the same.

But no-one knows how Peggy ties them, because that is Peggy's little secret. Only Peggy knows how to tie bows in the way that makes them look that way. And the bows are so incredibly intricate that you cannot try to untie a bow and figure out how she did it, because that would take a very long time.

One day Peggy comes to Victor and says "Hi, I am Peggy!". Victor says "Oh yes? Well if you are Peggy, then you can tie a special pretty bow for me, right?". "Oh yes I can" says Peggy, "give me a piece of string and I will prove it to you!".

Victor gives Peggy a piece of string. Peggy takes it, turns around so that Victor cannot see what she is doing, and ties the bow. She then gives the bow to Victor.

Victor looks at the bow. First he checks that the string is the right one that he gave to Peggy (otherwise this could have been an impostor that has stolen a pretty bow that Peggy gave to someone else).

Victor says: "Can you do it again please?". Peggy says, "Sure! Give me a new string!".

Victor and Peggy does this several times, and every time Victor checks to see that the bows look exactly the same. Then Victor is happy and knows that Peggy can indeed tie this kind of bow with any string.

Hence...

Peggy knows a secret: how to tie a bow in a particular way. Victor can look at a bow and see that it was tied by Peggy, but Victor does not know how to do it themselves

What is this useful for?

If everyone — not just Peggy — knows how to tie pretty bows, but everyone ties them differently, we can make a catalogue. The catalogue says that Alice ties this type of bows, Bob ties that kind... Carol, Dave, Erin... everyone that we know is in this catalogue, along with the kind of bow they tie.

So some time later, Peggy comes back to Victor and says "Hi, I am Peggy!".

Victor looks at Peggy and says "You know what... I am really terrible with faces. But I have my catalogue of bows! Here is a piece of string. Can you please tie a bow for me?".

"Of course!" says Peggy, takes the string, turns around, and ties the special kind of bow only she knows how tie. She gives the bow to Victor.

Victor checks the bow against the catalogue and says "Oh yeah! This is the kind of bow that I know only Peggy can tie! Welcome back Peggy."