Cryptography Reference
In-Depth Information
Exploiting this property of matrix multiplication requires assum-
ing that the data in the file is relatively random and comes with a
mean value of zero. Sound files fit this model, but image files usually
fail because they consist of bytes that range between
0
and
255
.Any
file can be converted into one with a zero mean value by calculating
the mean and subtracting it from each entry. The result may not be
sufficiently random for this algorithm, but we will assume that it is.
Let
x
be a vector of data where the watermark will be hidden. We
assume that it comes with a zero mean and is sufficiently random.
What is sufficiently random? Perhaps it's better to define this by
describing the effect we want. Ideally, we want
h
=0
or at least
sufficiently close to zero. Then it will drop out of the computation
and only the watermark will be left.
Let
x
Mx
w
be an eigenvector of some matrix,
M
,and
λ
be the corre-
sponding eigenvalue.
. This vector can be used as a water-
mark and added to the camouflaging data,
Mw
=
λw
x
, with a weight,
β
.Ide-
ally,
β
is chosen so that
x
+
βw
is perceptually identical to
x
and the
watermark can be extracted.
The watermark is extracted from the data by computing
)
h
h
h
β
2
wMw.
(
x
+
βw
M
(
x
+
βw
)=
x
Mx
+
x
Mβw
+
βwMx
+
If the assumption about the randomness of
x
holds, the first three
β
2
λ
w
)=
β
2
λ
terms will be close to zero leaving us with
(
w
.
A public-key systemcan be established if the values of
M
,
β
,and
λ
are distributed. Anyone can test a file,
y
,forthepresenceorabsence
h
of the watermark by computing
y
My
and determining whether it
β
2
λ
.
This approach still has a number of different limitations. First,
the number of elements in
matches
must be relatively large. Eggers,
Su and Girod report results with lengths of about 10,000 and about
100,000. Larger values help guarantee the randomness that pushes
x
x
and
w
h
Mx
to zero.
Second, finding the eigenvectors of
is just as easy for the mes-
sage creator as any attacker. One solution is to choose an
M
M
which
has many different eigenvectors,
{w
1
,...,w
n
}
that all come with the
same eigenvalue
. The attacker may be able to identify all of these
eigenvectors, but removing the watermark by subtracting out the dif-
ferent values of
λ
w
i
, one after another, could be seen as a brute-force
attack.
Of course, the ease of finding the eigenvectors means that some-
one can insert a fake watermark by choosing any eigenvector,
w
i
,that
comes with an eigenvalue of
. This means that the algorithm can't
be used to generate digital signatures like many of the classic pub-
λ
