2
$\begingroup$

I asked this earlier on how to explain a Zero Knowledge Proof to a layman. but I'm looking for a mathematical analogy that might "enhance" the superpower explanation.

In that linked superpower, that is simply a Sum() and a compare to a previous value.

Is there an alternative, math-focused analogy that would get the idea across what a ZKP is? (opposed to a hash, or a public private key)

My goal is to get people curious about math and to dive deeper into the subject, without being confused or overwhelmed by lack of knowledge beyond Algebra.

$\endgroup$
2
$\begingroup$

Understanding Zero Knowledge Proofs with simple math:

x -> f(x)

Simple one way function. Easy to go one way from x to f(x) but mathematically hard to go from f(x) to x.

The most common example is a hash function. Wired: What is Password Hashing? provides an accessible introduction to why hash functions are important to cryptographic applications today.

f(x) = g ^ x mod p

Known(public): g, p * g is a constant * p has to be prime

Easy to know x and compute g ^ x mod p but difficult to do in reverse.

Interactive Proof

Alice wants to prove Bob that she knows x without giving any information about x. Bob already knows f(x). Alice can make f(x) public and then prove that she knows x through an interactive exchange with anyone on the Internet, in this case, Bob.

  1. Alice publishes f(x): g^x mod p
  2. Alice picks random number r
  3. Alice sends Bob u = g^r mod p
  4. Now Bob has artifact based on that random number, but can't actually calculate the random number
  5. Bob returns a challenge e. Either 0 or 1
  6. Alice responds with v: If 0, v = r If 1, v = r + x
  7. Bob can now calculate: If e == 0: Bob has the random number r, as well as the publicly known variables and can check if u == g^v mod p If e == 1: u*f(x) = g^v (mod p)

I believe step 6 is true based on Congruence of Powers, though I'm not sure that I've transcribed e==1 case accurately with my limited ascii representation.

If r is true random, equally distributed between zero and (p-1), this does not leak any information about x, which is pretty neat, yet not sufficient.

In order to ensure that Alice cannot be impersonated, multiple iterations are required along with the use of large numbers.


In this answer, I've reproduced key proof points from my blog post based on Chris Blanton's IIW presentation (session notes). Since I found this question while seeking to understand this topic, I thought I would post here too. Would love feedback on whether this makes sense, and, of course, correctness of my explanation!

$\endgroup$
  • $\begingroup$ Thank you for this breakdown. Curious, for point 7 can the validation be rewritten as u=f(v) and u*f(x) = f(v) for e == 0 and 1 respectively? If so, I'm writing a simple program to demonstrate this, but my case always fails when e == 1. $\endgroup$ – Tomislav Markovski Apr 25 '18 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.