Databases Reference
In-Depth Information
can formulate a coalition),
=0
.
01 and
N
= 1000, the length of the col-
lusion resistant codeword is 51
,
695; when
c
= 2 increases to
c
=3and4,
the length increases to 317
,
185 and 1
,
098
,
622, respectively. Such long fin-
gerprints are only suitable for very large databases such as terabyte scientific
databases, surveillance databases, and anti-terror databases [17]. Nonetheless,
the database fingerprinting scheme mitigates the damage of collusion attacks
by embedding multiple copies of each fingerprint bit and recovering it with a
majority vote. As a result, the probability of detecting a traitor in collusion
attacks does not drop dramatically even as the coalition size goes beyond
c
.
A high detection rate can be obtained by either increasing
c
or decreasing
as shown experimentally in [17].
5.3 From One Watermark to Multiple Watermarks
A major concern in database watermarking is that a pirate may simply
add additional watermarks to watermarked data so as to confuse watermark
detection (i.e., additive attack). Defending against this type of additive attacks
demands an in-depth analysis of multiple watermarks.
When a group of people jointly create a database, the participants may
embed their own watermarks separately into the database, and thus can verify
their ownership independently. Such an application also requires basic research
on multiple watermarks.
We consider to extend Agrawal and Kiernan's watermarking scheme to
allow for multiple watermarks. Assume that
n
watermarks
W
n
are
embedded into database relation
R
sequentially with different secret keys
K
1
,...,
W
1
,...
K
n
but with the same parameters
γ,ν
and
ξ
. Interference exists among
multiple watermarks, as an embedded bit of one watermark could be flipped
back and forth by some later embedded watermarks. The interference among
multiple watermarks can be quantified as follows. Let
p
c
=
1
γνξ
be the proba-
bility that a least significant bit is used in embedding a single watermark. For
any mark bit of watermark
W
n
1
, the probability that this mark bit is modi-
fied by other watermarks is
p
n
1
,n
=
p
c
)
n−n
1
]
<
0
.
5. For any least
significant bit of the original data, the probability that this bit is modified by
all watermarks is
p
0
,n
=
2
[1
1
2
[1
−
(1
−
p
c
)
n
]
<
0
.
5.
If watermark detection is applied to unmarked data using each of
n
differ-
ent valid secret keys
−
(1
−
K
n
, then the probability that at least one valid
watermark is detected, or the false hit rate, is 1
K
1
,...,
;
ω,
0
.
5))
n
,
−
(1
−
B
(
τω
assuming that
ω
bits are detected for each watermark.
The false miss rate can be analyzed under a typical modification attack in
which an attacker randomly toggles each least significant bit with a probability
p<
0
.
5. Under this attack, the probability that the
n
1
-th watermark cannot
be detected from the modified data, or the false miss rate, is
B
(
ω
−
τω
−
1;
ω, p
n
1
,n
(1
p
n
1
,n
)
p
). The reason is that after modification, each
mark bit of the
n
1
-th watermark could be modified either due to watermark
−
p
)+(1
−
