Cryptography Reference
In-Depth Information
that they are the rightful owner without revealing the technique to
others.
In theory, any zero-knowledge proof can be used as a watermark.
Every proof begins with a set of bits that identify the instance of the
problem. Imagine that
m
iterations of the encrypted graph proce-
dure described above are sufficient to prove knowledge of the graph
coloring. The proof can be embedded in a document with these
steps:
1. Create a value of
by hashing the parts of the document that
won't be modified during the embedding process. These might
be the most significant bits or some other high-pass filtering of
the document.
S
f
1
,f
2
,...f
m
.
2. Create
m
permutations of the coloring:
3. Create
m × n
keys,
p
i,j
,where
i
stands for the iteration of the
proving algorithm, (
1
≤ i ≤ m
), and
j
stands for the node,
(
1
≤ j ≤ n
).
4. Scramble the coloring of the
n
nodes for each iteration of the
f
i
(
proof by encrypting the string
S
+
i
+
j
+
v
j
)
,where
+
stands
for concatenation.
5. Embed each of the encrypted colors and the description of the
graph in the document. If necessary, the encrypted colors can
be embedded in hidden locations described by
p
i,j
.Forin-
stance, this value could be used as a seed for a cryptograph-
ically secure random number generator that chooses a string
of pixels to hide the signal.
If someone challenges the document, they can ask the informa-
tion hider to prove that they know how to color the graph hidden
away inside of it. Presumably, this problem is difficult to solve and
only the person who hid the graph would know how to color it. The
skeptic could repeat these steps
m
times. Let
i
stand for the iteration.
1. The skeptic recovers the graph.
2. The skeptic assembles
S
by examining the unchanged parts of
the document.
3. The skeptic chooses a random edge,
(
v
a
,v
b
)
.
4. The prover reveals
p
i,b
. These values can be used to
locate the encrypted colors and thendecrypt them. If they don't
match, the process continues. If they do match, the prover is
toast.
p
i,a
and
