Databases Reference
In-Depth Information
Algorithm 4
Watermark verification in
G
k
1: sort tuples in
G
k
in ascendant order according to their primary key hash //
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 in Algorithm 2
4:
for
i
=1
,i<q
k
,i
=
i
+2
do
5:
if
h
i
≤ h
i
+1
then
6:
W
[
i/
2] = 0
7:
else
8:
W
[
i/
2] = 1
9:
end if
10:
end for
11:
if
W
==
W
then
12:
V
=
TRUE
13:
else
14:
=
F ALSE
15:
end if
V
The embedding capacity can be further increased such that at most ln
q
k
!
bits can be embedded into each group of
q
k
selected tuples. The increase in
embedding capacity is illustrated in Table 1.
Table 1.
Embedding capacity
q
k
10 20 30 40 50 60 70 80 90 100
q
k
/
2 5 10 15 20 25 30 35 40 45 50
ln
q
k
! 15 42 74 110 148 188 230 273 318 363
is calculated the
same way as in Algorithm 2. Then, a watermark
W
=
extractBits
(
Given a group of
q
k
selected tuples, a group hash
H
H
,
ln
q
k
!)
of length ln
q
k
! is derived from
. The watermark
W
is embedded into this
group by permuting the order of the tuples. The new order
π
can be easily cal-
culated using Myrvold and Ruskey's linear permutation unranking algorithm
[19] based on
W
:
H
1.
π
=(0
,...,q
k
−
1)
2. unrank(
q
k
,W,π
) // see lines 4-5 below
3. return
π
4. function unrank(
q
k
,W,π
)//
W
is in integer form
5. if
q
k
>
0 then swap
π
[
q
k
−
,π
)
The tuples in this group are re-arranged such that
π
indicates the order of
their tuple hash values.
1] and
π
[
W
mod
q
k
]; unrank(
q
k
−
1
,
W/q
k
