DIMACS TR: 2001-52
Digital fingerprinting codes: Problems statements, constructions, identification of traitors
Authors: A. Barg, G. R. Blakley, and G. Kabatiansky
ABSTRACT
We consider a general fingerprinting problem of digital data under which
coalitions of users can alter or erase some bits in their copies in order
to create an illegal copy. Each user is assigned a fingerprint which is a
word in a fingerprinting code of size M (the total number of users) and
length n. We present binary fingerprinting codes secure against size-t
coalitions which enable the distributor (decoder) to recover at least one
of the users from the coalition with probability of error exp(-Omega(n))
for M=exp(Omega(n)). This is an improvement over the best known schemes
that provide the error probability no better than exp(-Omega(n^{1/2})) and
for this probability support at most exp(O(n^{1/2})) users. The
construction complexity of codes is polynomial in n. We also present
versions of these constructions that afford poly(n)=poly log(M)
identification algorithms of a member of the coalition, improving over the
best previously known complexity of Omega(M).
For the case t=2 we construct codes of exponential size with even stronger
performance, namely, the distributor can either recover both users from
the coalition with probability 1-exp(Omega(n)), or identifies one traitor
with probability 1.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-52.ps.gz
DIMACS Home Page