Zero Knowledge Proofs 101
Zero Knowledge Proof 101
Wednesday 1G
Convener: Chris Blanton
Notes-taker(s): Kazue Sako
Discussion notes, key understandings, outstanding questions, observations, and, if appropriate to this discussion: action items, next steps:
Notes also online at: https://github.com/afroDC/Personal/wiki/Kazui-Sako-Zero-Knowledge-Proof-101-Notes-from-IIW-26
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.
Contents
=========
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'.
Commit:
Alice sends Bob u = g^r mod p
Bob receives u
Challenge:
Bob returns a challenge(e). Either 0 or 1
e = 0 || 1
Response:
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:
pass
else fail
if Bob sent e = 1 before:
and if u*f(x) = g^v mod p
pass
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
Alice:
v = r + x * e
Bob:
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
