Databases Reference
In-Depth Information
order of attributes. Based on the primary key hash values, all tuples are se-
curely divided into
g
groups. The grouping is only a virtual operation, which
means that it does not change the physical position of the tuples. After group-
ing, all tuples in each group are sorted according to their primary key hash.
Like grouping, the sorting operation does not change the physical position of
tuples either. Each group is then watermarked independently.
Algorithm 2 shows the embedding process in each group. A (keyed) group
hash value is computed based on the tuple hash values in a sorted order.
A watermark, the length of which is equal to the number of tuple-pairs in
the current group, is extracted from the group hash value. To embed the
watermark, for each tuple pair, the order of the two tuples are changed or
unchanged (physically in the original database) to represent a corresponding
watermark bit 1 or 0, where 0 is encoded by the ascendant order and 1 by the
descendant order. Since only the order of the tuples is changed, the watermark
insertion does not introduce any error to the underlying data.
Algorithm 1
Watermark embedding
1: For all
k
=1
,...g
,
q
k
=0
2:
for
i
=1to
η
do
3:
h
i
=
HMAC
(
K,r
i
) // tuple hash
4:
h
i
=
HMAC
(
K,r
i
.P
) // primary key hash
5:
k
=
h
i
mod
g
6:
r
i
→G
k
// Virtual operation: assign tuple
r
i
to group
k
7:
q
k
++
8:
end for
9:
for
k
=1to
g
do
10:
G
k
// See algorithm 2
watermark embedding in
11:
end for
Algorithms 3 and 4 describe the watermark detection process. As in wa-
termark insertion, the primary key hash is computed for each tuple and all
tuples are divided into groups. Each group is processed independently. In a
group, the tuples are first sorted according to their primary key hash values.
Like watermark insertion, the sorting is a virtual operation and does not in-
volve order change of any tuples. Based on the tuple hash of the sorted tuples,
a group hash value is computed. Then, a watermark
W
is extracted from the
group hash. The watermark
W
is the one that is supposed to have been em-
bedded if the underlying data were watermarked. On the other hand, a binary
string
W
is extracted from the tuples in this group. For every tuple pair, if
their tuple hash values are in ascendant order, the corresponding bit in
W
is
extracted to be zero; otherwise, it is one. If
W
matches
W
, the data in the
group are authentic; otherwise, the data in this group have been modified or
tampered with.
