Databases Reference
In-Depth Information
maximum or local minimum value satisfying the criteria that at least one of its
δ
-neighboring values can be found in any uniform random sampling of degree
χ
(i.e., randomly selecting one value out of every
χ
values) of the sequence, where
the
δ
-neighboring values are defined to be a subset of stream items forming
a complete “chunk”, being immediately adjacent to the extreme value, and
having a Euclid distance to the extreme value smaller than
δ
. The intuition
of using extreme values as watermark bit-carriers is that the extreme values
are likely to be largely preserved in value-preserving attacks or transforms as
they reflect the fluctuating behavior of the data stream.
Each
δ
-neighboring value is partitioned into two parts: most significant
part and least significant part, where the most significant part is used to
determine whether, where, and how to embed a watermark bit, and the least
significant part may be used to embed a watermark bit. It is assumed that all
δ
-neighboring values of an extreme value share the same most significant part.
It is also assumed that it is tolerable to modify the least significant part but
not the most significant part in both watermark insertion and value-preserving
attacks.
The watermark insertion can be interpreted using a cryptographically se-
cure pseudo-random sequence generator
S
as follows. For each extreme value,
seed
with the significant part of the extreme value in concatenation with a
secret key. If
S
S
1
mod
γ
= 0, this extreme value is selected; otherwise it is ig-
nored (roughly 1
/γ
of extreme values are selected). For each selected extreme
value, watermark bit
wm
[
i
] is selected, where
i
=
S
2
mod the length of the
watermark. Then, bit position
j
is selected, where
j
=
S
3
mod the length
of least significant part of the extreme value. Finally, for each
δ
-neighboring
value including the extreme value, the bit position
j
is set to
wm
[
i
] and the
adjacent bits are set to zero (to prevent “overflow” in computing average of
some
δ
-neighboring values). Since the entire set of
δ
-neighboring values are
modified, any random sampling of degree
χ
will include some watermarked
values. Also, the average of any combination of some
δ
-neighboring values
would preserve the embedded bit. In watermark detection, a majority vote is
used for recovering each watermark bit
wm
[
i
], as in Agrawal and Kiernan's
scheme. The analysis on false detection rates can be done similarly as for Li,
Swarup, and Jajodia's multi-bit watermarking scheme.
It has been shown that this scheme can be further improved to be resilient
to various transform attacks including sampling, averaging, random alteration,
and some combined transforms [23].
A Fragile Watermarking Scheme
Guo, Li, and Jajodia [7] proposed a fragile watermarking scheme for detecting
malicious modifications to streaming data. The scheme partitions a numerical
data stream into groups based on synchronization points. A data element
x
i
is defined to be a synchronization point if its keyed hash
HMAC
(
K
,x
i
)
mod
m
= 0, where
K
is a secret key, and
m
is a secret parameter. When a
