Databases Reference
In-Depth Information
1) totalcount = matchcount = 0
2)
foreach
tuple
s ∈ S
do
3) seed
G
with
s.P
concatenated with
K
4)
if
(next(
G
)mod
γ
=0)
then
// tuple was marked
5) attribute index
i
=next(
G
)mod
ν
//
A
i
was marked
6) bit index
j
=next(
G
)mod
η
//
j
th
bit was marked
7) totalcount = totalcount + 1
8) matchcount = matchcount + match (next(
G
,
s.A
i
,
j
)
9)
τ
= threshold(totalcount,
α
)
10)
if
((matchcount
<τ
)
or
(matchcount
>
totalcount -
τ
))
then
11)
suspect piracy
12) match(random number
i
,value
v
,bitindex
j
)
return
integer
13)
if
(
i
is even)
then
return
1
if
the
j
th
least significant bit of
v
is 0
else return
0
14)
15)
else
return
1
if
the
j
th
least significant bit of
v
is 1
else return
0
16)
Fig. 5.
Watermark detection for the single-bit encoding of [1, 16].
This can be modeled by first fixing an acceptable value for the
significance
level α
(0
,
2
) such that the
∈
(0
,
1) and then computing a threshold
τ
∈
probability of
m<τ
or
m>ω
−
τ
under the null hypothesis is less than or
equal to
α
.
The authors discuss additional extensions and properties of the solution
including the following:
•
Incremental Updatability: Updates can be handled independently of the
existing watermark as the selection and marking criteria are self-sucient
and only depend on the primary key value.
•
Blind Watermarking: The method does not require the availability of the
un-watermarked data at detection time.
•
Varying Parameters: The assumption that any two attributes are marked
at the same rate can be removed. Different attributes can be marked at
different rates because the attributes may tolerate different error rates
and, if the rate parameters are secret, Mallory's task become even more
dicult. Additionally, the number of bits available for marking can be
varied from one attribute to another.
•
Relations Without Primary Keys: The authors also discuss extensions
aimed at handling the case of relations without primary keys. This is
an important problem as it has the potential to overcome the required
assumption of unchanged primary key values in the watermarked data
at detection time. In the case of no primary key, the authors propose to
designate another attribute, or a number of most significant bit-portions
of the currently considered one, as a primary key. This however presents
a significant vulnerability due to the very likely existence of duplicates
