7 ms·

How to explain zero-knowledge protocols to your children (1998) [pdf]

jimmies 9y ago
In the same spirit and format of OP's link, I also enjoy Thompson's paper "Reflections on Trusting Trust." It's so dead simple yet was an ah-ha moment for me. Materials like this are the reason why I love security and cryptography (despite never had the chance to work on cryptography full-time). For anyone who is interested in understanding basic ideas of cryptography, Art of the Problem also has an excellent playlist (Gambling with Secrets, Randomized algorithms) on Youtube: https://www.youtube.com/user/ArtOfTheProblem/playlists https://www.youtube.com/user/ArtOfTheProblem/playlists Art of the Problem is probably the transformative channel that made me see how and why Youtube is an excellent tool to learn.
- amelius 9y ago
  From Thompson's paper: > The press must learn that misguided use of a computer is no more amazing than drunk driving of an automobile. That's a silly thing to say, especially considering that there is a different and bigger problem: a software system with broken security.
yjgyhj 9y ago
I enjoyed the story, and got it! The one part I miss to be able to claim understanding of zero-knowledge protocols is anchoring the story to what one uses (modern) ZKPs for. Hoping to read that connection here in the HN comments.
- ooqr 9y ago
  Try this as an example. https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
- mbgaxyz 9y ago
  https://z.cash https://z.cash Zcash is the first open, permissionless cryptocurrency that can fully protect the privacy of transactions using zero-knowledge cryptography. The Zcash client is now available for download as a command-line tool for Linux.
  - yjgyhj 9y ago
    Does this work the same way as Monero?
