Databases Reference
In-Depth Information
Algorithm 2
Watermark embedding in
G
k
1: sort tuples in
G
k
in ascendant order according to their primary key hash values//
Virtual operation
2:
H
=
HMAC
(
K,h
1
);
H
=
HMAC
(
K,H|h
2
);
... H
=
HMAC
(
K, H|h
q
k
)//
group hash, where
h
i
(
i
=1
, ···q
k
) is the tuple hash of the
i
th
tuple after ordering
3:
W
=
extractBits
(
H,q
k
/
2) // See lines 10-17
4:
for
i
=1
,i<q
k
,i
=
i
+2
do
5:
if
W
[
i/
2] == 1
then
6: switch the position of
r
i
and
r
i
+1
physically in DB
7:
end if
8:
end for
9:
10: function
extractBits
(
H,
)
{
11:
if
length(
H
)
≥
then
12: W = concatenation of first
selected bits from
H
// in most cases,
H
is longer
than
13:
else
14:
m
=
-length(
H
)
15:
W = concatenation of
H
and extractBits(
H
,
m
)
16:
end if
17: return
W
}
Algorithm 3
Watermark detection
1: For all
k
=1
,...g
,
q
k
=0
2:
for
i
=1to
η
do
3:
h
i
=
HMAC
(
K,r
i
)
4:
h
i
=
HMAC
(
K,r
i
.P
)
5:
k
=
h
i
mod
g
6:
r
i
→G
k
7:
q
k
++
8:
end for
9:
for
k
=1to
g
do
10: watermark verification in
G
k
// See algorithm 4
11:
end for
In this solution, the number
g
of groups is used to make a tradeoff between
security and localization. On the one hand, the smaller the value of
g
,the
larger the probability of detecting modifications in watermark detection, and
the more secure the proposed scheme. On the other hand, this leads to a larger
group size; thus, one can localize modifications less precisely as there are more
tuples in each group.
3.2 Embedding Capacity
Li, Guo, and Jajodia's scheme embeds one bit for each pair of selected
tuples; thus,
q
k
/
2 bits are embedded into each group of
q
k
selected tuples.
