Socialist millionaire protocol
I love zero knowledge proofs. My professor in college explained the idea in what I thought was an especially clear way:<p>Say that you and a friend are reading a Where's Waldo book, and you want to prove that you have found Waldo, but you don't want to tell your friend where Waldo is. This seems impossible. However, you could take a large piece of cardboard, cut out a Waldo-shaped hole, and place it over the book. Now you have proven that you can find Waldo.<p>"But wait!" cries your friend. "How do I know the book is even under there? Let me see." But you can't do that, since he knows roughly the spot Waldo would be if you lifted the cardboard.<p>So, you get a second piece of cardboard and put it on top of the first. Now, you play a game. You ask your friend whether you should lift one piece of cardboard (to verify the picture of Waldo) or two pieces (to verify that the book is beneath the second piece). You can play this game as many times as required for your partner to gain a reasonable confidence that you're not cheating.<p>And that's a zero knowledge proof.