zero knowledge

A zero-knowledge proof allows a prover to demonstrate that it possesses certain information, without revealing that information to the verifier.

Formally, the prover $P$ must convince a verifier $V$ that some object $x$ is in a set (formal language) $\mathcal{L}$. The prover possesses information, a witness $w$, that demonstrates this. For example, $x$ may be a graph which the prover wants to demonstrate belongs to the set $\mathcal{L}$ of three-colorable graphs. To do this it would serve to exhibit a three-coloring of $x$: this is the witness $w$. A zero-knowledge proof scheme allows the prover to demonstrate their claim without revealing $w$.

We model the prover and verifier $P$ and $V$ as probabilistic polynomial-time algorithms that send a sequence of messages back and forth, ending with the verifier outputting either ACCEPT or REJECT.

Such a scheme is required to have three properties:

1. Completeness: if $x\in\mathcal{L}$ and $w$ is the correct witness, then $V$ outputs ACCEPT.
2. Soundness: if $x \not\in \mathcal{L}$, then a 'dishonest' prover (any probabilistic polynomial-time algorithm $\hat{P}$) will convince the verifier to ACCEPT only with some probability that goes to zero at a faster-than-polynomial rate (i.e., a negligible function of the interaction length).
3. Zero-knowledge: the verifier doesn't learn anything except that $x \in \mathcal{L}$. Formally, there must exist some probabilistic polynomial time algorithm $S$, the 'simulator', such that for any $x\in \mathcal{L}$, the simulator can generate a trace $\tau'$ whose distribution is polynomial-time indistinguishable from that of a real prover-verifier interaction trace $\tau$.

Note that the simulator doesn't have access to the witness $w$ (and being a poly-time algorithm, doesn't have the computational capability to discover it), so its traces cannot leak any information about $w$. If these traces are indistinguishable from those of real interactions, then the real traces can't leak anything either. But since the interaction was supposed to prove access to $w$, how is it possible to produce an indistinguishable trace without access to $w$? The key is that it's the interaction itself that is convincing, not the trace that it produces. The verifier knows that it is producing its challenges honestly, not colluding with the prover, but a third party viewing the trace will not know this. Because the simulator controls both sides of the trace, the simulated 'verifier' can generate 'random' challenges that always happen to correspond to what the simulated 'prover' is prepared to answer; equivalently, the prover can anticipate the verifier's challenges and prepare accordingly.

Given the crucial role of interaction in classic zero-knowledge proofs, it is somewhat surprising that non-interactive zero-knowledge proofs (zk-SNARKs) are possible, but they are, and this also turns out to be practically very impactful.

Zero-knowledge proofs for NP

We can show that all languages in NP admit zero-knowledge proofs by demonstrating a proof scheme for a particular NP-Complete problem: three-colorability of a graph.

Let $w$ be a three-coloring of a graph $x$; note that by permuting the colors one can actually generate six equivalent such colorings $w_1, \ldots, w_6$. A single round of the protocol works as follows:

1. The prover secretly chooses one of the permutations $w_1, \ldots, w_6$ at random, and uses a commitment scheme to commit to the color of each vertex in the graph without revealing these colors to the verifier.
2. The verifier chooses a pair of adjacent vertices at random, and challenges the prover to reveal the colors of just those vertices.
3. The prover reveals that the adjacent vertices have different colors.

It is easy to see that this scheme is complete: if the prover really does possess a three-coloring of the graph, they can go for as many rounds as the verifier requires. To see that the scheme is sound, consider a dishonest prover without access to a three-coloring: then the coloring it commits to has at least one edge pair with identical colors, so the chance that it 'gets lucky' and fools the verifier at each step is at most $(|E| - 1)/|E|$. The probability of fooling the verifier over $n$ independent rounds thus goes to zero exponentially quickly.

The fact that the proof is zero-knowledge follows from the hiding property of the commitment scheme --- so the verifier learns nothing other than the colors of the edge it asks about --- and from the random permutation of colors at each step, which prevents the verifier from building up a larger picture across multiple steps.

References

• https://en.wikipedia.org/wiki/Zero-knowledge_proof#Variants_of_zero-knowledge
• https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture21.pdf