Zero Knowledge Proofs (2024)

This is an interactive explanation of the protocol described here.

Alice wants to prove that it knows x = such that g ^ x mod p = y without revealing to Bob the value of x, having agreed ahead of time on a large prime number p = , a primitive root g = and an integer y = .

The way they accomplish that is by:

1. Alice generates a random number r = and commits to it by computing C = g ^ r mod p = ^ mod = = C and sending it to Bob.
2. Bob asks for w = (x + r) mod (p - 1) with the same r that was committed to C
3. Alice computes w = (x + r) mod (p - 1) = ( + ) mod ( - 1)= = w and sends it to Bob.
4. Bob knows that:
   1. a ^ x * a ^ y = a ^ (x + y) (arithmetic),
   2. a ^ x mod p = a ^ (x mod (p - 1)) mod p (fermat's little theorem)
   3. y = g ^ x mod p (definition)
5. So y * C mod p = g ^ x * g ^ r mod p = g ^ (x + r) mod p = g ^ ((x + r) mod (p - 1)) = g ^ w mod p.
6. Bob computes
   1. y * C mod p = * mod = and
   2. g ^ w mod p = ^ mod =
   3. And if these numbers match, Bob knows that Alice knows x unless Alice wasn't cheating.
7. Bob is suspicious that if Alice picks a specific r = z = and responded with
   1. C = g ^ (z / y) mod p = ^ ( / ) mod = = C and
   2. w = z = = w, then
   3. Then Bob would compute = y * C mod p = y * g ^ (z / y) mod p = g ^ z mod p = without Alice knowing what x is.
8. Bob also knows that:
   1. To prove that Alice chose a random r, Bob would have to ask for it, so that it can check if g ^ r mod p = C matches what he got.
   2. But, if Bob asks for both (x + r) mod (p - 1) and r, then that reveals to Bob what x is.
9. So, Bob asks Alice repeatedly until it is confident that Alice isn't cheating
   1. Commit and send me a C and
   2. I'll ask you one of the following requests after you commit to a C:
      1. Send me r (without revealing me x) so that I can check if you didn't cheat at constructing C = g ^ (z / y) mod p but rather used g ^ r mod p = C that I got.
      2. Send me w (without revealing me r), so that I can check if y * C mod p = g ^ w mod p with the C that I got.
10. Every time Bob repeats this process, he gets exponentially confident that Alice (a) isn't cheating and (b) knows the value of x.