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

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:

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

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

###### =========

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 returns 0 or 1 as 'e'

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

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