6 ms·

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

163 points by ColinWright 4y ago

littlestymaar 4y ago
Jacques Patarin[1], my cryptography teacher at university introduced us with zero-knowledge proofs with a simple real-life zero knowledge scheme. All you need is 5 cards, 3 identical red and 2 identical blacks. You give one black and one red to each person (Alice and Bob), and keep the last red. The scheme is the following: Alice will puts her two cards ON TOP of the remaining red card: to say yes, she puts her black card on top of her red card, to say no she does the opposite (red on top of black). Bob will put his pair of cards BELOW the remaining red card, and to say yes he puts his black card at the bottom, with his red card in between, and to say no he does the opposite. Then you cut the deck enough times to obfuscate who've done what, and you know that they've both day yes if you have the two blacks cards next to each other (or both at each ends of the deck). If anyone (or both of them) said no, you'd have black cards separated by one red card. [1] https://fr.wikipedia.org/wiki/Jacques_Patarin https://fr.wikipedia.org/wiki/Jacques_Patarin
- maxbond 4y ago
  What does "cut the deck" mean here, precisely? I feel like this word is fuzzy & can mean several things.
  - Emigre_ 4y ago
    You divide the cards stack in two and put the top part at the bottom of the other part (which was the bottom part and will be now the top). The relative order of the cards is maintained: you don’t shuffle them. But if you cut them in this way several times, it obfuscates the original location of the cards (as it’s in practice impossible to follow their position changes) so you can’t tell who put which card where. Therefore the final arrangement, when revealed, is anonymized.
    - maxbond 4y ago
      Okay gotcha, what was confusing me was how we could randomize it and preserve the relationships of the cards at the same time, but I see now this shuffle is more like "secure by magic trick" than "secure by cryptography", that makes sense. Or equivalently, we put it into a black box, that flips a secure coin, and either does or doesn't swap the cards. Thank you.
      - user5678 4y ago
        No, it is not magic. It really is cryptography.
        maxbond 4y ago
        Yeah sorry, my original wording was confusing, I've tried to clarify that the _shuffle_ is the magic trick, the overall cryptosystem is real.
  - elefanten 4y ago
    The only thing that makes sense is keeping the middle red card in place and swapping the top two for the bottom two repeatedly? Anything else could change the answers? I dont get the exercise
    - deleted 4y ago
      [deleted]
    - Ma8ee 4y ago
      No, the order of the cards is preserved. The "cutting" of the deck is just a rotation.
- once_inc 4y ago
  I personally prefer the red ball - green ball version, where a colourblind person can find out if both balls are the same color or not. Simpler, with fewer variables and still very clean in its explanation.
  - kikowi 4y ago
    Can you send a link to the red ball - green ball version?
    - jhugo 4y ago
      Google gives https://www.senzilla.io/blog/2018/01/14/two-balls-and-the-colour-blind-friend/ https://www.senzilla.io/blog/2018/01/14/two-balls-and-the-co... as the first result
- adg001 4y ago
  I have designed one of such card decks and released it under an open source license at DKC - Dining Kid-Cryptographers [0]. This was done as part of an EU Hackathon at Google, Belgium. [0] Dining Kid-Cryptographers, https://github.com/secYOUre/DKC https://github.com/secYOUre/DKC
  - daveloyall 4y ago
    Hi. Could you add a section that explains what this is about? The linked repo does not explain what the objective of the game is supposed to be. I understand that the game is related to "the dining cryptographers", but I haven't memorized that piece. I read it once? I can probably find it on Wikipedia? I recommend making your game a self-contained work that does not rely on at least one of the players remembering some details about a very specific thought experiment.
    - adg001 4y ago
      Hi! Thanks for your feedback, this is appreciated. While there is no background information about the game in the DKC repository at the moment, the game comes with a set of cards where the equipment, rules, and finishing criteria are described [1]. If there is interested for that, I will add more context on the game and its contribution towards understanding secure multi-party computations for the youngest. I may still have the slide deck I used to present this work at the end of the hackathon, which may provide some further introductory material. [1] DKC's rules https://github.com/secYOUre/DKC/tree/master/self-print/300-dpi-png/rules https://github.com/secYOUre/DKC/tree/master/self-print/300-d...
