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

`Alice`

generates a random number`r`

= and commits to it by computing`C`

=`g ^ r mod p`

=`^`

`mod`

`=`

`=`

`C`

and sending it to`Bob`

.`Bob`

asks for`w`

=`(x + r) mod (p - 1)`

with the same`r`

that was committed to`C`

`Alice`

computes`w`

=`(x + r) mod (p - 1)`

= (`+`

`) mod (`

`- 1)=`

`=`

`w`

and sends it to`Bob`

.`Bob`

knows that:`a ^ x * a ^ y = a ^ (x + y)`

(arithmetic),`a ^ x mod p = a ^ (x mod (p - 1)) mod p`

(fermat's little theorem)`y = g ^ x mod p`

(definition)

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

. `Bob`

computes`y * C mod p`

=`*`

`mod`

`=`

`and`

`g ^ w mod p`

=`^`

`mod`

`=`

- And if these numbers match,
`Bob`

knows that`Alice`

knows`x`

unless`Alice`

wasn't cheating.

`Bob`

is suspicious that if Alice picks a specific`r`

=`z`

= and responded with`C`

=`g ^ (z / y) mod p`

=`^ (`

`/`

`) mod`

`=`

`=`

`C`

and`w`

=`z`

=`=`

`w`

, then- Then
`Bob`

would compute`=`

`y * C mod p`

=`y * g ^ (z / y) mod p`

=`g ^ z mod p`

=`without`

`Alice`

knowing what`x`

is.

`Bob`

also knows that:- 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. - But, if
`Bob`

asks for both`(x + r) mod (p - 1)`

and`r`

, then that reveals to`Bob`

what`x`

is.

- To prove that
- So,
`Bob`

asks`Alice`

repeatedly until it is confident that`Alice`

isn't cheating- Commit and send me a
`C`

and - I'll ask you one of the following requests after you commit to a
`C`

:- 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. - 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.

- Send me

- Commit and send me a
- Every time
`Bob`

repeats this process, he gets exponentially confident that`Alice`

(a) isn't cheating and (b) knows the value of`x`

.