This is a note of the blog Zero Knowledge Proofs: An illustrated primer part1 and Part2. Zero-knowledge proofs are one of the most powerful tools cryptographers have ever devised.

1 Origins of Zero Knowledge

MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff proposed the notion of zero knowledge in 1985 when they worked on interactive proof systems. Prior to them, most work in this area focused on the soundness of the proof system: the case where a malicious Prover attempts to ‘trick’ an honest Verifier into believing a false statement. What happens if you don’t trust the Verifier?

A zero knowledge proof is defined as an interaction between two computer programs (or Turing machines) — respectively called a Prover and a Verifier — where the Prover works to convince the Verifier that some mathematical statement is true.

2 What makes a proof zero knowledge?

Three properties of a ZKP:

  • completeness: if a prover tells a truth, it will eventually convince a verifier, at least with high probability.
  • soundness: a prover can only convince a verifier if he is actually tell the truth.
  • zero-knowledge: the verifier learns nothing beyond the fact that the statement is true.

3 A thought experiement for zero-knowledge

If the prover has no knowledge and he can still convince a verifier, for example by a time machine, and the two protocol transcripts have the same statistical distribution. Then the verifier cannot tell the difference between the real experiment and the time machine experiment. And this implies that the protocol must not leak any useful information. The protocol is zero-kmnowledge protocol.

4 Commitment Scheme

A commitment scheme allows one party to ‘commit’ to a given message while keeping it secret, and then later ‘open’ the resulting commitment to reveal what’s inside. They can be built out of various ingredients, including (strong) cryptographic hash functions.

A simple example of a commitment can be built using a hash function. To commit to the value “x” simply generate some (suitably long) string of random numbers, which we’ll call ‘salt’, and output the commitment C = Hash(salt || x). To open the commitment, you simply reveal ‘x’ and ‘salt’. Anyone can check that the original commitment is valid by recomputing the hash. This is secure under some (moderately strong) assumptions about the function itself. A prover can control what to reveal.

If there exists any Verifier computer program that successfully extracts information by interactively running this protocol with some Prover, then we can simply use the rewinding trick on that program to commit to a random solution, then ‘trick’ the Verifier by rewinding its execution whenever we can’t answer its challenge correctly. The same logic holds as we gave above: if such a Verifier succeeds in extracting information after running the real protocol, then it should be able to extract the same amount of information from the simulated, rewinding-based protocol. But since there’s no information going into the simulated protocol, there’s no information to extract. Thus the information the Verifier can extract must always be zero.

5 What does this all mean?

A protocol can be proven zero knowledge if for every possible Verifier, you can demonstrate the existence of an algorithm called a ‘Simulator’, and show that this algorithm has some very special properties.

  • Simulator gets no special knowledge at all.
  • The transcript of the interaction with a simulator is distributed identically to a real protocol run with a normal Prover, i.e., the Verifier can’t do better against the real prover than it can do against the Simulator.

The 2nd property means that the Simulator (or Simulators) must be able to ‘fool’ every Verifier into believing that the statement is true, while producing a transcript that’s statistically identical to (or indistinguishable from) the output of a real Prover.

To build our simulator, we’re allowed to do things to the Verifier that would never happen in the real world. For exmaple, using a time machine.

Since it’s trivial for anyone to ‘fake’ a protocol transcript, even after a prover proves to me that they have a solution, I can’t re-play a recording of the protocol transcript to prove anything to anyone else (say, a judge). That’s because the judge would have no guarantee that the video was recorded honestly, and that I didn’t simply edit in the same way one might have done using the time machine.

This means that protocol transcripts themselves contain no information. The protocol is only meaningful if I myself participated, and I can be sure that it happened in real time – the real time guarantees the soundness of the protocol.

6 Efficient Proofs for all of NP

It is proved that the 3-coloring problem has an efficent proof. Because all NP-complete problems can be translated into the 3-coloring problem, there are efficient (polynomial) interactive zero knowledge proofs for a vast class of useful statements.

The general theoretic approach is as follows:

  • represent an input problem as a boolean circuit where the cuiruit is satisfied iff the cuorrect answer is known.
  • translate the circuite into a graph.
  • run the grpah ZK protocol.

In practice, we don’t follow the above approach because it is too complex. There are some efficient ZKP for practical problems.

7 Proof vs. Proof of Knowledge

There are two kinds of statement you might want to prove in zero knowledge:

  • Statements about “facts”. For example, I might wish to prove that “a specific graph has a three coloring” or “some number N is in the set of composite numbers“. Each of these is a statement about some intrinsic property of the universe.
  • Statements about my personal knowledge. Alternatively, I might wish to prove that I know some piece information. Examples of this kind of statement include: “I know a three coloring for this graph”, or “I know the factorization of N”. These go beyond merely proving that a fact is true, and actually rely on what the Prover knows.

