# ZK Auth

• 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