Databases Reference
In-Depth Information
When fingerprint detection is applied to unmarked data, it may return some
binary string (
f
0
,...f
−
1
) as a potential fingerprint. Let
f
i
be extracted
ω
i
times from data. Then,
f
i
is detected to be zero or one with the same proba-
bility
B
(
;
ω
i
,
0
.
5). The fingerprint scheme detects a binary string as a po-
tential fingerprint with probability
−
1
τω
i
;
ω
i
,
0
.
5), where the factor
2 means that each bit could be either zero or one. Let
N
be the total number
of valid fingerprints. The probability that the binary string is a valid finger-
print is
i
=0
2
B
(
τω
i
2
−
1
N
2
. The overall misdiagnosis false hit is
N
i
=0
2
B
(
τω
i
;
ω
i
,
0
.
5) =
·
−
1
N
N
2
,
which is tight in the case that all
ω
i
are odd and
τ
=0
.
5. The upper bound
is independent of the size of the database relation being checked.
The misattribution false hit and false miss rates can be analyzed un-
der a typical modification attack in which an attacker randomly flips ev-
ery least significant bit with a probability
p<
0
.
5 in fingerprinted data.
For the detection algorithm to extract a binary bit for fingerprint bit
f
i
,
either at most
ω
i
−
i
=0
B
(
τω
i
;
ω
i
,
0
.
5). The misdiagnosis false hit has upper bound
τω
i
−
1 of its embedded bits are toggled, or more than
of its embedded bits are toggled. If the detection algorithm extracts
a binary string, the probability that the binary string is a valid but “in-
nocent” fingerprint is
τω
i
N
1
2
. Therefore, the false misattribution false hit is
−
N
−
1
2
Π
−
1
N
−
1
i
=0
(1
−
B
(
ω
i
−
τω
i
−
1;
ω
i
,p
)+
B
(
τω
i
;
ω
i
,p
))
≤
2
. The mis-
N
−
1
attribution false hit rate has an upper bound
since
B
(
τω
i
;
ω
i
,p
)
≤
2
B
(
ω
i
−
0
.
5. The upper bound is tight in the case
that all
ω
i
are odd and
τ
=0
.
5. It is straightforward to get the false miss rate
τω
i
−
1;
ω
i
,p
) when
τ
≥
Π
−
1
1
−
i
=0
(1
−
B
(
ω
i
−
τω
i
−
1;
ω
i
,p
))
−
N
−
1
Π
−
1
i
=0
(1
−
B
(
ω
i
−
τω
i
−
1;
ω
i
,p
)+
B
(
τω
i
;
ω
i
,p
))
.
2
Π
−
1
where 1
−
i
=0
(1
−
B
(
ω
i
−
τω
i
−
1;
ω
i
,p
)) is the probability that the entire
fingerprint is detected incorrectly.
Fingerprinting schemes are susceptible to collusion attacks. A collusion at-
tack is launched by a coalition who has access to different fingerprinted copies
of the same data. Members of a coalition can identify the differences in their
fingerprinted copies, change the identified values to damage the correspond-
ing fingerprint bits, and create a useful data copy that does not implicate any
member of the coalition. Note that the collusion attack is specific to finger-
printing and there is no collusion attack in watermarking setting.
To thwart collusion attacks, the fingerprint codes need to be carefully de-
signed so that information that a coalition cannot detect can be used to trace
at least one of the traitors. Such fingerprinting codes have been rigorously
studied in the literature of cryptography. A well-known fingerprinting code,
called BoSh code (Boneh and Shaw [3]), is designed to be
c
-secure with
-error,
as it enables the capture of a member of a coalition of at most
c
members with
probability at least 1
, where
c
and
are two design parameters (increasing
c
or reducing
will result in longer BoSh codes).
−