It’s important to recognize that there’s a big difference between these two kinds of statements! For example, it may be possible to prove that a number N is composite even if you don’t know the full factorization. So merely proving the first statement is not equivalent to proving the second one.

The second class of proof is known as a “proof of knowledge”. It turns out to be extremely useful for proving a variety of statements that we use in real life.

8 The Schnorr identification protocol

Let’s imagine that Alice has published her public key to the world, and later on wants to prove that she knows the secret key corresponding to that public key – this is Shnorr’s identification problem.

The protocol is as follows:

  • p is a prime number, g is a public number called the generator of a cyclic group of prime-order q.
  • Alice picks a random number a as her private key in range [1, q].
  • Alice wants to prove that she know prviate key a for public key p, where p = g ^ a mod p.
  • Alice picks a random number k in range [1, q] , sends h such that h = g ^ k mod p
  • Bob picks and sends a random c to Alice
  • Alice sends back s = ac + k mod q.
  • Boc checks g^s = p ^ c * h mode p.

The protocol is complete because of the the finite field calcuation properties.

9 Proving soundness

The soundness means “If Alice successfully convinces Bob, then she must know the secret key a.”

When it comes to demonstrating the soundness of a proof of knowledge, we have a really nice formal approach. Just as with the Simulator we discussed above, we need to demonstrate the existence of a special algorithm. This algorithm is called a knowledge extractor, and it does exactly what it claims to. A knowledge extractor (or just ‘Extractor’ for short) is a special type of Verifier that interacts with a Prover, and — if the Prover succeeds in completing the proof — the Extractor should be able to extract the Prover’s original secret. To prove soundness for a proof of knowledge, we must show that an Extractor exists for every possible Prover.

The Extractor is not required to exist during a normal run of the protocol. We simply show that it exists if we’re allowed to take special liberties with the Prover — in this case, we’ll use ‘rewinding’ to wind back the Prover’s execution and allow us to extract secrets.

The extractor works as follows:

  • Alice picks a random number k in range [1, q] , sends h such that h = g ^ k mod p
  • Extract picks and sends a random c1 to Alice
  • Alice sends back s1 = ac1 + k mod q.
  • Extractor rewinds Alice to step 2
  • Extract picks and sends a random c2 to Alice
  • Alice sends back s2 = ac2 + k mod q.

Here the extractor tricks Alice into making two different proof transacript using the same k. Then the extractor can find a by doing the following culculation s1 - s2 = (ac1 - ac2) mod q = a (c1 - c2) mod q.

Ergo, the extractor proves the soundness of the protocol.

10 Proving zero-knowledge against an honest Verifier

To prove zero-knowledge property, normally we require a Simulator that can interact with any possible Verifier and produce a ‘simulated’ transcript of the proof, even if the Simulator doesn’t know the secret it’s proving it knows.

The standard Schnorr protocol does not have such a Simulator. Instead, to make the proof work we need to make a special assumption. Specifically, the Verifier needs to be ‘honest’. That is, we need to make the special assumption that it will run its part of the protocol correctly — namely, that it will pick its challenge “c” using only its random number generator, and will not choose this value based on any input we provide it. As long as it does this, we can construct a Simulator.

Let’s say we are trying to prove knowledge of a secret a for some public key g^a mod p— but we don’t actually know the value a. Our Simulator assumes that the Verifier will choose some value c as its challenge, and moreover, it knows that the honest Verifier will choose the value c only based on its random number generator — and not based on any inputs the Prover has provided.

  • First, output some initial g^k1 as the Prover’s first message, and find out what challenge c the Verifier chooses.
  • Rewind the Verifier, and pick a random integer z in the range [0, q - 1].
  • Compute g^k2 = g^z * g^(-ac) (where p = g^a, no need to know a) and output h = g^k2 as the Prover’s new initial message.
  • When the Verifier challenges on c again, output z.
  • The Verifier checks g^z = p ^ c * h = g^ac * g^z * g ^(-ac) = g ^ z

What this proves is that if we can rewind a Verifier, then (just as in the first post in this series) we can always trick the Verifier into believing we have knowledge of a value, even when we don’t.

11 From interactive to non-interactive

A non-interactive zero knowledge proof (NIZK) was developed by Fiat and Shamir in the 1980s. What they observed was that if you have a decent hash function lying around, you can convert an interactive protocol into a non-interactive one by simply using the hash function to pick the challenge.

Specifically, the revised protocol for proving knowledge of a with respect to a public key g^a looks like this:

  • The Prover picks g^k (just as in the interactive protocol).
  • Now, the prover computes the challenge as c = H(g^k || M) where H() is a hash function, and M is an (optional) and arbitary message string.
  • Compute ac + k mod q (just as in the interactive protocol)

The upshot here is that the hash function is picking the challenge c without any interaction with the Verifier.

It isn’t just a proof of knowledge, it’s also a signature scheme – it is the basis of EdDSA.