Title: Digital fingerprinting codes--problems, constructions and identification of traitors

Speaker: Alexander Barg, DIMACS

Date: February 4, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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$.

In the first part we discuss general properties of the problem and derive bounds on the error probability of identification.

Next 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 identification algorithms of complexity poly(n)=polylog(M). improving over the best previously known complexity of \Omega(M).

Technically the results rely upon the use of separating codes (a.k.a. secure frameproof codes), easy probabilistic arguments and algebraic list decoding.

Joint work with G. R. Blakley (T A&M U) and G. Kabatiansky (IPPI RAN, Moscow).