Dynamic Traitor Tracing
Traitor tracing schemes we re introduced by Chor, Fiat and Naor in 1994 in order to combat piracy in broadcast environments. In a typical piracy scenario, pirate decoders are manufactured and sold by pirates to illegal users. Traitor tracing schemes (that, in other contexts, are referred to as watermarking, frameproof, or parent-identifying codes) offer methods for fingerprinting each decoder in such a way that the fingerprint of an illegal decoder would enable the tracing of at least one of its "parents". Those schemes, however, are ineffective in dynamic piracy scenarios: As the data provider supplies access control keys to its legal users on a periodical basis, a number of these users may collude in order to publish those keys via the Internet or any other network. We introduce the concept of dynamic traitor tracing. Dynamic traitor tracing schemes rely on the feedback from the pirate network in order to modify their key allocation until they are able to incriminate and disconnect all traitors, or force them to stop their illegal activity. Those schemes are deterministic in the sense that incrimination is certain. In addition, we describe probabilistic schemes that trace all traitors with an almost certainty while imposing a small penalty on bandwidth consumption, and analyze their convergence time.
Part of this work was done in collaboration with Amos Fiat.