- anilakar 4y ago
  While the cryptographic part is easily understandable, what are the practical uses of this scheme? It can only verify half of the bits on average.
  - jlokier 4y ago
    If you can verify half of a set of bits, sometimes you can use an error-correcting code to verify a full set of bits. Or sometimes to verify a property of those bits. Think of RAID storage. If some drives can't be read, but not too many, you can still read all the data.
  - bombcar 4y ago
    You could use this to allow two people that both need to say "yes" without anyone else knowing who said "no" if the two yes doesn't occur. However, it does leak knowledge to Alice and Bob; if either said yes they will know what the other chose. This is probably unavoidable.
- SamBam 4y ago
  I don't really understand this. Who is hiding what from whom? Is the idea that the outside observers can discover that either Alice or Bob said no, but not know which one? Why do that with five cards? Why can Alice and Bob not just hand a single card to you, saying "Yes" or "No". You then mix the cards and reveal them. Now you know if there's a "No" but not who said it.
  - grraaaaahhh 4y ago
    Just using single cards will let bystanders know when both Alice and Bob say "No". The 5 card solution makes it impossible to differentiate between when both say "No" and when only one says "No".
tromp 4y ago
The network demonstration of knowledge of the secret passage by 40 coin flips appears unnecessarily complicated. Why not simply send Mick down the left path and show him returning from the right? That directly demonstrates Mick knows a passage from left to right (at least to all observers at the fork. home viewers still worry about video editing).
- Khoth 4y ago
  To be a proper zero knowledge proof, it mustn't prove to bystanders that Mick knows the secret. With your simple proposal, everyone watching is convinced. In the more complicated version, only the person calling left/right knows for sure. As far as everyone else knows, Mick doesn't actually know the secret and the reporter colluded with Mick to pre-arrange a sequence of left/right calls.
  - true_repairman 4y ago
    Why should bystanders not know? It seems like Micks proof is an attempt at fame, so he would want everybody to know.
    - Khoth 4y ago
      Because it's an imperfect real-world analogy for something used in cryptography
      - SamBam 4y ago
        Yeah, I understand why the author wants to turn it into a probabilistic argument, but it doesn't quite work with the circular cave analogy. You need something where the entry and the exits are different, and Mick Ali were able to use his secret to affect the outcome at the exit. What if Mick Ali were going down one of those twisty waterslide tubes, and could say his secret phrase to shunt himself off to a different fork, so he could come out at a different tube exit at the bottom?
  - tromp 4y ago
nicolas-siplis 4y ago
The explanation I read used Finding Wally as an example: I can put a piece of paper with Wally's silhouette cut off in front of the book. Align Wally to fit into the silhouette and you're done! The paper just needs to be considerably bigger than the actual book, so other people can tell I know where Wally is without actually knowing his location.
icemelt8 4y ago
I found this made up story very nostalgic.
itronitron 4y ago
I must have missed something in the telling of this story, because it sounds like their just cheating.
- ColinWright 4y ago
  Yes, you must have missed something. If you want someone to help clarify it for you then you'll need to be more specific. Who do you think is cheating? How do you think they are cheating? Why do you think they are cheating? And so on.
- true_repairman 4y ago
  I think the point is, that a zero knowledge proof only works between two parties, the proofer and the verifier. If I want to proof something to you I cant just say "Hey I showed it to Bob over there. Ask him if I'm telling the truth." But that doesnt really come through in the analogy.
  - SamBam 4y ago
    > I think the point is, that a zero knowledge proof only works between two parties Ah! I did not get that part of it. Thanks for clarifying. I don't think the story made that part clear enough. For example, in the epilogue it says "Countless people saw Mick Ali on television, and he became famous." But, as you say, one of the main points was that watching it on television shouldn't have been enough to convince the viewers at home. They could have been watching the faked version. It would have been clearer if the epilogue had said "Countless viewers saw Mick Ali on television and remained skeptical, but the reporter himself was convinced Ali must have been telling the truth."
