Zero-Knowledge Proofs (Informal)

A common conversation amongst kids might go something like this (for lack of better names, I’ll call them Alice and Bob):

Alice: Hey Bob, I have a secret!
Bob: Ooh secret! I like secrets. Tell me! Tell me!
Alice: No! If I told you, it wouldn’t be a secret anymore!
Bob: Ha, I bet you don’t have a secret!
Alice: I do!
Bob: Well then, prove it!

After a few more exchanges, Alice relents and tells Bob the secret. Now, Bob goes and tells Charlie, and pretty soon, everyone learns what Alice’s secret is. Well, that was rather unfortunate for Alice.

So, the natural question is whether we can do better? This brings us to the concept of a zero-knowledge proof. Informally, zero-knowledge proofs allow Alice to convince Bob that her claim is true without revealing any information that would allow Bob to then convince someone else that her claim was true. In particular, we want to avoid the above scenario where Bob learns Alice’s secret and can now broadcast it to the world. At the same time, we want Bob to be absolutely convinced that Alice is not lying when she says she has some secret.

We consider a more concrete example of this. Alice and Bob discover a cave deep in the mountains. The cave is very small and there is only a single path leading into the cave. At some point, the path branches off into two separate paths, one to the left, and one to the right. Both paths seemingly lead to a dead end. But this is no ordinary cave, for there is actually a portal at each of the dead ends. If one speaks the magic incantation, the portals will activate, allowing one to cross from one end of the cave to the other.

One day, Alice somehow discovers the words that open the portal. Excited, she runs over to tell Bob of her discovery. But from her past experience, she knows that Bob cannot keep a secret, so she doesn’t want to directly tell Bob the magic words. Consider what would happen if she did. Then, Bob can very easily go to the cave, speak the magic words, and check that either the portal opens and Alice was telling the truth, or nothing happens, and Alice just lied to him. If Alice was indeed telling the truth, Bob can now tell all of his friends the magic words and they too can be convinced that the words are correct simply by trying to open the portal in the cave. Thus, simply telling Bob the secret is not a zero-knowledge proof.

Being a very clever person, Alice thinks of a way to let Bob know that she discovered the secret to the cave without explicitly telling Bob the magic words. When Bob asks Alice to tell him the secret, Alice instead proposes that they play the following game instead:

  1. Alice and Bob travel to the cave. Alice tells Bob to wait at the entrance. She enters the cave and walks down one of the paths.
  2. Alice calls out to Bob to tell him to enter the cave. Bob walks to the fork in the path. At the fork in the path, he announces “Left” or “Right.”
  3. Upon hearing Bob’s selection, Alice exits the cave from the path that Bob announced.

Let’s analyze this scheme in some more detail. First, suppose that Alice does indeed know the magic words. Then, when Bob makes the announcement, either Alice comes out on the same path she took when entering the cave, or she walks through the portal and emerges from the other path. Regardless of which direction Bob chooses, Alice can exit the cave on the path that Bob announced. Now suppose what happens if Alice does not in fact know the magic words, that is, she lied to Bob. In this case, when Bob announces the direction, she has only a 50% chance of coming out on the designated path. Suppose Bob chooses “left.” In this case, if Alice went down the “left” path, she can exit the cave on the path Bob selected, but if she went down the “right” path instead, then she has no choice but to exit from the same path, namely the “right” path.

Is Bob convinced at the end of all this? Well, no. If Alice did in fact emerge from the direction he selected, he might just think that Alice got lucky. And if Alice fails to come out on the designated path, she can just claim to Bob that she wasn’t able to hear Bob announce the path. But what happens if Alice and Bob continue to play this game. Surely, Alice cannot keep getting lucky and she cannot keep claiming that she is unable to hear Bob properly whenever she comes out on the wrong path. In fact, if after k rounds of the game, Bob observes that Alice is successful at exiting through the designated path, he will be more and more convinced that Alice is telling the truth. In particular, if Alice has a \frac{1}{2} chance of getting “lucky” on any given round, the chances that she will get lucky k rounds in a row is given by \frac{1}{2^k}. For sufficiently large k, this probability will become very small and Bob will be convinced that Alice has indeed discovered the secret to the cave. If Alice has not discovered the secret, then after k rounds, she will have succeeded roughly \frac{k}{2} times; if Bob indeed observes that Alice consistently fails to exit on the designated path, he will remain unconvinced that Alice is telling the truth. But observe the crucial fact here: if Alice is telling the truth, she will be able to convince Bob.

The next question then is whether all this is really “zero-knowledge.” We know that in playing this game, Bob does not learn what the magic words are. But can he still convince his friend Charlie (who has not played the game), that Alice has discovered the secret? Bob tries the following: when he and Alice play the game, he takes a video recorder and records everything he sees while he plays the game. In particular, he records the following sequences:

  1. Alice walking into the cave.
  2. Bob walking into the cave and arriving at the fork.
  3. Bob announcing his choice of direction.
  4. Alice exiting the cave.

Suppose Alice and Bob play this game 10 times and Alice successfully exits the cave from the designated direction each time. Bob captures all this on video and shows it to Charlie. Is Charlie convinced that Alice does indeed know the secret? Not surprisingly, the answer is no! In fact, after watching the video, Charlie tells Bob: “So what? I bet you and Alice prearranged the entire sequence ahead of time? Not fooling me!” Indeed, Bob’s video is convincing – who knows, Bob could have edited the video before showing it, or he may colluded with Alice to make it seem like Alice knew the secret. Thus, given only what he has seen, Bob is unable to convince anyone else of Alice’s claim. This brings us to the second important aspect of zero knowledge proofs: the fact that using the information he has gained (i.e., the video of his interactions with Alice), he is unable to convince anyone else that Alice’s claim is true. He has not gained any knowledge or information from Alice about her secret, and yet, he is unequivocally convinced that Alice possesses the secret!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s