Databases Reference
In-Depth Information
1)
foreach
tuple
r ∈ R
do
2) seed
G
with
r.P
concatenated with
K
3)
if
(next(
G
)mod
γ
=0)
then
// mark this tuple
4) attribute index
i
=next(
G
)mod
ν
// mark attribute
A
i
5) bit index
j
=next(
G
)mod
η
// mark
j
th
bit
6)
r.A
i
= mark(next(
G
),
r.A
i
,
j
)
7) mark(random number
i
,value
v
,bitindex
j
)
return
value
8)
if
(
i
is even)
then
set the
j
th
least significant bit of
v
to 0
9)
10)
else
set the
j
th
least significant bit of
v
to 1
11)
12)
return
v
Fig. 4.
Watermark insertion for the single-bit encoding of [1, 16].
the current tuple is to be watermarked (step 3), (ii) which attribute value to
mark (step 4), (iii) which bit within that attribute's value to alter (step 5),
and (iv) what new bit-value to assign to that bit-position in the result (step
6, invocation of mark()). This encoding guarantees that, in order to entirely
remove a watermark, Mallory is put in the position of guessing correctly the
marked tuples, attributes and altered bit positions.
Once
R
is published, the data owner, Alice, would like to determine
whether the (similar) relation
S
published by Mallory has been pirated from
R
. The sets of tuples and of attributes in
S
are assumed to be strict subsets
of those in
R
. Additionally, Mallory is assumed not to drop the primary key
attribute or change the value of primary keys. Then watermark detection is a
direct inverse of insertion. It proceeds as follows (see Figure 5).
Alice starts by identifying the bits that should have been marked by the
insertion algorithm. To do so, it executes the operations described in lines 1
through 5 of the insertion algorithm (steps 3 through 6). The assumption is
that the original database primary key is preserved in
S
. Each such identified
bit is tested for a match with the value that should have been assigned by the
insertion algorithm. Each match is counted. If the resulting count is either too
small or too large, piracy is suspected. In the case of too small a number, the
method assumes that somehow Mallory has identified the marked bits and
systematically flipped each one.
In other words, the insertion algorithm is modulated on a set of successive
independent coin tosses. A detection algorithm over
ω
bits will yield a number
of matches with a binomial distribution (
ω,
1
/
2) for the null hypothesis of non-
piracy. Naturally, in the absence of piracy, the expected number of matches is
ω
2
. The paper proposes to suspect piracy if the observed number of matches
m
is so large or so small that its probability under the null hypothesis is highly
unlikely.
