# 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`

- Because
- 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`

- I could have choosen a random
- 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

- if the prover generates

- If the verifier randomly picks

- first, I'll generate random integer