sgo.to

Zero Knowledge Proofs

Sam Goto

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.