jlokier 4y ago
These days I'm working on "proof of execution" and "proof of data availability", which are an interesting application of zero-knowledge proofs to very large sequences of values. The steps aren't revealed, but the rule which the steps must follow is revealed. It's almost magical how it's possible to prove that N billion steps of a simulated virtual computer, run exactly according to specification, complete with CPU and memory, given a particular set of input files (or even a hash of an input) and program (or hash of a program), produces a particular set of output files. All summarised in a short proof that a verifier can easily and quickly check, so it doesn't have to redo the computation itself - it can trust the outputs it receives, due to the proof.
- orbat 4y ago
  Interesting! Sounds somewhat like what the Cairo programming language & VM does https://www.cairo-lang.org https://www.cairo-lang.org; Turing-complete provable computation using a fairly funky "arithmetic" CPU architecture.
  - jlokier 4y ago
    Yes, like Cairo. In fact I almost applied to a job working with Cairo recently, but I was told someone else had just started it. It's possible to build more standard CPUs as well which use ordinary arithmetic, logic and memory, at some cost to efficiency. But the cost is almost entirely borne by the prover.
- victor106 4y ago
  Interesting, any resources you can share?
  - jlokier 4y ago
    As a start I suggest you look at whatever is written about SNARK and STARK in the Ethereum world. Vitalik Buterin's blog has some good technical articles (literally look for those words in the titles). They don't cover proofs of CPU-like systems, though. There are a lot of other articles, papers, etc. I'm just suggeting those search terms as a starting point. The Cairo system from Starkware is a pretty good, modern CPU-like system (albeit using finite fields and an unusual CPU model, instead of normal numbers), which is simpler than its predecessors in some ways because the techniques have matured and they have been able to use techniques devised by many different R&D groups before that iteration. As far as I'm aware, however, performance at the billions of steps level is more on the frontier. I'd love to share details of what I've been working on, and I hope I will be able to one day. One problem is I'm looking for work, and there's an interesting company I'm negotiating with but their view of IP may prevent me from publishing my own work in this area after I've started. Meanwhile, I haven't published yet, even though I've done a lot of work on it. I do not like this, I always want to share, but...
Kenneth21 4y ago
[dead]
margarina72 4y ago
I mean when you get to the point where your kids are asking about zero-knowledge protocol instead of a new iphone...
- danlugo92 4y ago
  You have some amazing children!
nextstep 4y ago
More like how to get your kids to resent you
jimmySixDOF 4y ago
On YouTube (23 min) Computer scientist Amit Sahai, PhD, is asked to explain the concept of zero-knowledge proofs to 5 different people; a child, a teen, a college student, a grad student, and an expert. Using a variety of techniques, Amit breaks down what zero-knowledge proofs are and why it's so exciting in the world of cryptography. Amit Sahai, PhD, is a professor of computer science at UCLA Samueli School of Engineering. From S1 E16 of Computer Scientist Explains One Concept in 5 Levels of Difficulty | WIRED https://youtu.be/fOGdb1CTu5c https://youtu.be/fOGdb1CTu5c
forestjc 4y ago
Dusk explanation with Where's Waldo is also great https://www.youtube.com/watch?v=dS5UUJpylT4 https://www.youtube.com/watch?v=dS5UUJpylT4
363849473754 4y ago
what math background is needed to specialize in ZKP?
dang 4y ago
Related: How to explain zero-knowledge protocols to your children (1998) [pdf] - https://news.ycombinator.com/item?id=14261067 https://news.ycombinator.com/item?id=14261067 - May 2017 (41 comments) How to explain zero-knowledge protocols to your children - https://news.ycombinator.com/item?id=12059309 https://news.ycombinator.com/item?id=12059309 - July 2016 (2 comments) How to Explain Zero-Knowledge Protocols to Your Children (1998) [pdf] - https://news.ycombinator.com/item?id=10400757 https://news.ycombinator.com/item?id=10400757 - Oct 2015 (6 comments) How to explain zero-knowledge protocols to your children (1998) [pdf] - https://news.ycombinator.com/item?id=8349721 https://news.ycombinator.com/item?id=8349721 - Sept 2014 (13 comments)
belkarx 4y ago
There's a nice SE thread about this: https://security.stackexchange.com/questions/86823/how-can-i-explain-zero-knowledge-proof-to-an-end-user https://security.stackexchange.com/questions/86823/how-can-i...
etamponi 4y ago
... unfortunately I didn't understand how this story relates to zero-knowledge protocols....

