Week 6: What are Zero Knowledge Proofs?

Imagine a ring-shaped cave with a single entry point dividing into paths A and B. Somewhere deep in there, there is a magic door connecting the paths that opens whenever someone utters a secret password.

Assume that I need to prove to you that I know that password but cannot reveal it under any circumstances. How can we achieve it?

First, you go out of the way while I enter the cave and randomly select one of two possible paths. You then approach the entry point and shout a random request: “Exit from path B!”. If indeed I know the secret password, then opening the door becomes easy for me. As long as I am able to leave the cave through the requested path in each round of our experiment, after twenty tries you become completely convinced of this fact and still remain clueless about the word. This is how the well-known Ali Baba Cave works.

And it turns out that the same technique of proving knowledge of passwords without disclosing any private data is widely used in modern cryptography to verify user data. Such proofs are known as Zero-Knowledge Proofs (ZKP).