Zero Knowledge Proofs

Apr 4, 2022

How do you prove that you know something secret without revealing the secret?

Let's say that Alice wants to prove to her red-green color blind friend Bob that two otherwise indistinguishable balls, one green, and one red, are different colors – without revealing which is green and which is red.

Alice gives the balls to Bob. Next, Bob puts the balls behind his back, randomly switching hands or keeping them in the same hand 50% of the time.

Alice has to then "guess" whether Bob switched or didn't switch hands. If they are different colors, Alice should be able to guess correctly 100% of the time. If they are the same, she can't do better than 50% in the long run. The more guesses ("proofs") Alice performs, the higher the probability that Alice can tell the balls apart (2-t).

Alice has proved that she can tell the balls apart without revealing to Bob which ball is green and which is red.

When you authenticate ("type in your password") to a website, many sites use something called Secure Remote Password (SRP) protocol. Instead of sending your password or a hash of your password across the network, SRP relies on a zero knowledge proof – the user demonstrates that they know the password to the server without revealing the password or anything from which the password can be derived.

The protocol is a bit difficult to explain (and implement!), but you can read about it more here.