163 points by ColinWright 4y ago

Jacques Patarin[1], my cryptography teacher at university introduced us with zero-knowledge proofs with a simple real-life zero knowledge scheme. All you need is 5 cards, 3 identical red and 2 identical blacks. You give one black and one red to each person (Alice and Bob), and keep the last red. The scheme is the following: Alice will puts her two cards ON TOP of the remaining red card: to say yes, she puts her black card on top of her red card, to say no she does the opposite (red on top of black). Bob will put his pair of cards BELOW the remaining red card, and to say yes he puts his black card at the bottom, with his red card in between, and to say no he does the opposite. Then you cut the deck enough times to obfuscate who've done what, and you know that they've both day yes if you have the two blacks cards next to each other (or both at each ends of the deck). If anyone (or both of them) said no, you'd have black cards separated by one red card. [1] https://fr.wikipedia.org/wiki/Jacques_Patarin https://fr.wikipedia.org/wiki/Jacques_Patarin

maxbond 4y ago
What does "cut the deck" mean here, precisely? I feel like this word is fuzzy & can mean several things.
- Emigre_ 4y ago
  You divide the cards stack in two and put the top part at the bottom of the other part (which was the bottom part and will be now the top). The relative order of the cards is maintained: you don’t shuffle them. But if you cut them in this way several times, it obfuscates the original location of the cards (as it’s in practice impossible to follow their position changes) so you can’t tell who put which card where. Therefore the final arrangement, when revealed, is anonymized.
  - maxbond 4y ago
    Okay gotcha, what was confusing me was how we could randomize it and preserve the relationships of the cards at the same time, but I see now this shuffle is more like "secure by magic trick" than "secure by cryptography", that makes sense. Or equivalently, we put it into a black box, that flips a secure coin, and either does or doesn't swap the cards. Thank you.
    - user5678 4y ago
      No, it is not magic. It really is cryptography.
      - maxbond 4y ago
        Yeah sorry, my original wording was confusing, I've tried to clarify that the _shuffle_ is the magic trick, the overall cryptosystem is real.
- elefanten 4y ago
  The only thing that makes sense is keeping the middle red card in place and swapping the top two for the bottom two repeatedly? Anything else could change the answers? I dont get the exercise
  - deleted 4y ago
    [deleted]
  - Ma8ee 4y ago
    No, the order of the cards is preserved. The "cutting" of the deck is just a rotation.
once_inc 4y ago
I personally prefer the red ball - green ball version, where a colourblind person can find out if both balls are the same color or not. Simpler, with fewer variables and still very clean in its explanation.
- kikowi 4y ago
  Can you send a link to the red ball - green ball version?
  - jhugo 4y ago
    Google gives https://www.senzilla.io/blog/2018/01/14/two-balls-and-the-colour-blind-friend/ https://www.senzilla.io/blog/2018/01/14/two-balls-and-the-co... as the first result
adg001 4y ago
I have designed one of such card decks and released it under an open source license at DKC - Dining Kid-Cryptographers [0]. This was done as part of an EU Hackathon at Google, Belgium. [0] Dining Kid-Cryptographers, https://github.com/secYOUre/DKC https://github.com/secYOUre/DKC
- daveloyall 4y ago
  Hi. Could you add a section that explains what this is about? The linked repo does not explain what the objective of the game is supposed to be. I understand that the game is related to "the dining cryptographers", but I haven't memorized that piece. I read it once? I can probably find it on Wikipedia? I recommend making your game a self-contained work that does not rely on at least one of the players remembering some details about a very specific thought experiment.
  - adg001 4y ago
    Hi! Thanks for your feedback, this is appreciated. While there is no background information about the game in the DKC repository at the moment, the game comes with a set of cards where the equipment, rules, and finishing criteria are described [1]. If there is interested for that, I will add more context on the game and its contribution towards understanding secure multi-party computations for the youngest. I may still have the slide deck I used to present this work at the end of the hackathon, which may provide some further introductory material. [1] DKC's rules https://github.com/secYOUre/DKC/tree/master/self-print/300-dpi-png/rules https://github.com/secYOUre/DKC/tree/master/self-print/300-d...
