Cryptography Reference
In-Depth Information
in the document. That is, the prover chooses
n −
1
keys,
p
2
,...,p
n
,
to extract
y
2
,...,y
n
. Using fake decoys derived from
the document can help increase the strength of the watermark. The
more there are, the more likely that removing them will damage the
image. In some cases, the prover may actually insert them if this
makes the task easier.
When a skeptic shows up with the document, the prover can show
knowledge of
n −
1
values,
without giving the skeptic the power to repeat this
process. The decoys prevent the skeptic from ever learning which
value of
x
y
i
has a known log. Here are the steps.
p
1
,...,p
n
,
1. The prover presents the keys,
to the skeptic.
2. The skeptic recovers the values of
y
i
.
3. This loop is repeated as many times as necessary.
(a) The prover generates
b
1
,...,b
n
,thatare
used to scramble thewatermarks by computing
n
blinding factors
,
b
i
w
i
=
g
y
i
.
(b) The prover scrambles up these values of
w
i
before ship-
ping them to the skeptic.
(c) The skeptic flips a coin and makes one of two demands to
the prover:
i. Tell me all of the blinding values,
b
1
,...,b
n
. Knowing
these, the skeptic can check to make sure that there is
one legitimate value of
y
i
.
ii. Prove you know the log to one of these values. The
prover accomplishes this by revealing
w
i
for each value of
x
+
b
1
mod
(
q−
1)
.
b
1
b
1
x
=
x+b
1
This is the log of
w
1
=
g
y
1
=
g
g
g
mod q.
At each iteration, the prover must reveal one half of the solution.
The structure makes it unlikely that a skeptic will turn around and
successfully repeat the proof to someone else. It is not possible to
take the answers from one and use the information to answer the
other. Only someone who knows the value of
can do it.
There are still limitations to this algorithm. The prover must re-
veal the location of the different blocks of bits, something that leaves
them succeptible to destruction. The decoys increase the workload
of the attacker and increase the probability that removing all of the
information will substantially change the document.
One way to improve the strength of the algorithm is to mix in a
number of real marks with the decoys. That is, the prover arranges
to hide multiple values of
x
y
i
where the prover knows the value of
x
i
x
i
such that
y
i
=
g
mod q
. The prover can then use a different
