3.1 The General Set-up

3.1 The General Set-up

3

P = Prover

wants to prove he knows m

V = Veriﬁer

wants to learn if P knows m

−−−−−−−−−w−=−w−it−ne−s−s −−−−−−→

←−−−x−=−r−a−nd−o−m−−ch−a−ll−en−g−e−−−−

−−−−−−−−y−=−r−es−p−on−s−e−−−−−−→

test (c, w, x, y).

Accept if OK, reject otherwise.

We want the protocol to satisfy the following properties:

1. If P does know m, then V always accepts. (Completeness)

2. If P does not know m, then P is unlikely to convince V . (Soundness)

Soundness may be shown by demonstrating that if P is prepared to respond to several diﬀerent

challenges (for the same witness), then in fact P must know (or must be able to easily compute) m.

We would also like to have that the protocol be zero-knowledge: the Veriﬁer learns nothing (zero),

aside from the fact that P knows m.

3.2 3-Colorability Example

We have an undirected graph with 5 vertices. Can we color the vertices with three colors so that no

two adjacent vertices have the same color?

A given graph may have many possible colorings, only one coloring, or no colorings at all. Suppose

I have a graph with a million vertices and I tell you I know how to color it using 3 colors. I want to

convince you that the graph is 3-colorable without telling you what the coloring is. Is there some

way I can convince a remote computer, the skeptic, that I know how to do the coloring without

saying what the coloring is?

Consider the following exchange between the Prover (you, the person who knows the 3-coloring) and

the Veriﬁer (the remote computer you are trying to convince):

For a given graph coloring, there are 6 diﬀerent permutations of the coloring possible: RGB, RBG,

BRG, BGR, GBR, GRB. That is, you take one coloring and just permute the color assignments

(e.g. from RGB to RBG, all vertices that are R are still R, all vertices that are G are now B, etc.).

Again, this is just for one coloring that the Prover picks. We can represent each permutation as a

sheet of paper with the graph and coloring on it (see Figure 4 below).

[Figure 4: Representation of the 6 permutations of a given graph 3-coloring]

Do t times: Prover: picks a sheet (graph with a coloring permutation) from a random pile (Veriﬁer

doesn’t know which pile Prover picks) and puts it on the table covering up vertices with little stickies