Maths & Logic for Zero-knowledge Proofs (simplified) — Part 5
A primer for understanding the mathematical insights used to build ZK.
Questions to answer
1. How is zero-knowledge implemented as a protocol? (Read 1 and 2)
1. Honest Verifier Zero-Knowledge (HVZK)
In the last part we defined zero-knowledge as
“Bob (Verifier V) has gained no knowledge if what he learns from his interactions with Alice (Prover P) could have been easily and feasibly calculated by himself.”
Translating it into a formal definition means
This becomes the core idea when defining a Honest-Verifier Zero Knowledge (HVZK).
Notes:
a. HVZK focuses only on the case where the Verifier is (prescribed) honest, i.e. it does not consider cases where the verifiers are malicious. This makes it a weak notion of zero-knowledge. Further conditions need to be added to this definition to make it usable in real-life cases where we encounter malicious entities.
But one reason we are care about this weak notion is because public coin HVZK protocols can be changed into similar protocols that are zero-knowledge in general [1].
b. The verifier is a probabilistic polynomial time (PPT) algorithm.
Here is the definition of zero-knowledge as presented in the GRM’85 paper [4].
2. Developing the Notion of Zero-Knowledge
A. QR is not HVZK :
Let’s take the proof for quadratic residuosity (QR) we saw in part 2. We know for sure that the presented proof was NOT zero-knowledge. Looking back at the example, let’s see why that proof can’t be considered zero-knowledge.
We can see that, because the simulator is only probabilistic polynomial time, it is not always able to give the same results as the actual interaction between P and V, where P is super-polynomial. This means the probability distribution of both are not same → not zero-knowledge.
B. Design an Interactive Proof for QR:
Now let’s design an Interactive Proof for QR.
To prove the statement “x is a quadratic residue of (mod N)”, the prover P claims he knows a value w such that x = w² mod N. Verifier V verifies this claim by exchanging messages with P and checking the result.
C. Verify the protocol is HZVK:
Now, we will take the above protocol and see how it fares on the 3 criteria of completeness, soundness and zero-knowledge.
- Completeness : Completeness means that if x is a residue & both P and V honestly follow the interactive protocol, V will always ACCEPT the proof (i.e. ACCEPT with probability 1). Let’s see both cases (b=0 and b=1) where x is a residue.
b = 0 → z² == y (y = u² and perfect square are always residue) → ACCEPT
b = 1 → z² == xy (xy = x*u² => residue*residue = residue) → ACCEPTSince verifier ACCEPTS in both the cases (where x is residue), then the probability of accepting is 1.
- Soundness : Soundness means that if x is not a quadratic residue, then regardless of what P does, V will REJECT the proof with probability at least 1/2. Here, “regardless of what P does” means this protocol also considers malicious provers P*, beside the honest ones. Since P* is malicious, we can’t trust that the value of y (Message 1) sent by them is actually y = u² and that y is a residue (perfect square). This gives rise to four cases where x is a non-residue.
--------------------------------------------------------------------------
GIVEN: x is a non-residue.
--------------------------------------------------------------------------
——————————————
Given:
b=0
y is residue
Proof:
z² = y
Since y is given as residue, there must exist such u that y = u² and z = u
Verification: ACCEPT
——————————————
Given:
b=1
y is non-residue
Proof:
z²/u² = xy/y = x
==> (z/u)² = x
x should be a residue but it is given as non-residue (contradiction)
Verification: REJECT
———————————————
Given:
b=0
y is non-residue
Proof:
If we consider y as residue, then theremust exist such u that y = u² and z = u.
But since we know that y is non-residue, no such u can exist. (contradiction)
Verification: REJECT
——————————————
Given:
b=1
y is residue
Proof:
z²/u² = xy/y = x
==> (z/u)² = x
If x is a perfect square, it must be a resiude.
But we are already given that x is a non-residue. (contradiction)
Verification: REJECTOut of the 4 cases (where x is non-residue), verifier rejects in 3 cases. This means the probability of verifier rejecting is atleast 1/2.
- Zero-Knowledge : To prove that a proof does not leak knowledge (aka zero-knowledge), we need to think like a malicious verifier V*.
But instead of showing the interaction between P and V*, we will use a simulator because (as we know from Part 4), zero-knowledge is defined as anything that V* can learn from the interaction with P, he can learn it himself by using a simulator S(x). If the results from the simulator are the same as from the interactions, then this interaction is guaranteed to be zero-knowledge.
We can make 2 claims about the simulator V* uses.
Claim 1: In both cases (b=0 and b=1), if x is a residue, the value of y is also a random residue [3].
Proof: Here is the value of y in both cases.
b = 0 → y = z²/x⁰ = z² (y is perfect square, hence a residue)
b = 1 → y = z²/x¹ = z²/x (z² is a perfect square, hence a residue. x is given
as residue. residue/residue = residue)This implies that y is independent of b (regardless the value of b, the probability distribution of the values of y is the same) → This means that using this y as input for V*(y), the result will also be independent of b → This means that value of b will be equal to V*(y) only 1/2 of the time, i.e. Pr[b = V*(y)] = 1/2. → Which further means that the above simulation will halt after k steps with very high (1 − 2^(−k)) probability (Refer to Part 4).
Claim 2: The output of the simulator is distributed identically to the view of V∗ in an interaction with the honest prover [3]. This means the protocol is zero-knowledge.
Proof: Assuming that we can’t trust the value of y provided by P*, we can’t be sure if there exists z such that y = z² . But if we can prove that such z exists, then the y sent by P would be considered valid and a residue.
We already saw that y is a residue in both cases (Claim 1). Now, let’s take the case where b == V*(y) and y is residue and see if we can derive z in case of Prover and simulator.
-------------------------------------------------------------------
GIVEN:
b == V*(y) , which happens only 1/2 of the times
y is residue
-------------------------------------------------------------------
b = 0
Prover: If y is a residue, then such z must exist that y = z²
Simulator: z is a random number selected by V*
---------------
b = 1
Prover: z exists and is a root of xy
Simulator: z is a random number selected by V*
Therefore, for both the prover and simulator, the values of z, b and y are available, implying that the probability distribution of the prover and simulator are same → interaction is zero-knowledge.
Thus, begins our exploration of zero-knowledge.
In the next part, we will dig deeper into what “same” really means for the probability distribution of a prover and simulator.
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] Barak, B. (2007). Lecture 15 — Zero Knowledge Proofs. https://www.cs.princeton.edu/courses/archive/fall07/cos433/lec15.pdf
[4] 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
