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

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/sup 1/2/)) and for this probability support at most exp(O(n/sup 1/2/)) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n)=polylog(M), 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, for which the distributor can either recover both users from the coalition with probability 1-exp((omega)(n)), or identify one traitor with probability 1.