Databases Reference
In-Depth Information
5 Watermark Information
5.1 From One-Bit Watermark to Multiple Bit Watermark
Back to Agrawal and Kiernan's scheme, the watermark information that
is embedded is one-bit only given a predetermined embedding key. This can
be seen clearly by extending it to embedding a multiple bits watermark
W
=
(
w
0
,...,w
−
1
), as proposed by Li, Swarup, and Jajodia [15]. To embed
W
,the
same procedure as in Agrawal and Kiernan's scheme is used to: (i) select some
tuples; (ii) for each selected tuple
r
, select one numerical attribute; (iii) for
each selected attribute, select one of
ξ
least significant bits; and (iv) compute
a mark bit
x
for each selected bit. Now the difference is that the mark bit
x
is
not used directly to replace the selected least significant bit; instead,
w
i
XOR
x
is used to replace the selected bit, where
w
i
is a watermark bit selected
from
W
for
i
=
S
5
mod
(note that the first four random sequence numbers
S
1
∼S
4
generated for each tuple have already been used in Agrawal and
Kiernan's scheme). Similar to Agrawal and Kiernan's scheme, each watermark
bit is embedded multiple times and is detected with a majority vote (i.e., the
percentage of correctly detected bits should be greater than threshold
τ
).
The whole watermark
W
is correctly detected if every bit in
W
is correctly
detected. Agrawal and Kiernan's scheme is a special case of Li, Swarup, and
Jajodia's scheme where
W
is 1-bit zero.
Assume
ω
i
bits are extracted from the data for each watermark bit
w
i
in
watermark detection. When Li, Swarup, and Jajodia's multi-bit watermarking
scheme is applied to unmarked data, the false hit rate is
−
1
i
=0
B
(
τω
i
;
ω
i
,
0
.
5)
1
≤
2
(i.e., the probability of detecting a particular binary string of length
from unmarked data), where
τ
0
.
5 is the threshold in the majority vote.
This false hit rate is extremely low if the watermark string is long enough,
regardless of the value of
τ
. When the scheme is applied to watermarked data,
the false hit rate is
−
1
≥
;
ω
i
,
0
.
5) (i.e., the probability of any binary
string of length
can be detected from watermarked data). This false hit rate
can be made low by increasing the threshold
τ
. The false miss rate can be
analyzed under a typical modification attack in which an attacker randomly
flips every least significant bit with a probability
p<
0
.
5. Under this attack,
the false miss rate is 1
i
=0
2
B
(
τω
i
−
−
1
1;
ω
i
,p
)).
Another multi-bit watermark scheme was proposed by Sion, Atallah, and
Prabhakar [22]. The scheme is designed primarily for watermarking a set of
real numbers
i
=0
(1
−
B
(
ω
i
−
τω
i
−
by manipulating its distributions. The first step
of watermark insertion is to sort the values according to a cryptographically
keyed hash of the set of most significant bits of the normalized values. Then, a
maximum number of non-intersecting subsets of values are formed, where each
subset consists of a certain number of adjacent items after sorting. Embedding
a watermark bit into a subset is achieved by making minor changes to some
of the data values in this subset such that the number of values that are
“outliers” in the distribution is less than a smaller threshold (for watermark
{
x
1
,...x
n
}
