DIMACS TR: 2001-52

Digital fingerprinting codes: Problems statements, constructions, identification of traitors

Authors: A. Barg, G. R. Blakley, and G. Kabatiansky


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