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

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).