Databases Reference
In-Depth Information
the tuple belongs to. This would both alleviate the need to deploy subset
markers as well as likely offering more resilience to attacks. This simple and
nice improvement was suggested to one of the authors during a discussion with
a Purdue graduate student (whose identity he cannot remember but whom
he invites forward for credit) attending the 2005 Symposium on Security and
Privacy.
distribution(S
i
)
c
x
stdev(S
i
)
avg(S
i
)
S
i
V
c
(S
i
)
Fig. 7.
In the single-bit mark encoding convention, the encoding of the watermark
bit relies on altering the size of the “positive violators” set,
v
c
(
S
i
).
Once constructed, each separate subset
S
i
will be marked separately with
a single bit, in the order it appears in the actual watermark string. The result
will be a
e
-bit (i.e.,
i
=1
,...,e
) overall watermark bandwidth in which each
bit is “hidden” in each of the marked
S
i
. If the watermark is of size less than
e
, error correction can be deployed to make use of the additional bandwidth
to increase the encoding resilience.
The single-bit distribution encoding proceeds as follows. Let
b
be a water-
mark bit that is to be encoded into
S
i
and
represent a set of user specified
change tolerance, or usability metrics. The set
G
will be used to implement
the consumer-driven awareness in the watermark encoding.
Let
v
false
,
v
true
,
c
G
(0
,
1),
v
false
<v
true
be real numbers (e.g.,
c
= 90%,
v
true
= 10%,
v
false
= 7%).
c
is called
confidence factor
and the interval
(
v
false
,v
true
)
confidence violators hysteresis
. These are values to be remem-
bered also for watermark detection time. They can be considered as part of the
encoding key. Let
avg
(
S
i
)and
δ
(
S
i
) be the average and standard deviation,
respectively, of
S
i
.Given
S
i
and the real number
c
∈
(0
,
1) as above,
v
c
(
S
i
)is
defined as the
number of items of S
i
that are greater than avg
(
S
i
)+
c
∈
δ
(
S
i
).
v
c
(
S
i
) is called the number of positive “violators” of the
c
confidence over
S
i
,
see Figure 7.
The single-bit
mark encoding convention
is then formulated: given
S
i
,
c
,
v
false
and
v
true
as above,
mark
(
S
i
)
×
∈{
true,false,invalid
}
is defined to
be
true
if
v
c
(
S
i
)
>
(
v
true
×|
S
i
|
),
false
if
v
c
(
S
i
)
<v
false
×|
S
i
|
and
invalid
if
v
c
(
S
i
)
∈
(
v
false
×|
S
i
|
,v
true
×|
S
i
|
).
