Databases Reference
In-Depth Information
In watermark detection, a group of
q
k
tuples are selected and the order
π
of
their tuple hash values is identified, where
π
is a permutation of (0
,...,q
k
−
1).
A watermark
W
can be derived from
π
using Myrvold and Ruskey's linear
permutation ranking algorithm [19]:
1. let
π
−
1
be a binary vector such that
π
−
1
[
π
[
i
]] =
i
for
i
=0
,...q
k
−
1
2.
W
=rank(
q
k
,π,π
−
1
) // see lines 4-7 below
3. return
W
in binary form
4. function rank(
q
k
,π,π
−
1
)
5. if
q
k
= 1 then return 0
6.
s
=
π
[
q
k
−
1] and
π
[
π
−
1
[
q
k
−
1]]; swap
π
−
1
[
s
]and
π
−
1
[
q
k
−
1]; swap
π
[
q
k
−
1]
1
,π,π
−
1
)
7. return
s
+
q
k
∗
rank(
q
k
−
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. If
W
matches
W
,
the tuples in this group are authentic; otherwise, the data in this group have
been modified or tampered with.
4 Sensitivity
Watermarking schemes can be classified to be either
robust
or
fragile
according
to their sensitivity to typical database attacks. A scheme is robust (fragile,
respectively) if it is dicult to make an embedded watermark undetectable
(unchanged, respectively) in the presence of database attacks, provided that
the attacks do not degrade the usefulness of the data significantly (otherwise,
there is no need to protect the data nor to detect the watermark). Robust
watermarks are usually used for copyright protection, ownership proof, or
traitor tracing, while fragile watermarks can be used for tamper detection
and localization.
Typical database attacks
To confuse watermark detection, various database attacks may be launched
to watermarked databases. Typical database attacks include
tuple/ attribute
insertion/ deletion/ reorganization, value modification/ suppression
(includ-
ing random/ selective bit-flipping/ value-rounding),
invertibility attack
(at-
tacker successfully discovers a fictitious watermark which is in fact a random
occurrence from a watermarked database),
additive attack
(attacker embeds
some additional watermarks into a watermarked database), and the
brute-
force attack
against the secret key. The brute-force attack can be thwarted by
assuming that the key is long enough (e.g., 160 bits) in watermarking.
