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
Art of the Problem is probably the transformative channel that made me see how and why Youtube is an excellent tool to learn.
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.
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.
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.
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.
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.
Awesome little paper. I wish there were more papers like this!
BTW, you guys might enjoy https://betterexplained.com - the author explains math concepts in new more intuitive ways.
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
> 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.
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.
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.
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.
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?
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.
"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.
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.
> He can go left and come out right to demonstrate that he knows the secret - without revealing the secret
Correct
> The reporter would still not know how he did it
Correct
> and could not pass his conviction on to the judges
Incorrect, in this case he could pass on his conviction to the judges simply by showing them the tape where Mick goes in left and comes out right in a single unbroken take. Such a tape cannot be faked by the fake reporter.
> Such a tape cannot be faked by the fake reporter.
This is where I disagree. The second reporter will just tape the actor going in the left, editing magic, and observe him coming out the right. Both tapes will be indistinguishable.
In the original story the second reporter couldn't produce an unbroken tape between successive trials like the first reporter, so that can't be the litmus for proof.
If you want, you can forget about recording and tapes. Assume there was another person (unaffiliated with Mick or the reporter) standing next to the reporter while the experiment was being conducted. The rest of the story can stay the same. Mick also does not want this person to become convinced that Mick knows the secret.
Per the original story, this second person cannot know whether Mick coming out of the path that the reporter announces is a genuine display of Mick's ability or simply a collusion between Mick and the reporter. But if we go with the plan to observe Mick going in one path and out the other then this second person can become convinced of 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.
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.
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.
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.
My preferred example: I want to prove to you I know how to do a card trick. I have you pick a card memorize it and put it in the deck. Then I am able to reproduce your card. I can do this a million times to convince you, but never reveal the method of the trick to you. As long as when the verifier picks a card they don't show it to anyone, any other spectators can't know if we are colluding and can't determine how the trick is done.
I prefer this example as it is easier to visual knowing how to do a card trick than it is to understand how you would identify the number of beans in a jar. It also allows you to further explain things like collisions as a magic trick can have multiple methods. Or how by observing enough cases of the trick and "thinking" really hard you might be able to figure out how the trick is done. The crappier the magician the easier it is to figure out their trick.
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.
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.
I think you're assuming that you can count the jar between pulls. (That was my initial reading also.) In that case, you guess your first number, count the jar, and then work backwards for all subsequent pulls.
But on rereading, the info to prove isn't "I know how many beans were here to start", it's "I'm capable of counting this jar of beans by looking at it". So if you guess right on the first trial, you still won't know the beans-remaining count, and will have to guess on the next trial too.
This is made super confusing by the claim that it's a ZKP of the initial count. That's narrowly true, but the real question at hand is whether you can count the beans.
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
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
Art of the Problem is probably the transformative channel that made me see how and why Youtube is an excellent tool to learn.