Cryptography Reference
In-Depth Information
have reasonable length for some applications; it is of course outperformed by
the Tardos code that has length almost the square root of `.
1.5 Bibliographic Notes
The concept of fingerprinting codes was first studied in [ 120 ]. An early work
is by Blakley et al. [ 15 ] presented a construction resilient against larger coali-
tions. Fingerprinting codes were implicit in the work of [ 28 ] that focused on
combinatorial tools in the design of traitor tracing schemes (cf. the extended
version of this work in [ 29 ]). Subsequent works on improving the code con-
structions have been very much related to the concept of traitor tracing. Still
the two notions, of fingerprinting and traitor tracing, are distinct and are pre-
sented separately here. We also opted to use the term “Identify” to name one
of the essential algorithms of fingerprinting instead of “tracing” that has been
used occasionally in the literature due to the relation to traitor tracing [ 28 ].
The formalization of the problem of designing fingerprinting codes is due
to Boneh and Shaw [ 23 ] who also introduced the first family of fingerprinting
codes over a binary alphabet that is collusion-resistant against any coalition
size. In following works an improvement in the length code — but not asymp-
totically - was made by Lindkvist [ 81 ] and an e cient implementation was
designed by Yacobi [ 126 ]. A restricted case lower bound was given in [ 93 ].
Tardos's collusion-secure probabilistic fingerprinting codes were presented
in [ 115 , 116 ]) along with a matching lower bound. In this chapter we described
the Tardos' codes distribution with a slightly modified “symmetric” variant
of the accompanying tracing algorithm where both 0's and 1's account in the
penalty function (Tardos originally employs only 1's for this purpose). We note
that asymptotically there is no difference in the performance of the original
tracing procedure and the present variant; still the presentation and analysis
is somewhat differently laid out. Tardos codes use a continuous probability
distribution for codeword generation which can lead to di culties in an im-
plementation. Obviously in practice only approximations can be achieved that
would affect the security and e ciency aspects of the code. In [ 92 ] a related
code distribution was shown that is discretized.
Fingerprinting codes in this chapter were shown under the marking as-
sumption. Enforcing the marking assumption in practice can be achieved
through methods related to watermarking see e.g., [ 30 ]. Still, the assump-
tion can be problematic at times depending on the underlying content that is
marked. If the marking assumption collapses then the fingerprinting system
that relies on the assumption would collapse as well, i.e., it will be unable to
identify the source of a signal or possibly present wrongful accusations.
We note that attacks against the marking assumption in the context of
watermarking have been shown in practice, see e.g., the work of Kirovski
and Petitcolas [ 73 ]. To address such issues various extensions of the marking
assumption have been identified in specific contexts. For example, Guth and
Search WWH ::




Custom Search