Databases Reference
In-Depth Information
Algorithm 5
Generating public watermark
W
for DB relation
R
1:
for
each tuple
r
in
R
do
2:
construct a tuple
t
in
W
with the same primary key
t.P
=
r.P
3:
for
i=0; i
<ϑ
; i= i+1
do
j
=
S
i
mod (the number of attributes in
r
)//
S
is seeded with
K
and
4:
r.P
.
5:
t.W
i
= MSB of the
j
-th attribute in
r
6: delete the
j
-th attribute from
r
7:
end for
8:
end for
9: return
W
W
ϑ−
1
), where
W
0
,...,W
ϑ−
1
are binary attributes. Compared to DB relation
R
, the watermark (relation)
W
has the same number
η
of tuples and the same
primary key attribute
P
. The number
ϑ
of binary attributes in
W
,whichis
called the watermark generation parameter, determines the number
ω
of bits
in
W
, where
ω
=
η
ν
.
The process of generating watermark
W
is shown in Algorithm 5. The
MSBs of selected values are used for generating the watermark. The whole
process does not introduce any distortions to the original data. The use of
MSBs is for thwarting potential attacks that modify the data. Since the wa-
termark key
K
, the watermark
W
, and the watermark generation algorithm
are publicly known, anyone can locate those MSBs in
R
that are used for
generating
W
. However, an attacker cannot modify those MSBs without in-
troducing intolerable errors to the data.
In the construction of watermark
W
, each tuple in relation
R
contributes
ϑ
MSBs from different attributes that are pseudo-randomly selected based
on the watermark key and the primary key of the tuple. It is impossible for
an attacker to remove all of the watermark bits by deleting some but not all
of the tuples and/or attributes from the watermarked data. The larger the
watermark generation parameter
ϑ
, the more robust the scheme is against
such deletion attacks.
In watermark detection, as in watermark generation, the MSB bits of
ϑ
val-
ues from each tuple are located based on the watermark key and the primary
key. Based on the primary key values (which are assumed to not change or
else can be recovered), the detected MSBs are compared to the corresponding
bits in the public watermark
W
. The ownership is claimed if the percentage of
the matches is more than a threshold
τ
·
ϑ
and
ϑ
≤
0
.
5, where
τ
is called the watermark
detection parameter. The watermark detection parameter is used to balance
between false hit and false miss.
It can be assumed that each MSB in
W
has the same probability of 1
/
2to
be 1 or 0. If this is not the case, one can randomize the MSBs in
W
by XOR'ing
them with pseudo-random mask bits. The mask bits can be computed from
the watermark key together with the primary key for each tuple. With this
assumption, the false hit rate (i.e., the probability of claiming ownership over
≥
