Explaining Zero-Knowledge-Proof strategies in an abstract manner through a hypothetical story
At the entrance of a club, there stands a security guard who has to verify that only people who has some pass-code can enter. If the guard prompts for the next person to tell him the pass-code, the other people in the line could potentially evesdrop. Therefore, the club came up with an interesting idea of asking the people to perform some mathematical question that only the person who actually knows the pass-code can give the right answer to. Problem solved, right?
|Image generated by OpenAI's DALL-E|
Well, what if the evesdropper listens to both the question and the answer and calculates back what the password could be? This could very well happen if the question that the guard asks is something like, "What is the pass-code times one hundread?" or "What is the pass-code minus twenty?". Taking this a bit further, if the guard ask "What is the pass-code plus five and then square it", then there is a fifty percent chance that the evesdropper could backcalculate the original pass-code. In fact, if the guard had asked to calculate an N-th degree polynomial with the password, then evesdropper would effectively wind up with N possibile answers.
If we keep thinking in this direction, we could potentially come up with some bizarre ideas on what question to ask such that lesser and lesser amount of knowledge is gained by the evesdropper. If we could come up with a strategy wherein the evesdropper effectively gains no information about the pass-code, it would be ideal. Otherwise, if the evesdropper remains in the line for a long amount of time, then he/she could potentially collect a lot of information about the pass-code. If the guard uses different degree polynomials, chances are that the evesdropper could arrive at the pass-code after a few question and answer sessions.
It is also worth noting that in order to verify using such a method, the guard should know the pass-code himself/herself. This could be an issue when there are multiple entrances and (hence) guards, and the club management does not want it to go unnoticed when a guard tries to sneak his/her friends. Sneaking in a person could happen in two ways:
- The guard simply lets the person in.
- The guard gives away the password to this person and the person approaches any entrance with this information.
A strategy that the club management can come up with, wherein the guards can verify if the people standing in the queue has the pass-code or not, while the guards themselves do not have the pass-code, and, an evesdropper does not gain information that gets him/her close to the pass-code over time, is called a Zero-Knowledge-Proof strategy.