Cryptography Reference
In-Depth Information
Figure 12.2: A graph colored so that no two adjacent nodes have the
same color. Information can be encoded in this solution by forcing
certain nodes to certain colors.
that also encodes the information. Figure 12.2 shows a graph colored
so that several nodes take fixed colors. One way to encode the infor-
mation is to grab pairs of nodes and force them to have either the
same or different colors. Two nodes can be forced to have the same
color by merging them while the algorithm looks for a solution. Two
nodes can be kept different by adding an edge that connects them.
Other problems usually have some latitude.
The process can be strengthened by hashing steps along the way.
Let
K
0
be a creator's original watermarking information. It might be
their name, it might be an email address, or it could be a reference
to some big table of known creators. Let
H
be a strong hash function
be a set of constraints to the prob-
lem that are open for twiddling to hold information. These may be
extra variables in a boolean satisfiability problem that can be set to
true or false. Or they could be nodes in a graph that might hold dif-
ferent values. For the sake of simplicity, assume that each constraint
can encode one bit. The following loop will encode the watermark:
likeMD5orSHA.Let
{C
1
,...,C
n
}
1. Let
K
i−1
,C
i−1
)
. The hashing function should be fed
both the information encoded in
K
i
=
H
(
C
i−1
and some data about
the structure of
C
i−1
itself. This data might include the node
numbers, the variable names, or the boolean formulae. (Set
C
0