logicallee 9y ago
Zero-knowledge proofs are an extremely practical problem. If you could convince an algorithm that you know a password, without having to type it, you would be impervious to keyloggers or any loss of your password - you would never have to change your password, either. Unfortunately, there are no practical zero-knowledge proofs anyone can use in their heads. For this reason we are left typing them at least into the local device we're using - or having to use a second factor. Passwords can't stay in our head. That's a shame, because there's no theoretical reason for this to be so. Theoretically, easy, practical zero-knowledge proofs we can implement in our heads could exist. But apparently they don't.
- chii 9y ago
  Imagine a website who wants to add password-less login. They can give the user a program or dongle which the user can type in their preferred password, and a code from the website. The dongle outputs a new nimber, which is then sent to the website. The website then asks to repeat this step as many times as they desire to ensure thst the user knew the password, all without sending it or revealing it to the website.
  - logicallee 9y ago
    Dongles similar to this exist, but you've just moved the problem: the user now needs to type their password into that device. If there were a real zero-knowledge protocol, the user could prove to the device that they know the password, without having to type it: the device still wouldn't have it. Even if someone stole the device, copied it, or modified it to record the user's input, this would not compromise the user's security in the future. (At worst it could MITM a current session, while leaving the user's password secure and uncompromised.) That is not the case with the dongle you have described.
akovaski 9y ago
Why wouldn't you just record Mick going in one direction and coming out the other? I had to reread it to understand that they weren't doing that. (I get that that is how this ties things together, but from a story perspective it feels like a weird move to me.) edit: Or is there an implication that Mick may have also faked it?
- Arnavion 9y ago
  Because then it's obvious to everyone that Mick knows how to pass through the wall. Mick wants only the one reporter to be convinced that Mick knows how to pass the wall. The point of zero-knowledge is that an external observer should not be able to be verify the proof, only the parties involved.
  - akovaski 9y ago
    > Mick wants only the one reporter to be convinced that Mick knows how to pass the wall. I can see how this could provide a justification, but this is not implied in the story at all.
    - Arnavion 9y ago
      "The Jealous Reporter" section is entirely about this. Start from "But the judges and the experts could not tell the tapes apart." In particular: >The reporter who had gotten the exclusive story had been convinced at the time that Mick Ali knew the secret, but the reporter could not pass his conviction on to the judges in court or to the television audiences either. >Mick Ali had achieved his real objective. He wanted, in fact, to show that it is possible to convince without revealing, and so without unveiling his secret.
      - dorgo 9y ago
        I don't get it. He can go left and come out right to demonstrate that he knows the secret - without revealing the secret. The reporter would still not know how he did it and could not pass his conviction on to the judges. And the fake reporter could still produce his fake report. The only reason for this complicated procedure I can come up with is that the secret includes some action at the fork which may not be observed by reporter.
tom_pulo 9y ago
Awesome little paper. I wish there were more papers like this! BTW, you guys might enjoy https://betterexplained.com https://betterexplained.com - the author explains math concepts in new more intuitive ways. The folks at Fermat's Library actually annotated this paper not too long ago: https://fermatslibrary.com/s/how-to-explain-zero-knowledge-protocols-to-your-children https://fermatslibrary.com/s/how-to-explain-zero-knowledge-p...
- mih 9y ago
  Without any idea of what ZKP is used for, I did not find it the explanation very intelligible. Later I found the simple explanation on Wikipedia and was able to connect the dots https://simple.wikipedia.org/wiki/Zero-knowledge_proof https://simple.wikipedia.org/wiki/Zero-knowledge_proof
  - mnarayan01 9y ago
    The "simple" version leaves out an important bit from https://en.wikipedia.org/wiki/Zero-knowledge_proof https://en.wikipedia.org/wiki/Zero-knowledge_proof: > 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. Without that, the example seems overly convoluted.
jonhyman 9y ago
My favorite example of this from my college encryption class is: let's say that there's a giant jar of jelly beans, and I tell you that my super power is that I can count how many jelly beans are in that jar. I don't want to tell you how many there are, and you might not even believe me if I did, so here is the test we'll run: I'll turn around, and you grab a handful of jelly beans and put them behind your back. I'll then turn back around, count the number of jelly beans in the jar, and tell you how many are in your hand. After repeating this 100 times, I will have demonstrated that I can count the number of jelly beans in the jar without telling you how many are in it.
- dorgo 9y ago
  Why repeating 100 times? Wouldn't the first time suffice? Ok, you could be lucky, but how probable is that? Update: Given the content of the jar it may happen that the count of items could go down with each experiment :-P
  - hvidgaard 9y ago
    The more times you repeat, the less likely it is that you've just guessed correctly.
- arcbyte 9y ago
  You would need 100 different jars with different counts. Otherwise, you either get lucky on the first time and then you always know the amount, or you (more likely) loose the first time and then it doesn't matter.
  - xtreme 9y ago
    No, you don't need 100 different jars. Let's say the jar started with S beans, and the person grabbed X_1, X_2, .. X_n beans in n trials. To prove the superpower, you have to tell him the correct value of X_i every time. Knowing S beforehand does not help you unless you can calculate S-X-i without knowing X_i.
  - Bartweiss 9y ago
deleted 9y ago
[deleted]
lgessler 9y ago
The idea reminds me of Dori-Mic and the Universal Machine: http://www.dori-mic.org/ http://www.dori-mic.org/
rumcajz 9y ago
I find the cave example non-intuitive. At some point I would like to write a book about crypto for children. Here's a dump of material I have w.r.t. zero-knowledge: https://github.com/sustrik/crypto-for-kids/blob/master/zero-knowledge-proofs.md https://github.com/sustrik/crypto-for-kids/blob/master/zero-...
ComodoHacker 9y ago
> The pursuer arrived, and was all upset to find only Ali Baba under the sacks at the dead end of the passage. The thief had escaped. The story clearly misses lively scene of beating Ali Baba as a thief.
metaphor 9y ago
If I try to keep in mind that the target audience is children, then the paragraph just before The Jealous Reporter is where I feel the clarity in prose really starts to fall apart. Introducing the concept of probability without really explaining its significance...or the notion of something being genuine...all this random court mumbo jumbo...simulation and parallel stuff...filming high-rise apartments with caves stuffed in them to achieve something that may not be optimal...even dropped authentication somewhere in there. Really? I'm honestly surprised Alice and Bob didn't somehow find their way into this plot...or was that Paul and Carole.
- Bartweiss 9y ago
  Yeah... We eventually hit "Do we have no conveyance of knowledge when you cannot simulate with successive attempts?" Which is not what I generally class as children's-story language. But the statistical argument is even harder - accepting that a low enough probability (more accurately, p value) implies a non-random source of a phenomenon is not obvious. I suspect that the initial usage would be ok, where Ali Baba says he didn't guess wrong 40 times. But the coin flip idea with Mick isn't intuitive and isn't really explained. The lead-in is interesting, and it's a clever story, but it lost the plot on target audience pretty badly.
jstanley 9y ago
I don't like this example of a ZKP. It seems like AliBaba could conclusively prove knowledge of the secret by simply being seen to enter on the left and return on the right. No interaction necessary, and it's conclusively proven in only one iteration. Am I missing something?
- y7 9y ago
  Perhaps if someone else stood at the entrance of the fork, they could hear him mutter the secret phrase.
- Ar-Curunir 9y ago
  It's not zero knowledge; if I record it then someone else will be convinced that Ali Baba knows the secret. A normal interactive ZKP should not have such a property.
  - n4r9 9y ago
    > if I record it then someone else will be convinced that Ali Baba knows the secret Isn't that exactly what they're trying to do? Prove that Mick Ali knows the secret? I thought the zero-knowledge part is in showing that Mick Ali knows the secret but without knowing/revealing the secret itself. EDIT: On a second reading I see your point. The paper says "the reporter could not pass on his conviction to the judges".
  - Spivak 9y ago
    But nothing about the story will actually change. The second reporter will use editing to make the the actor appear to go in the left and come out the right. Then when they go before the judge there's no difference between the real and fake tapes so it's again unconvincing. Since the author allowed the use of video editing in the story anything that isn't seen in person is unconvincing.
retox 9y ago
My understanding broke down when they introduced the Israeli connection, I couldn't understand what point was being made.
- Bartweiss 9y ago
  It's not very well written - this starts out as a children's story but rapidly transitions into 'conveyance' and 'authentication'. Simply: you can authenticate by testing one binary value many times (the cave), but you can shorten the handshake process by adding multiple secrets or multiple possibilities for each secret-test. The goal is to create a result which is highly improbable without secret knowledge, and you can trade off different values (number of secrets, number of handshakes, size of secrets) to achieve that. I confess I don't understand the last line of that section about 'conveyance'. The process appears robustly ZKP even without successive attempts.

In the same spirit and format of OP's link, I also enjoy Thompson's paper "Reflections on Trusting Trust." It's so dead simple yet was an ah-ha moment for me. Materials like this are the reason why I love security and cryptography (despite never had the chance to work on cryptography full-time). For anyone who is interested in understanding basic ideas of cryptography, Art of the Problem also has an excellent playlist (Gambling with Secrets, Randomized algorithms) on Youtube: https://www.youtube.com/user/ArtOfTheProblem/playlists https://www.youtube.com/user/ArtOfTheProblem/playlists Art of the Problem is probably the transformative channel that made me see how and why Youtube is an excellent tool to learn.

amelius 9y ago
From Thompson's paper: > The press must learn that misguided use of a computer is no more amazing than drunk driving of an automobile. That's a silly thing to say, especially considering that there is a different and bigger problem: a software system with broken security.

yjgyhj 9y ago

I enjoyed the story, and got it! The one part I miss to be able to claim understanding of zero-knowledge protocols is anchoring the story to what one uses (modern) ZKPs for. Hoping to read that connection here in the HN comments.

ooqr 9y ago
Try this as an example. https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
mbgaxyz 9y ago
https://z.cash https://z.cash Zcash is the first open, permissionless cryptocurrency that can fully protect the privacy of transactions using zero-knowledge cryptography. The Zcash client is now available for download as a command-line tool for Linux.
- yjgyhj 9y ago
  Does this work the same way as Monero?

logicallee 9y ago

Zero-knowledge proofs are an extremely practical problem. If you could convince an algorithm that you know a password, without having to type it, you would be impervious to keyloggers or any loss of your password - you would never have to change your password, either. Unfortunately, there are no practical zero-knowledge proofs anyone can use in their heads. For this reason we are left typing them at least into the local device we're using - or having to use a second factor. Passwords can't stay in our head. That's a shame, because there's no theoretical reason for this to be so. Theoretically, easy, practical zero-knowledge proofs we can implement in our heads could exist. But apparently they don't.

chii 9y ago
Imagine a website who wants to add password-less login. They can give the user a program or dongle which the user can type in their preferred password, and a code from the website. The dongle outputs a new nimber, which is then sent to the website. The website then asks to repeat this step as many times as they desire to ensure thst the user knew the password, all without sending it or revealing it to the website.
- logicallee 9y ago
  Dongles similar to this exist, but you've just moved the problem: the user now needs to type their password into that device. If there were a real zero-knowledge protocol, the user could prove to the device that they know the password, without having to type it: the device still wouldn't have it. Even if someone stole the device, copied it, or modified it to record the user's input, this would not compromise the user's security in the future. (At worst it could MITM a current session, while leaving the user's password secure and uncompromised.) That is not the case with the dongle you have described.

akovaski 9y ago

Why wouldn't you just record Mick going in one direction and coming out the other? I had to reread it to understand that they weren't doing that. (I get that that is how this ties things together, but from a story perspective it feels like a weird move to me.) edit: Or is there an implication that Mick may have also faked it?

Arnavion 9y ago
Because then it's obvious to everyone that Mick knows how to pass through the wall. Mick wants only the one reporter to be convinced that Mick knows how to pass the wall. The point of zero-knowledge is that an external observer should not be able to be verify the proof, only the parties involved.
- akovaski 9y ago
  > Mick wants only the one reporter to be convinced that Mick knows how to pass the wall. I can see how this could provide a justification, but this is not implied in the story at all.
  - Arnavion 9y ago
    "The Jealous Reporter" section is entirely about this. Start from "But the judges and the experts could not tell the tapes apart." In particular: >The reporter who had gotten the exclusive story had been convinced at the time that Mick Ali knew the secret, but the reporter could not pass his conviction on to the judges in court or to the television audiences either. >Mick Ali had achieved his real objective. He wanted, in fact, to show that it is possible to convince without revealing, and so without unveiling his secret.
    - dorgo 9y ago
      I don't get it. He can go left and come out right to demonstrate that he knows the secret - without revealing the secret. The reporter would still not know how he did it and could not pass his conviction on to the judges. And the fake reporter could still produce his fake report. The only reason for this complicated procedure I can come up with is that the secret includes some action at the fork which may not be observed by reporter.

tom_pulo 9y ago

Awesome little paper. I wish there were more papers like this! BTW, you guys might enjoy https://betterexplained.com https://betterexplained.com - the author explains math concepts in new more intuitive ways. The folks at Fermat's Library actually annotated this paper not too long ago: https://fermatslibrary.com/s/how-to-explain-zero-knowledge-protocols-to-your-children https://fermatslibrary.com/s/how-to-explain-zero-knowledge-p...

mih 9y ago
Without any idea of what ZKP is used for, I did not find it the explanation very intelligible. Later I found the simple explanation on Wikipedia and was able to connect the dots https://simple.wikipedia.org/wiki/Zero-knowledge_proof https://simple.wikipedia.org/wiki/Zero-knowledge_proof
- mnarayan01 9y ago
  The "simple" version leaves out an important bit from https://en.wikipedia.org/wiki/Zero-knowledge_proof https://en.wikipedia.org/wiki/Zero-knowledge_proof: > 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. Without that, the example seems overly convoluted.

jonhyman 9y ago

My favorite example of this from my college encryption class is: let's say that there's a giant jar of jelly beans, and I tell you that my super power is that I can count how many jelly beans are in that jar. I don't want to tell you how many there are, and you might not even believe me if I did, so here is the test we'll run: I'll turn around, and you grab a handful of jelly beans and put them behind your back. I'll then turn back around, count the number of jelly beans in the jar, and tell you how many are in your hand. After repeating this 100 times, I will have demonstrated that I can count the number of jelly beans in the jar without telling you how many are in it.

dorgo 9y ago
Why repeating 100 times? Wouldn't the first time suffice? Ok, you could be lucky, but how probable is that? Update: Given the content of the jar it may happen that the count of items could go down with each experiment :-P
- hvidgaard 9y ago
  The more times you repeat, the less likely it is that you've just guessed correctly.
arcbyte 9y ago
You would need 100 different jars with different counts. Otherwise, you either get lucky on the first time and then you always know the amount, or you (more likely) loose the first time and then it doesn't matter.
- xtreme 9y ago
  No, you don't need 100 different jars. Let's say the jar started with S beans, and the person grabbed X_1, X_2, .. X_n beans in n trials. To prove the superpower, you have to tell him the correct value of X_i every time. Knowing S beforehand does not help you unless you can calculate S-X-i without knowing X_i.
- Bartweiss 9y ago

deleted 9y ago

[deleted]

lgessler 9y ago

The idea reminds me of Dori-Mic and the Universal Machine: http://www.dori-mic.org/ http://www.dori-mic.org/

rumcajz 9y ago

I find the cave example non-intuitive. At some point I would like to write a book about crypto for children. Here's a dump of material I have w.r.t. zero-knowledge: https://github.com/sustrik/crypto-for-kids/blob/master/zero-knowledge-proofs.md https://github.com/sustrik/crypto-for-kids/blob/master/zero-...

ComodoHacker 9y ago

> The pursuer arrived, and was all upset to find only Ali Baba under the sacks at the dead end of the passage. The thief had escaped. The story clearly misses lively scene of beating Ali Baba as a thief.

metaphor 9y ago

If I try to keep in mind that the target audience is children, then the paragraph just before The Jealous Reporter is where I feel the clarity in prose really starts to fall apart. Introducing the concept of probability without really explaining its significance...or the notion of something being genuine...all this random court mumbo jumbo...simulation and parallel stuff...filming high-rise apartments with caves stuffed in them to achieve something that may not be optimal...even dropped authentication somewhere in there. Really? I'm honestly surprised Alice and Bob didn't somehow find their way into this plot...or was that Paul and Carole.

Bartweiss 9y ago
Yeah... We eventually hit "Do we have no conveyance of knowledge when you cannot simulate with successive attempts?" Which is not what I generally class as children's-story language. But the statistical argument is even harder - accepting that a low enough probability (more accurately, p value) implies a non-random source of a phenomenon is not obvious. I suspect that the initial usage would be ok, where Ali Baba says he didn't guess wrong 40 times. But the coin flip idea with Mick isn't intuitive and isn't really explained. The lead-in is interesting, and it's a clever story, but it lost the plot on target audience pretty badly.

jstanley 9y ago

I don't like this example of a ZKP. It seems like AliBaba could conclusively prove knowledge of the secret by simply being seen to enter on the left and return on the right. No interaction necessary, and it's conclusively proven in only one iteration. Am I missing something?

y7 9y ago
Perhaps if someone else stood at the entrance of the fork, they could hear him mutter the secret phrase.
Ar-Curunir 9y ago
It's not zero knowledge; if I record it then someone else will be convinced that Ali Baba knows the secret. A normal interactive ZKP should not have such a property.
- n4r9 9y ago
  > if I record it then someone else will be convinced that Ali Baba knows the secret Isn't that exactly what they're trying to do? Prove that Mick Ali knows the secret? I thought the zero-knowledge part is in showing that Mick Ali knows the secret but without knowing/revealing the secret itself. EDIT: On a second reading I see your point. The paper says "the reporter could not pass on his conviction to the judges".
- Spivak 9y ago
  But nothing about the story will actually change. The second reporter will use editing to make the the actor appear to go in the left and come out the right. Then when they go before the judge there's no difference between the real and fake tapes so it's again unconvincing. Since the author allowed the use of video editing in the story anything that isn't seen in person is unconvincing.

retox 9y ago

My understanding broke down when they introduced the Israeli connection, I couldn't understand what point was being made.

Bartweiss 9y ago
It's not very well written - this starts out as a children's story but rapidly transitions into 'conveyance' and 'authentication'. Simply: you can authenticate by testing one binary value many times (the cave), but you can shorten the handshake process by adding multiple secrets or multiple possibilities for each secret-test. The goal is to create a result which is highly improbable without secret knowledge, and you can trade off different values (number of secrets, number of handshakes, size of secrets) to achieve that. I confess I don't understand the last line of that section about 'conveyance'. The process appears robustly ZKP even without successive attempts.