Databases Reference
In-Depth Information
value is thus selected by the secret key
k
1
, the associated relational primary
key value and a corresponding bit from the watermark data
wm data
.
In the decoding phase (see Figure 13), the first aim is to discover the
embedded
wm data
bit string. The same criteria for discovering “fit” tuples
is used. For each “fit” tuple
T
i
, with
T
i
(
A
)=
a
t
, its corresponding entry in
the result bit string is set to (
t
&1)
wm data
[
msb
(
H
(
T
j
(
K
)
,k
2
)
,b
(
N
e
))]
←
(
t
&1)
Once
wm data
(possibly altered) is available, the error correcting mechanism
is invoked to generate the “closest”, most likely, corresponding watermark
wm
=
ECC.decode
(
wm data
,
|
wm
|
).
wm dec alt
(
K
,
A
,
k
1
,
e
,ECC,
embed map
)
for
(
j ←
1;
j<N
;
j ← j
+1)
if
(
H
(
T
j
(
K
)
,msb
(
k, b
(
K
))) mod
e
=0)
then
determine
t
such that
T
j
(
A
)=
a
t
wm data
[
embed map
[
T
j
(
K
)]] =
t
&1
wm ← ECC.decode
(
wm data, wm.length
)
return
wm
Fig. 13.
Decoding Algorithm (alternative using embedding map shown)
The authors propose a natural extension to the above solution aimed at
defeating vertical partitioning attacks (
A1.b
). Instead of relying on the as-
sociation between the primary key and
A
, the extended algorithm considers
all
pairs of attributes and embeds a watermark separately in
each
of these
associations. Additionally, if data constraints allow, the authors propose wa-
termarking each and every attribute pair by first building a closure for the
set of attribute pairs over the entire schema that minimizes the number of
encoding interferences while maximizing the number of pairs watermarked.
To solve the issue of interference, maintaining a mark “interference graph” is
proposed.
The proposed extension features a particular issue of concern in certain
cases of multi-attribute embeddings where two non-key attributes are used
in the encoding, i.e., mark(A,B). Because of the correlation between the wa-
termarking alteration (the newly selected value
T
i
(
B
)=
b
t
) and its actual
location (determined by the fitness selection,
H
(
T
i
(
A
)
,k
1
)and
e
), sometimes
Mallory can mount a special attack with the undesirable result of revealing
some of the mark bit embedding locations. This occurs if the fitness criteria
decides that a particular value of
A
yields a tuple fit and that value of
A
