Cryptography 101: Zero Knowledge Proofs

In this post I will give a high-level explanation of Zero Knowledge Proofs and if there will be any demand for practical (mathematical or programmatical) information, I'll post another article.

Disclosure: I'm a computer science student and enthusiast. There might be slight mistakes in professional terms. I'd like anyone who finds mistakes to correct me and I'll edit the post.

Let's assume that I have gained a top secret knowledge (Um, like a cupon for a free pizza for life) and I'd like to keep it for myself, and yet, I'd like to brag about it and prove (or at least convince at a very high probability) to other people that I posses this knowledge. Sounds impossible?

Well it is possible. This simple riddle will demonstrate:

Your best friend, Bob claims that he has a superpower. Allegedly, he knows the exact number of leaves on any given tree at any time. (Obviously, it is a very poweful knowledge). So, you take Bob to the nearest forest and challenge him. But how can you know he's not bluffing, without you counting the leaves yourself?

You can rephrase the question and ask: "How Bob can prove he knows the number of the leaves on the tree at any given time, without knowing the number of the leaves yourself?" or How can Bob prove that he knows something without me gaining any knowledge at all about this subject?

If you answered the riddle, great, you rock.

If you haven't, this is the solution; You would blindfold Bob in a manner that you're 100% positive that he sees nothing. As this is all set, you would choose to take a leaf of the tree, or do nothing and then ask Bob whether there was any change with the number of the leaves on the tree.

If he's wrong, you busted him. But if he's right, he is 50% bluffing, if a 50% odd doesn't satisfy your susceptive soul, then go for another round, at this time Bob will only have 25% chance of bluffing. 

At the 10th round, Bob would have only have ~0.09%  chance of bluffing, and you can go on and on until you're content. And you have either approved or refuted Bob's claim while gaining no knowledge at all about the number of the leaves on the tree.

There are three requirements for a proof to be zero proof, from Wikipedia:

1. Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
2. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
3. Zero-knowledge: if the statement is true, no cheating verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier.

Now, that you believe that ZKP are possible, the classic use case of such proof is an authentication protocol in which the user proves the server that he knows his password, never sending any information that can be used to infer his password. There is also an application of zero knowledge proofs on the blockchain 

A common protocol called Feige-Fiat-Shamir after it's authors. The protocol is based on a modular arithmetic problem, of finding a root for a given number at a finite field.

More of this, at the next post