Cryptography Reference
In-Depth Information
Figure 12.3: A graph where the nodes are assigned one of four colors.
edges.
is the coloring function. Figure 12.3 shows one graph that is
4-colored.
Finding a
f
coloring of an arbitrary graph can be a complicated
and difficult process in some cases. The problem is known to be
NP-complete, [GJ79] which means that some instances seem to grow
exponentially more difficult as more nodes and edges are added. In
practice, a coloring for many graphs can be found relatively quickly.
It's often harder to find difficult graphs and this is one of the practical
limitations of using zero knowledge proofs in applications. There are
a number of details that make it difficult to produce a working and
secure implementation of this idea.
Let's say you know a coloring of some graph and you want to
provethatyouknowitwithoutactuallyrevealingittoanotherper-
son, the skeptical inquirer. Here's an easy way to prove it:
k−
f
.Thatis,swap
1. Create a random permutation of the coloring,
f
(
f
(
the various colors in a random way so that
v
i
)
=
v
j
)
for all
(
v
i
,v
j
)
in the graph.
S
might be established from an unimpeachable source by hash-
ing an uncorruptible document. If the zero knowledge proof is
going to be embedded in a document, this hash might be of the
parts of the document that will not be changed by the embed-
ding.
S
2. The skeptical inquirer can give you a random bit string,
.Or
3. Create
n
random keys,
p
1
...p
n
and use an encryption function
f
(
to scramble the string
S
+
i
+
v
i
)
for each node in the graph
