Databases Reference
In-Depth Information
interference or by data modification. The probability of it being modified due
to watermark interference is
p
n
1
,n
, and the probability of it being modified by
a data modification attack is
p
. Therefore, the probability of it being modified
in any way is
p
n
1
,n
(1
−
p
)+(1
−
p
n
1
,n
)
p
. The false miss rate in this case is
the probability of at least
ω
−
τω
embedded bits out of
ω
bits of the
n
1
-th
watermark being modified.
It can be verified that as
n
, the false hit rate approaches 100% and
the false miss rate approaches 50%. The more watermarks embedded into a
data copy, the larger the false detection rates in watermark detection, and the
more errors introduced to the underlying data in watermark insertion.
The watermarking errors should be carefully evaluated so as to preserve
data quality. The errors can be controlled at two different levels. At item
level, the errors introduced to individual values are bounded because no al-
teration is allowed beyond
ξ
least significant bits. At aggregation level, the
errors introduced to descriptive statistics of attribute values can be quanti-
fied. In particular, one can study the watermarking error introduced to the
mean of an integer-valued attribute with values
x
1
,...x
η
. After embedding
n
watermarks, value
x
i
becomes
x
i
+
e
i
(
n
), where
e
i
(
n
) is a random variable.
For value
x
i
, if its least significant bit
j
is modified in watermark insertion,
the modification will cause change +2
j
or
→∞
2
j
to
x
i
with the same probability
1
/
2. Knowing that the least significant bit
j
will be modified in watermark
insertion with a probability
p
0
,n
(due to watermark interference), one can de-
rive that the mean of
e
i
(
n
) is zero and the variance of
e
i
(
n
)is
p
0
,n
(2
2
ξ
−
−
1)
3
.Let
μ
=
i
=1
x
η
be the mean of original attribute values and let
μ
e
(
n
)=
i
=1
e
i
(
n
)
η
be the error in computing
μ
after watermarking. The expected error in com-
puting
μ
after watermarking is
E
[
μ
e
(
n
)] = 0 and the variance of the error is
V
[
μ
e
(
n
)] =
p
0
,n
(2
2
ξ
−
1)
3
η
. It can be verified that the variance of watermarking
error is monotonic increasing with
n
to approach its upper limit
2
2
ξ
−
1
6
η
.
An application of multiple watermarks is to defend against additive at-
tacks. In an additive attack, a pirate inserts additional watermarks to water-
marked data so as to confuse ownership proof. A pirate can insert watermarks
to claim ownership of the data or claim that the data were provided to a buyer
legitimately. An additive attack can be thwarted by raising the watermark-
ing error to a predetermined threshold such that any additive attack would
introduce more errors than the limit [16]. In the case of additive attack, the
ownership dispute can be resolved by comparing whose watermarks can be
detected more. To gain advantage in an ownership dispute, a pirate is forced
to embed a large enough number of watermarks. Consequently, the pirated
data is less useful or less competitive compared to the originally-watermarked
data and it is not necessary for the owner to claim ownership over such data.
Multiple watermarks can also be used for proving joint ownership in a
scenario where a database relation is jointly created by
n
participants. Each
participant can embed a watermark with his own key so that he can prove his
