Databases Reference
In-Depth Information
BoSh codes can be adapted such that for each user, the owner of a database
can generate a
c
-secure and
-error BoSh code using a secret key and the
user's identification information [17]. If this BoSh code is directly used as a
fingerprint, the misdiagnosis false hit rate will be 100 percent, as the tracing
algorithm proposed in [3] returns exactly one “traitor” no matter what the
input is (the assumed input in [3] is pirated data under collusion attacks). The
solution to reduce the misdiagnosis false hit is to partition each fingerprint
F
of
bits into two parts. The first part,
F
1
of
1
bits, is used as a multi-bit
watermark, while the second part,
F
2
of
2
bits, is the adapted BoSh code
generated from a secret key and a user's identification information. The entire
fingerprint
F
1
|F
2
of length
=
1
+
2
is embedded into a data copy as in
a multi-bit watermarking scheme. For fingerprint detection, a binary string
F
=
F
is extracted from a suspicious data copy also as in a multi-bit watermarking
scheme. From the extracted fingerprint template
F
1
is
first checked against the codeword used in fingerprint insertion. If there is a
single bit mismatch, the detection procedure returns none suspected. If the
watermark part passes the first phase examination, the fingerprint part
F
, its watermark part
F
2
will become the input of the tracing algorithm proposed in [3] for identifying
a traitor.
If fingerprint detection is applied to a pirated data copy in the presence
of a collusion attack only, the watermark part can be detected correctly. This
is because the collusion attack can only change the values if the coalition has
data copies that differ in those values. Then, the fingerprint part is fed into
the tracing algorithm proposed by Boneh and Shaw [3]. The tracing algorithm
will return exactly one buyer with a probability that this returned buyer is
indeed a traitor in the coalition being greater than 1
,asprovedin[3].In
such a case, the false miss rate is zero, and misattribution false hit is no larger
than
.
Now, consider the misdiagnosis false hit when fingerprint detection is ap-
plied to unmarked data. Note that the watermark part is the same for all users
and it is examined first in the detection process. The probability of detect-
ing a binary string for the watermark part is
Π
1
−
1
i
=0
−
;
ω
i
,
0
.
5). Now
there is only one valid watermark codeword. Thus, the probability that the
detected binary string matches the watermark codeword is
2
B
(
τω
i
1
2
1
. Since when-
ever watermark detection succeeds, fingerprint detection returns exactly one
valid buyer's identity, the misdiagnosis false hit is
2
1
Π
1
−
1
1
i
=0
2
B
(
τω
i
;
ω
i
,
0
.
5)
=
Π
1
−
1
1
1
2
1
. The upper
bound is tight in the case that all
ω
i
are odd and
τ
=0
.
5. The misdiagnosis
false hit rate can be reduced exponentially by increasing
1
; it can also be
decreased by increasing
τ
.
It should be noted that length of a collusion resistant fingerprint is quite
long even for small
c
and moderate
. (All collusion resistant fingerprints
are intrinsically long and there is no significant improvement in this regard
to BoSh codes so far.) For example, for
c
= 2 (where at most two buyers
i
=0
B
(
τω
i
;
ω
i
,
0
.
5)
≤
2
1
, which has an upper bound
