Zero-Knowledge Prof’s 101 ENCORE – Only Highschool Math

From IIW
Jump to: navigation, search

Zero-Knowledge Prof’s 101 ENCORE – Only Highschool Math


Thursday 1F

Convener: Kazue Sako

Notes-taker(s): Christian Lundkvist


Discussion notes, key understandings, outstanding questions, observations, and, if appropriate to this discussion: action items, next steps:


Suppose we have publicly known integers g, p, where p is large(~ 2^256), g < p. (p is often a prime)

Define f(x) = g^x mod p

We use the fact that given f(x) it is computationally infeasible to compute x (“Discrete logarithm problem”)

For modular arithmetic (i.e. the “mod p“ above), see https://en.wikipedia.org/wiki/Modular_arithmetic

(All operations are modulo p here)

Alice gives y = f(x) to Bob, he holds on to y. Alice has the secret number x and wants to prove to Bob that she knows x such that y = f(x) without revealing x.

Alice can prove to Bob that she knows x through the following protocol:Alice creates random number r

Alice gives u = g^r mod p to Bob Bob sends a random number e \in {0, 1} to Alice


If e=0 Alice defines v = u

If e=1 Alice defines v = g^(r+x) mod p


Alice sends v to Bob


Bob verifies by checking:


if e=0 check that v = u

if e=1 check that v = u * y (=u * f(x) = g^r * g^x = g^(r+x))


If Alice knows x she can always give the right response v. If Alice doesn’t know x she has probability 1/2 of giving the correct value (if Bob sends e=0).


Now if we do this 10 times the probability of Alice sends the right thing without knowing x is 1/2^10 (around 1 in a million).Why is the choice e=0 relevant (it’s unrelated to x)?


Suppose Bob always gives e=1 and Alice knows this. She can then cheat by providing


u = g^r / y mod p


to Bob, and when Bob sends e=1 Alice can respond by sending v = g^r mod p. Bob will compute u * y = g^r/y * y = g^r mod p = v so Bob’s check will always succeed even though Alice didn’t know x. This is why Bob needs to also send e=0.


Generalize a bit:


Alice generates r, defines u = g^r mod p, send u to Bob

Bob sends e, Alice sends back v = g^(r + e*x) mod p Bob verifies by checking that v = u * y^e(same as above in the case e \in {0,1})


Now, instead of e \in {0, 1}, let e be a random number in the interval [0, p-1] and do the same thing:


Alice generates r, defines u = g^r mod p, send u to Bob

Bob sends e, Alice sends back v = g^(r + e*x) mod p Bob verifies by checking that v = u * y^e


Now you only have to do one step in the interactive proof, and the probability of Alice generating a successful number v without knowing x is around 1/2^256

This is still an interactive proof, can we make the proof non-interactive?


Instead of Bob randomly choosing e, we can automatically generate a “random” response value e by hashing u:


e = Hash(u)


Now Alice can create a non-interactive zk-proof v:

Randomly generate r Define u = g^r mod p define e = Hash(u) v = g^(r + e * x) mod p Bob verifies the proof by checking that: v = u * y^e

If we only do this an attacker can replay Alices proof u, so Alice could add something like a nonce value to e, i.e. use e = Hash(u || nonce) ) where || means concatenation of byte strings. This way you can protect against replay attacks.


We now see that at this point we’ve actually designed a general signature scheme, by using an arbitrary message instead of the nonce above.This signature scheme would be defined as follows:Alice has a private key x, and generates a public key y = f(x) = g^y mod p.


To sign a message M with the private key x Alice does Randomly generate r Define u = g^r mod p define e = Hash(u || M) v = g^(r + e * x) mod p


The signature is defined as the pair (u, v).

To verify the signature on M using Alice’s public key y Bob computes e = Hash(u || M) and checks that v = u * y^e.This is very close to the Schnorr signature scheme: https://en.wikipedia.org/wiki/Schnorr_signature


Also instead of using modular arithmetic directly we often use more specific group arithmetic (such as elliptic curve arithmetic in elliptic curve cryptography).