anilakar 4y ago
While the cryptographic part is easily understandable, what are the practical uses of this scheme? It can only verify half of the bits on average.
- jlokier 4y ago
  If you can verify half of a set of bits, sometimes you can use an error-correcting code to verify a full set of bits. Or sometimes to verify a property of those bits. Think of RAID storage. If some drives can't be read, but not too many, you can still read all the data.
- bombcar 4y ago
  You could use this to allow two people that both need to say "yes" without anyone else knowing who said "no" if the two yes doesn't occur. However, it does leak knowledge to Alice and Bob; if either said yes they will know what the other chose. This is probably unavoidable.
SamBam 4y ago
I don't really understand this. Who is hiding what from whom? Is the idea that the outside observers can discover that either Alice or Bob said no, but not know which one? Why do that with five cards? Why can Alice and Bob not just hand a single card to you, saying "Yes" or "No". You then mix the cards and reveal them. Now you know if there's a "No" but not who said it.
- grraaaaahhh 4y ago
  Just using single cards will let bystanders know when both Alice and Bob say "No". The 5 card solution makes it impossible to differentiate between when both say "No" and when only one says "No".

tromp 4y ago

The network demonstration of knowledge of the secret passage by 40 coin flips appears unnecessarily complicated. Why not simply send Mick down the left path and show him returning from the right? That directly demonstrates Mick knows a passage from left to right (at least to all observers at the fork. home viewers still worry about video editing).

Khoth 4y ago
To be a proper zero knowledge proof, it mustn't prove to bystanders that Mick knows the secret. With your simple proposal, everyone watching is convinced. In the more complicated version, only the person calling left/right knows for sure. As far as everyone else knows, Mick doesn't actually know the secret and the reporter colluded with Mick to pre-arrange a sequence of left/right calls.
- true_repairman 4y ago
  Why should bystanders not know? It seems like Micks proof is an attempt at fame, so he would want everybody to know.
  - Khoth 4y ago
    Because it's an imperfect real-world analogy for something used in cryptography
    - SamBam 4y ago
      Yeah, I understand why the author wants to turn it into a probabilistic argument, but it doesn't quite work with the circular cave analogy. You need something where the entry and the exits are different, and Mick Ali were able to use his secret to affect the outcome at the exit. What if Mick Ali were going down one of those twisty waterslide tubes, and could say his secret phrase to shunt himself off to a different fork, so he could come out at a different tube exit at the bottom?
- tromp 4y ago

nicolas-siplis 4y ago

The explanation I read used Finding Wally as an example: I can put a piece of paper with Wally's silhouette cut off in front of the book. Align Wally to fit into the silhouette and you're done! The paper just needs to be considerably bigger than the actual book, so other people can tell I know where Wally is without actually knowing his location.

icemelt8 4y ago

I found this made up story very nostalgic.

itronitron 4y ago

I must have missed something in the telling of this story, because it sounds like their just cheating.

ColinWright 4y ago
Yes, you must have missed something. If you want someone to help clarify it for you then you'll need to be more specific. Who do you think is cheating? How do you think they are cheating? Why do you think they are cheating? And so on.
true_repairman 4y ago
I think the point is, that a zero knowledge proof only works between two parties, the proofer and the verifier. If I want to proof something to you I cant just say "Hey I showed it to Bob over there. Ask him if I'm telling the truth." But that doesnt really come through in the analogy.
- SamBam 4y ago
  > I think the point is, that a zero knowledge proof only works between two parties Ah! I did not get that part of it. Thanks for clarifying. I don't think the story made that part clear enough. For example, in the epilogue it says "Countless people saw Mick Ali on television, and he became famous." But, as you say, one of the main points was that watching it on television shouldn't have been enough to convince the viewers at home. They could have been watching the faked version. It would have been clearer if the epilogue had said "Countless viewers saw Mick Ali on television and remained skeptical, but the reporter himself was convinced Ali must have been telling the truth."

jlokier 4y ago

