L13-PALLADIUM Datasheet, PDF (3/7 Pages) List of Unclassifed Manufacturers – Palladium, Zero Knowledge

3.1 The General Set-up
3
3.1 The General Set-up
P = Prover
wants to prove he knows m
V = Verifier
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 different
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 Verifier 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 Verifier (the remote computer you are trying to convince):
For a given graph coloring, there are 6 different 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 (Verifier
doesn’t know which pile Prover picks) and puts it on the table covering up vertices with little stickies