3 ms·
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 i
by 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 agoWhat does "cut the deck" mean here, precisely? I feel like this word is fuzzy & can mean several things.
- Emigre_ 4y agoYou 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 agoOkay 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.
- elefanten 4y agoThe 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 agoNo, the order of the cards is preserved. The "cutting" of the deck is just a rotation.
- once_inc 4y agoI 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.
- adg001 4y agoI 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 agoHi. 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 agoHi! 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 agoWhile 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 agoIf 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 agoYou 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 agoI 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 agoJust 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".