sgo.to

ZK Auth

Sam Goto
  • Dan Boneth's Discrete Log based Zero-Knowledge Proof
  • diffie hellman assumption: inverting discrete logarithms is hard
  • y = g ^ x mod p
  • If I give you y (and we have a pre-agreement on g and p), I'd like to prove to you that I know x without giving x to you *So, how do I prove that I know x without giving `x to you?
  • zero knowledge proof
    • first, I'll generate random integer r
    • then, I'll calculate C = g ^ r mod p
    • I'll send you, the verifier, C
    • The verifier asks for x + r?
    • I'll calculate w = x + r mod (p - 1)
    • I'll send you w
    • Using C and w (as well as g, p and y), the verifier can tell that you know `x
      • Because a ^ x * a ^ y = a ^ (x + y) and
      • a ^ x mod p = a ^ (x mod (p - 1)) mod p (Fermat's Little Theorem)
      • y * C mod p = (g ^ x mod p) * (g ^ r mod p) * mod p = g ^ x * x ^ r mod p = g ^ (x + r mod (p - 1)) mod p = g ^ w mod p
    • I'll verify that y * C mod p =? g ^ w mod p
    • But:
      • I could have choosen a random z such that
      • C = g ^ z / y mod p and when you ask for w I'll send you:
      • w = z
      • Which you'd use to calculate y * C mod p =? g ^ w mod p and I'd trick you because:
      • y * C mod p = y * (g ^ z / y) mod p = g ^ z mod p which would match
      • To check that you used a random r, the verifier would ask for it
      • Such that it could verify that C was computed such that it matches g ^ r mod p
      • But if the verifier asks for both x + r and r then it can derive x
    • The trick is for the verifier not to ask for x + r and r but to randomly ask for one of the two
      • If the verifier randomly picks r, then it can check if the prover lied by testing if C = g ^ r mod p
      • If the verifier randomly picks x + r, then it can check if you know x by checking if y * C mod p =? g ^ w mod p
      • If the prover is trying to fool the verifier, it needs to prepare and commit to y and C:
        • if the prover generates C = g ^ r mod p then it can't know how to prepare w = x + r mod (p - 1) because it doesn't know x so y * C mod p won't match g ^ w mod p
        • if the provder generates C = g ^ z / y then it can't provide r because C = g ^ r mod p won't match the C that was given before