These days I'm working on "proof of execution" and "proof of data availability", which are an interesting application of zero-knowledge proofs to very large sequences of values. The steps aren't revealed, but the rule which the steps must follow is revealed. It's almost magical how it's possible to prove that N billion steps of a simulated virtual computer, run exactly according to specification, complete with CPU and memory, given a particular set of input files (or even a hash of an input) and program (or hash of a program), produces a particular set of output files. All summarised in a short proof that a verifier can easily and quickly check, so it doesn't have to redo the computation itself - it can trust the outputs it receives, due to the proof.

orbat 4y ago
Interesting! Sounds somewhat like what the Cairo programming language & VM does https://www.cairo-lang.org https://www.cairo-lang.org; Turing-complete provable computation using a fairly funky "arithmetic" CPU architecture.
- jlokier 4y ago
  Yes, like Cairo. In fact I almost applied to a job working with Cairo recently, but I was told someone else had just started it. It's possible to build more standard CPUs as well which use ordinary arithmetic, logic and memory, at some cost to efficiency. But the cost is almost entirely borne by the prover.
victor106 4y ago
Interesting, any resources you can share?
- jlokier 4y ago
  As a start I suggest you look at whatever is written about SNARK and STARK in the Ethereum world. Vitalik Buterin's blog has some good technical articles (literally look for those words in the titles). They don't cover proofs of CPU-like systems, though. There are a lot of other articles, papers, etc. I'm just suggeting those search terms as a starting point. The Cairo system from Starkware is a pretty good, modern CPU-like system (albeit using finite fields and an unusual CPU model, instead of normal numbers), which is simpler than its predecessors in some ways because the techniques have matured and they have been able to use techniques devised by many different R&D groups before that iteration. As far as I'm aware, however, performance at the billions of steps level is more on the frontier. I'd love to share details of what I've been working on, and I hope I will be able to one day. One problem is I'm looking for work, and there's an interesting company I'm negotiating with but their view of IP may prevent me from publishing my own work in this area after I've started. Meanwhile, I haven't published yet, even though I've done a lot of work on it. I do not like this, I always want to share, but...

Kenneth21 4y ago

[dead]

margarina72 4y ago

I mean when you get to the point where your kids are asking about zero-knowledge protocol instead of a new iphone...

danlugo92 4y ago
You have some amazing children!

nextstep 4y ago

More like how to get your kids to resent you

jimmySixDOF 4y ago

On YouTube (23 min) Computer scientist Amit Sahai, PhD, is asked to explain the concept of zero-knowledge proofs to 5 different people; a child, a teen, a college student, a grad student, and an expert. Using a variety of techniques, Amit breaks down what zero-knowledge proofs are and why it's so exciting in the world of cryptography. Amit Sahai, PhD, is a professor of computer science at UCLA Samueli School of Engineering. From S1 E16 of Computer Scientist Explains One Concept in 5 Levels of Difficulty | WIRED https://youtu.be/fOGdb1CTu5c https://youtu.be/fOGdb1CTu5c

forestjc 4y ago

Dusk explanation with Where's Waldo is also great https://www.youtube.com/watch?v=dS5UUJpylT4 https://www.youtube.com/watch?v=dS5UUJpylT4

363849473754 4y ago

what math background is needed to specialize in ZKP?

dang 4y ago

Related: How to explain zero-knowledge protocols to your children (1998) [pdf] - https://news.ycombinator.com/item?id=14261067 https://news.ycombinator.com/item?id=14261067 - May 2017 (41 comments) How to explain zero-knowledge protocols to your children - https://news.ycombinator.com/item?id=12059309 https://news.ycombinator.com/item?id=12059309 - July 2016 (2 comments) How to Explain Zero-Knowledge Protocols to Your Children (1998) [pdf] - https://news.ycombinator.com/item?id=10400757 https://news.ycombinator.com/item?id=10400757 - Oct 2015 (6 comments) How to explain zero-knowledge protocols to your children (1998) [pdf] - https://news.ycombinator.com/item?id=8349721 https://news.ycombinator.com/item?id=8349721 - Sept 2014 (13 comments)

belkarx 4y ago

There's a nice SE thread about this: https://security.stackexchange.com/questions/86823/how-can-i-explain-zero-knowledge-proof-to-an-end-user https://security.stackexchange.com/questions/86823/how-can-i...

etamponi 4y ago

... unfortunately I didn't understand how this story relates to zero-knowledge protocols....