Zero Knowledge Proofs 101

From IIW
Jump to: navigation, search

Zero Knowledge Proof 101

Wednesday 1G

Convener: Chris Blanton

Notes-taker(s): Kazue Sako


Notes also online at:

Simple one way function:

x -> f(x)

Easy to go one way to f but mathematically hard to go from f(x) to x.

The most common example is a hash function.

Known(public): g, p:prime

g is a constant p has to be prime

f(x) = g ^ x mod p

Easy to know x and compute g ^ x mod p but difficult to do in reverse.


Use case of a hash function:

register password(x)

It is not smart to store password(x) in plaintext, so we register password as f(x)

From there it is easy to compute that x = f(x).


Zero knowledge proof (ZKP)

Alice wants to prove Bob that she knows x without giving any information about x. Bob already knows f(x).

So again:

Known(public): g, p:prime g is a constant p has to be prime

random number 'r'.


Alice sends Bob u = g^r mod p

Bob receives u


Bob returns a challenge(e). Either 0 or 1

e = 0 || 1


If Alice receives 0, Alice returns v = r

Else if Alice receives 1 Alice returns v = r + x

e = 0 -> v = r

e = 1 -> v = r + x

Check that Alice knows x:

if Bob sent e = 0 before:

if u = g^v mod p:


else fail

if Bob sent e = 1 before:

and if u*f(x) = g^v mod p


else fail


Bad actor can cheat with:

u = g ^ r mod p / f(x)

To get around this, multiple rounds of this(t), where 'r' is different for every t.

g = number

p = prime

t = number of rounds/iterations

for t:

r = random number

Send Bob 'u = g^r mod p'

Bob receives u

Bob returns 0 or 1 as 'e'

If Alice receives e==0:

v = r
return v to Bob
g^v mod p = u

If Alice receives e==1:

v = r + x
return v
g^v mod p = u*f(x)

(Correct) Alice is always accepted (pass)

Chris(bad actor) with high probability, will be rejected.

By performing this protocol, information on x is not revealed.


If Alice performs correctly she will send.

v = r when e = 0

v = r + x when e = 1

Otherwise, the bad actor (Chris) will most likely send "garbage" as they won't know r.


More secure method of ZKP:

if e < 2^160


v = r + x * e


g^v mod p = u*f(x)^e


If you want this to be non interactive:

e = H(u) where H is hash

in this case:

g^v mod p = u*f(x)^H(u)

Both Alice and Bob run H(u) individually and do not pass it.


Paper recommendation given by Alan Karp:

Comparing information without leaking it