32

A ZKP allows proof of knowing the answer to a secret, without actually disclosing what that answer is.

Is there any analogy that can help people put this concept into everyday practice? A "lie to children" example is sufficient.

For example, Diffie–Hellman has the color mixing analogy, and the padlock metaphor.

Is there any real life metaphor, superhero with powers, hero/villain, object, or anything that someone can relate to that would help describe what a ZKP is?

My intent is to convert the winning metaphor into an animation that will play on a mobile device as a ZKP is presented. (one animation on the sender side, one on the receiving side)

51
+100

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 how my superpower works. 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.

  • This is a really clever metaphor. – Joseph Kern Apr 25 '15 at 11:19
  • The problem in this metaphor is that if you don't reveal the exact number of leaves, you could also count how many leaves were (If there were any) cut, instead of actually counting how many it still has, hence there's no proof of the superpower... Am I right? – Azteca May 4 '17 at 17:38
  • This is similar to the method I was thinking of on how to convince skeptics I have a 'superpower' to feel crystals and qi/chi/pranna/energy. Now I'll use the phrase 'zero knowledge proof' and sound even smarter! – Chloe May 5 '17 at 20:15
  • The point here is to prove that you have a superpower without revealing which superpower, right? I think "without revealing which superpower I have" would be better wording for the 2nd paragraph. So the other person doesn't know if you can read their mind, or see with your eyes closed / back turned, or if you have a radio and someone telling you what happened. :P Or is the secret you're trying to prove just that you know the number of leaves on a tree, even after it changes? That would basically be revealing your superpower wouldn't it? – Peter Cordes Mar 24 '18 at 2:43
  • 1
    @PeterCordes Thanks for pointing that out. Boy, it's been a couple of years since I wrote that answers, and years since I first heard the metaphor. I think what I don't want to reveal is the exact number of leaves and how the superpower works. Since you have no way of counting all the leaves on a tree, you wont trust me with an exact number unless we repeat exercise mentioned in the metaphor. :) I updated my answer. Lmk if it is still a little confusing. – Rahil Arora Mar 28 '18 at 18:55
6

The best demonstration of zero-knowledge proofs I have come across is "Applied Kid Cryptography, or How to Convince Your Children You Are Not Cheating" by Moni Naor, Yael Naor, and Omer Reingold. They examine a simple but real-life cryptographic problem: how to convince people that you know the solution to a Where's Waldo puzzle without releaving any information about his location. As the paper's title suggests, the explanation aims to be simple enough for a child to understand.

  • I love that one of the solutions has "full cavity search" mentioned. – Cybergibbons May 1 '15 at 6:20
  • 5
    Well, what is it? – Chloe May 4 '17 at 17:41
3

The good answer is this story: The notable case is the “Ali Baba’s cave” metaphor used to illustrate the basic mechanisms behind a zero-knowledge proof: the prover must convince the verifier about his/her knowledge via an interactive protocol, but at the same time a casual onlooker must not gain any information about the secret knowledge.

  • From the book: Explaining Algorithms Using Metaphors, Michal Forišek · Monika Steinová, 2013
  • The reference of the book is this article for 1990: How to Explain Zero-Knowledge Protocols to Your Children.

enter image description here

  • 6
    Either I'm blind or you didn't include actual metaphor here (just a reference and a teaser) – joozek Apr 30 '15 at 18:27
  • Nice username/post combo – Numeron May 1 '15 at 4:38
  • Here's a source for the story mentioned in this answer: pages.cs.wisc.edu/~mkowalcz/628.pdf – Brilliand May 19 '15 at 23:09
1

Kudos on the rsa mixing analogy. A great find.

The zkp mostly depends on an operation of some sort, with the verifying party being able to dictate some terms that the opposing party can use. Of course this is very dependent on the question being asked in the first place.

The peggy victor secret door combination wouldn't work if the question was phrased as Victor wanting to know if Peggy could get to the left/right side of the tunnel as opposed to knowing the password to get through the door.

So the question in real life is could possibly be summarised for kids as so:

I would like to know if you understand how A/B/C works, or that you are privy to a knowledge that says that you do. The proof of which might be some form of test, which possibly could translate into some form of verbatim exposition of the accepted answer, or a physical expression of the knowledge ( i.e. do you know how the combustion engine works, and yes, here's the flat 8 with twin carbs that i made with my bare hands with the steel hewn from the depths of a mine somewhere in the northern reaches of russia ). The tricky thing with ZKP, and this extends to a lot of other areas, is whether upon producing the proof, it in itself reveals the manner in which to derive the answer.

And it appears in real life, that translates into the amount of time necessary for the verifying party to reverse engineer the proof to determine the machinations inside. So i contend that ZKP is also about increasing this time to a proportion where it does not make sense to figure this out.

And with that you'd be able to apply this to quite a number of real world examples.

0

Suppose there are two type of drinks which are widely believed to be the same but in different packaging. But A knowing the fact that they are same tries to discover a test to distinguish between the two. Next A would like to convince B that two drinks are not same.

a) A trivial way to prove it would be for A to send the details of her test to B and let B carry out the test. b) But suppose A does not want to divulge anything about the conducted test. Then A could still convince B using the following protocol.

It goes as: B takes a can of drink of each brand and randomly chooses a can, pours some drink out of it (all in private), and gives it to A. A then tests the sample and tells B which brand the sample belongs to. They iterate this procedure several times. If A answers correctly each time, then B will accept the claim that the drinks are not identical.

In this protocol, firstly, if the drinks are different and A has a reliable test to distinguish between them, then A can always convince B. On the other hand, if indeed the drinks from both the cans are identical, then A cannot tell them apart.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.