Maths & Logic for Zero-knowledge Proofs (simplified) — Part 4
A primer for understanding the mathematical insights used to build ZK.
Questions to answer
This part will address 2 questions that need to be understood before we start the technical discussions on zero-knowledge.
1. We saw how randomness/probability was used in computationally hard problems (probabilistic polynomial time, IP). But probability implies that we can either be correct or wrong. How can we be sure we are correct? (Read 1)
2. What do we mean by “gaining” knowledge, as opposed to being zero-knowledge? (Read 2)
1. Negligible Error in Soundness
As discussed in the previous part, we saw how super-polynomial (difficult & slow) problems can be verified using probabilistic polynomial time (PPT) algorithms, i.e. Interactive Proofs (IP). But we face another problem now.
If IPs are probabilistic, then the answer given by IPs is either probably correct (or probably wrong). How can we be sure we are correct?
The simple answer — Keep repeating your process (the IP algorithm) and checking your answer. More number of times you get the expected answer, higher the probability you are guessing correctly.
Let’s understand this using some high school maths.
I have a coin and I tell my friend I know a secret way to toss that will always give me Heads. So we make a bet to prove that I know such a secret toss. Heads, I win. Tails, I lose.
I toss the coin once.
Probability I get Tails and lose the bet? 1/2.
Probability I win? Total probability - Loss = 1 – 1/2 = 1/2
I toss the coin again.
Probability I will lose again?
1/2 (probability of loss on 1st toss) * 1/2 (probability of loss on 2nd toss) = 1/4
Probability I win in second toss? Total probability - Loss = 1 – 1/4 = 3/4
What is the probability I lose if I keep tossing the coin, for say n times?
Moral of the story:
- If I really have a secret way to get Heads, I can prove it to my friend with higher certainty by repeating the coin toss more number of times.
- In terms of Interactive Proofs (IP), completeness is the same as winning the bet and margin of error in soundness is losing. You can improve completeness & decrease error in soundness by repeating the IP interactions. Using this, you can decrease your error almost close to negligible (remember this for later!).
Finally, we have completed our discussions on the various rudimentary proof systems (P, NP, IP, etc.).
If you recall, each of the above-mentioned proof systems were judged based on 3 criteria : completeness, soundness and efficiency. It’s now time for us to add a fourth criteria — zero-knowledge.
2. “Gaining” Knowledge vs Zero-Knowledge
There is an interesting feature that emerges when we try to understand what zero-knowledge is.
For the purposes in cryptography, zero-knowledge proofs are defined as proofs by “which verifier gains no knowledge (beyond the validity of the assertion made by the proof)” [1]. Which raises the questions — what is knowledge and what is considered “a gain in knowledge”. Funnily enough, we don’t need to answer the first question to address the second question. And cryptography is satisfied with that.
Let’s take an example and see how this is possible.
Consider a conversation between Alice and Bob about a graph that is known to both of them.
Case 1: Bob asks Alice if the graph is Eulerian (there exists a path in the graph that visits each edge exactly once and returns to the starting vertex).
Regardless of Alice’s answer, Bob gains no knowledge from the answer because he could have easily found the answer by using a linear-time decision algorithm that utilises the Euler’s theorem, i.e. a graph is Eulerian if and only if it is connected and all its vertices have even degrees[1].
Bob doesn’t learn anything new that he already couldn’t have calculated himself. Hence there is no gain of knowledge.
Case 2: Bob asks Alice if the graph is Hamiltonian (there exists a path in the graph that visits each vertex exactly once and returns to the starting vertex).
We know that there is no efficient polynomial time program for finding if a graph is Hamiltonian. So Alice’s answer signifies that Bob gains something new that he couldn’t have efficiently calculated by himself [1]. And how does Alice know the answer? We can assume she had some additional hints that are unavailable to Bob.
Bob only gains something when he receives an answer that is computationally infeasible for him.
To summarise,
- Bob has gained knowledge if his computational ability has increased, i.e. he learns something that was infeasible for him to calculate.
- Bob has gained no knowledge (zero-knowledge) if what he learns from his interactions with Alice could have been easily and feasibly calculated by himself.
You must have noticed, none of these arguments required us to actually define what the said knowledge is.
Please remember this concept.
Bob has gained no knowledge if what he learns from his interactions with Alice could have been easily and feasibly calculated by himself.
In the next part, we will turn this concept into the formal definition of a perfect zero-knowledge proof system.
Sources :
[1] Goldreich, O. (2001, January 1). Foundations of Cryptography: Basic Tools.
[2] The 9th BIU Winter School on Cryptography | BIU Cyber Center. (2018, August 5). The 9th BIU Winter School on Cryptography | BIU Cyber Center. https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/
[3] Goldwasser, S., Micali, S., & Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing — STOC ’85. https://doi.org/10.1145/22145.22178
