Zero Knowledge Proofs 101

From IIW
Jump to: navigation, search

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.


=========

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


==========