The zero-knowledge proof term appears more frequently with the hype of blockchain. It is not a simple concept to understand. Therefore I will try to explain it here in layman terms using an example. The example is based on Quisquater and Guillou (Crypto 89) explanation.
Imagine a shopping mall like on the picture with only one entrance and door in the middle that opens with a secret phrase. Angelina wants to convince Brad she knows the secret without revealing it. She enters the mall leaving Brad outside and picks randomly right or left route until she gets to the door. She calls Brad’s mobile to enter the mall too. Brad does not know if she went right or left. He calls her back and tells her left or right. Angelina can arrive from left or right based on the command from Brad using the door if needed. From now on we will refer to this as the protocol.
For the first time, Brad has only 50% confidence that Angelina knows the secret. However, they keep repeating the exercise n-times. If she does not know the secret, then she would be able to cheat Brad only with probability 2-n. Therefore Brad is constantly gaining confidence, that Angelina knows the secret.
Why can’t Angelina simply make a round from left to right or vice versa to convince Brad?
The secret opening the door works only one way, and the whole point is to avoid revealing any other information than Angelina knows the secret. If Angelina would make round walk through the door, then it would be proof of knowledge and not the zero-knowledge proof.
Let’s assume Brad has a video camera to record the protocol. He throws a coin to pick right or left randomly. Jennifer and Justin would like to make a similar tape to fool Brad. They can do guessing the coin throw, and recording Jennifer walk down the guessed path. If they guessed wrong, then they would just rewind the video. Form both videos it must no be possible to tell who knows the secret and which version is staged. The point is if there is indistinguishable simulation possible, then Brad does not learn anything more from the protocol.
In more formal definition, the protocol has to have the following properties to be considered Zero-knowledge proof.
- Security — Angelina’s impostor can comply with the protocol only overwhelmingly . small probability.
- Completeness — If Angelina knows the secret, then she passes the test.
- Soundness — If an impostor can fool Brad, then there must be an alternative way between left and right and anybody can use it.
- Zero-Knowledge Property — It is possible to create a simulation based on recorded protocol (Jennifer and Justin tape in this case) that Brad is not able to distinguish that from real protocol he executed with Angelina.
Hope my explanation helped you a bit to grasp the idea of Zero-Knowledge proof and what is the difference to knowledge-proof. I highly suggest to look around the internet for other examples (e.g., with Color balls… Angelina and colorblind Brad).
Sources
- http://www.cse.scu.edu/~tschwarz/coen350/zkp.html
- https://en.wikipedia.org/wiki/Talk%3AZero-knowledge_proof
Happy Block Chaining!
— Lukas