B (146:24)
He, Peggy made him leave. She took the, the top sheet off, he came back. He's still pissed off now because he knows Wally's there somewhere and he absolutely knows it. But he can't prove it to anybody else either. Okay, so next example. This next example demonstrates some other properties of this interesting realm. We've got two competitors. They have so far each been allowed to purchase some number of a rare and precious item from a common supplier. They want as much as they can get. They've each been allowed to purchase a certain amount. The supplier claims that both parties have been allowed to purchase the same number of these items. But as part of the purchase agreement, the supplier made them sign an NDA, a non disclosure agreement, which has bound them to keep the number of items they were each sold a secret, especially from one another. They're not allowed to divulge to anyone, especially each other, how many they have been allowed to purchase. The supplier says, I've sold you both the same amount. If they violate that NDA, they will lose any opportunity to purchase any more of these precious items in the future. The problem is their competitors. They need these things and they don't trust completely. The suppliers claim their assertion to have sold them so far the same number. So they want to verify, or in this case, to prove, that they have both purchased the same number of items without breaching their NDA and revealing the number of items each has purchased. The items, as it turns out, are only sold in lots of 100. So they may have each purchased 100, 200, 300 or 400 of the items. They know how many they have purchased, but they don't know how many their competitor has purchased. And neither of them is allowed to reveal their purchase quantity to the other. What they want to know is whether the seller has told them the truth. Just that, the truth about having sold them each the same number of units. Yes or no. What they need is a zero knowledge proof. And over drinks one night, they devise a way to accomplish this. They get four identical small lockable boxes, each having a differently keyed lock. So four box, four lockable boxes and four keys, one, one for each box. Into the top of each box they cut a small slit through which a piece of paper can be dropped. You know, like a little ballot box. The four boxes are labeled 100, 200, 300 and 400, corresponding to the number of items each has been able to purchase from their common supplier. And each box is locked with its respective key which is left in the lock. And all four boxes are placed alone on a table in a room with a door. They also prepare four slips of paper. One piece, one slip of the paper has a big green check mark on it, and the other three have a big red X. The two competitors gather outside the room containing these four boxes, and they flip a coin to decide who's going to go first. The winner of the coin toss enters the room and closes the door behind him. He goes to the box which represents the quantity of items he has purchased. 100, 200, 300, or 400. He removes its key and places it in. In his pocket. He also removes the other three keys from the other three boxes. So now all the boxes look the same, right? They're just. There are three. There are four locked boxes. There's no keys. He. He leaves the room, closes the door behind him. Then together, the two of them destroy the three keys for the other boxes, which will never be opened. Okay? And that first guy has kept the key for the one box that corresponds to how many items he's purchased. Next, the other competitor takes the four slips of paper into the room and closes the door behind him. He drops the slip of paper having the big green check mark into the top slot of the box, which corresponds to the quantity of items he has been allowed to purchase from their common supplier. Again, 100, 200, 300, 400, whichever box. And he drops the three big red X slips into the other three boxes. And then he exits the room and closes the door. Finally, the first person who removed and retained that one key from the one box, which only opens the box corresponding to the quantity of items he has purchased, enters the room and closes the door. He. He goes to that box. He returns to the box for which he has the key and use it. And that's. That's the. That that key will only open that box. Uses the key to open the box and withdraws the slip of paper that box contains. He relocks the box so now they're all locked again. And exits the room with a slip of paper and shows it to the competitor. Only if the box he had the key for was the same box as his competitor dropped the green check mark paper into, will he have been able to successfully withdraw a piece of paper containing a green check mark. And in that case, they will have confirmed to each other that they have each been able to purchase the same quantity of items from their shared supplier. In other words, if the first competitor withdrew a slip of paper with a red X, they will both know that they had been lied to by their seller. But that is all they know. They only get a yes or no. They don't learn anything else. Neither of them will have learned how many of the items the other has been able to purchase. So they will not have discovered, they will not have disclosed that to the other and thus will not have breached their purchase agreement. They did not breach their agreement. They did not breach their NDA. If they, if they don't know how much. If, if they learn if, if they, if, if a red X gets pulled out after that, that, that third round, they only know they did not, they have not both purchased the same amount of, but not how much. So there again is. That is an interactive zero knowledge proof where nothing is learned, no information is gained other than the. The. The verification of an assertion. Okay, and for the third example, we're going to look at one that involves statistical proof. This is another famous thought experiment often referred to as Ali Baba's Cave. And for this we return to Peggy and Victor. A cave is discovered which has an odd shape. It has a cave tunnel shaped in a ring with an entrance in the side of the mountain on one side of the ring shaped tunnel and a locked door which completely blocks the tunnel at the opposite. Deep inside the mountain, the opposite side of the ring. So the locked door, which is far away from the tunnel's opening from the outside, cannot be seen since it's deepest in the back of the ring tunnel. Peggy, who returns as our prover, claims to have discovered the magic word that can unlock the door from either side. But once again, Victor. Oh, Victor. He's skeptical before this. Victor. And it's understandably why he's skeptical. He had tried every word he could think of. No matter what he says to the door, it remains stubbornly locked. He doubts Peggy's claim to have discovered the magic word. He thinks, you know, he knows all the words that she knows. And especially all that business with Wally. He's a bit more annoyed than ever with her. For her part, Piggy is willing to work to convince Victor that she knows the magic word. But she insists upon doing it in a way that cannot also be used to prove it to anyone else. Remember, that's part of our, our, our. Our goal here is not being able to. To prove what is proven to the Victor, the Verifier to anyone else. So, and, and this is a problem. For whatever reason, that's crucial because, you know, Peggy wants to keep this secret. She's willing to prove it to Victor. She doesn't want Victor to be able to go off and and prove it elsewhere. Remember, the formal requirements for zero knowledge proofs are that the the. Even if the verifier has been convinced of the truth of the prover's statement, it the verifier should nevertheless be unable to prove the statement to any other third party. Okay, so if Victor and Peggy were to simply stand at the cave's opening with the two tunnels heading off in opposite directions, clockwise and counterclockwise around the ring, and if Peggy were to go down one path, say the magic words to the door, and then a few minutes later emerge from the other path, Victor would obviously be immediately convinced that Piggy had to have been able to open the door with the magic word because the only way she could have completely circumnavigated the ring Tuttle would if would be if she was able to open and pass through the magic word door. But if Victor were to record Piggy's accomplishment with his phone's video camera, or if someone other than Victor happened to also be standing there too, watching Piggy do this, either of those would constitute incontrovertible proof of Piggy's grasp of magical cave door operation. And that would be unacceptable to her. She refuses to do that. She's willing to convince Victor, but you know, you know and, and you know she's stubborn. We've already seen her use a large sheet of paper to frustrate Victor. Piggy's pretty clever. So she's come up with a way to prove to Victor and Victor alone that she can pass through that door at the far back side of the Ring tunnel cave, while at the same time preventing a video recording from creating solid evidence or even evidence for someone standing by and silently observing the same thing that Victor observes. Once again, Peggy and Victor stand at the mouth of the cave with the two tunnels diverging in opposite directions. Inside the mountain, Peggy has Victor turn around so that she is unobserved and has him start counting down from 10. She keeps her eye on him while she disappears from sight down the tunnel of her choosing. Once Victor's count reaches zero, he turns around and shouts into the tunnel that he wants her to and, and, and, and shouts like, you know, into both tunnels the specific tunnel he wants her to emerge from. If Peggy happened to go down that side of the ring, she simply retraces her path and comes out the side that Victor asked her to. But if she went down the other side, she must use her magic word to open the door and emerge from the path Victor has requested. So what do we know? And what does Victor know at this point? What we know is that there's a 5050 chance that piggy may have initially gone down the same path that Victor asked her to return from. So she would not have needed to use her magic word. Victor knows that she got it correct once because he's only asked her once so far. But of course that might have just been beginner's luck. So they do it again. As before, Victor turns us back, counts down from 10, which is what Peggy insists upon. Peggy herself chooses a direction, gets to the door and waits for Victor to shout out which path he wants her to return from. Since Peggy does know the magic word, she is always able to succeed. But if she did not know the magic word, and if they kept playing this game, the chances get greater and greater that Victor will ask her to return on the path opposite the one she went down. And Victor will have his, well, his victory of proving that she never did know the magic word after all. Now we know how the statistics of this go. Right. One test is a 50, 52 tests where both must be correct. Assuming an equal probability of outcome is 1 in 4, there's a 1 in 4 chance, if Victor and Peggy do this twice, that Peggy could just get lucky, not know the word, but choose the right path both times. There's a 1 in 4 chance of that. Three tests reduces the probability to 1 and 8. Four tests, 1 in 16. Then we get to 1 in 32, 6412-825651-21024, 2048, 4096 and so on to get to 4096. One chance in 4096. That only requires 12 runs. So if Piggy did not know the secret door opening word, there would only be one chance in 4096 of her being able to get the path correct. Or all 12 times. Before long, annoying as he may be, Victor will give up and admit that Piggy must indeed be able to cross that door's threshold. Either that or she is incredibly lucky and just should go to Las Vegas. So how has this statistical variation solved Peggy's concern about keeping her magical locksmith abilities unproven to anyone else. Assuming that a camera or an observer were to turn around and be unable to see the path she took, which is the obvious requirement. Just as she has required a Victor, there would be no way for a video recording or an on the spot observer to know that she and Victor were Not conspiring. By having prearranged the sequence of tunnels, Victor would call out and Piggy would choose to return. Would choose to go down and then return from. They could have some system like take a famous phrase, ask not what you can do for your country, where a vowel in the letters of that of the words of that phrase means take the left tunnel. And a consonant in the words of that phrase means go down the right. This would allow Victor and Peggy to stage the entire event for an audience and gives Peggy the plausible deniability that she requires. And if confronted by someone who stood there or watched the video, she could say how gullible are you? Victor and I simply pre arranged the sequence of tunnels. Why else do you do you imagine I didn't just let people directly observe which path I took? It was so I could stage the whole thing. So she has plausible deniability. And you'll note that assuming that that she and Victoria did not stage the entire thing, Victor would be unable to convince the observer that she. That. That he and she did not stage it. He has no way of. He knows he was choosing paths at random, but he has no way of proving the knowledge. He now has that Piggy has the magic word to anybody else because only he knows that it was actually random. Everybody, everybody else is saying, yeah, sure, you know, we know you guys cheated somehow. There are many other physical world constructions involving colored balls and. And decks of cards. But anyway, everyone should now know by. By now have a good idea for what we're talking about. There are clearly ways to prove some statement or assertion involving other conditions without disclosing any other information about those conditions. The proof can be made while leaking zero knowledge. As an academic pursuit, a great deal of time and attention has been devoted to the formalization of zero knowledge proofs. A zero knowledge proof of some statement must satisfy three properties. The the property of completeness. Completeness means if the statement is true, that an honest verifier who's following the protocol properly will be convinced of this fact by an honest prover. Then there's the statement of soundness. If the statement is false, then no cheating prover, no matter what they do, can convince an honest verifier that it is true, except with some acceptably very small probability, like we saw with the Cave. And thirdly zero knowledge. If the statement is true, then no verifier learns anything other than the fact that the statement is true. Peggy said, Wally's there somewhere. Victor said, no, he's not. I've looked everywhere There he, you know, you're making that up. She showed him Wally through a little hole in the paper. Victor's like, wow, okay, you're right, he's there. But after she removes the paper, Victor still doesn't know where Wally is. He's, you know, he's no wiser afterwards, but now he's really upset because he knows he's there somewhere and he can't find him. So the statement is true. The no verifier learns anything other than the fact that it's true. You know, in the case of our competitors, they only learned whether or not they had both purchased the same quantity of goods, yes or no. And if not, they didn't learn anything about who was able to purchase more than the other. And later, finally with the cave, Victor was only ever able to convince himself that despite himself trying all the words he could think of, Peggy must indeed know the magic cave door opening word. And she was willing to prove it as many times as he needed to.
