Understanding Zero Knowledge Proofs with simple math:
x -> f(x)
Simple one way function. Easy to go one way from
f(x) but mathematically hard to go from
The most common example is a hash function. Wired: What is Password Hashing? provides an accessible introduction to why hash functions are important to cryptographic applications today.
f(x) = g ^ x mod p
g is a constant
p has to be prime
Easy to know
x and compute
g ^ x mod p but difficult to do in reverse.
Alice wants to prove Bob that she knows
x without giving any information about
x. Bob already knows
f(x). Alice can make
f(x) public and then prove that she knows
x through an interactive exchange with anyone on the Internet, in this case, Bob.
- Alice publishes f(x):
g^x mod p
- Alice picks random number
- Alice sends Bob
u = g^r mod p
- Now Bob has artifact based on that random number, but can't actually calculate the random number
- Bob returns a challenge
e. Either 0 or 1
- Alice responds with
v = r
v = r + x
- Bob can now calculate:
If e == 0: Bob has the random number
r, as well as the publicly known variables and can check if
u == g^v mod p
If e == 1:
u*f(x) = g^v (mod p)
I believe step 6 is true based on Congruence of Powers, though I'm not sure that I've transcribed e==1 case accurately with my limited ascii representation.
r is true random, equally distributed between zero and
(p-1), this does not leak any information about
x, which is pretty neat, yet not sufficient.
In order to ensure that Alice cannot be impersonated, multiple iterations are required along with the use of large numbers.
In this answer, I've reproduced key proof points from my blog post based on Chris Blanton's IIW presentation (session notes). Since I found this question while seeking to understand this topic, I thought I would post here too. Would love feedback on whether this makes sense, and, of course, correctness of my explanation!