On Crafty Pirates and Foxy Tracers

Piracy in digital content distribution systems is usually identified as the illegal reception of the material by an unauthorized (pirate) device. A well known method for discouraging piracy in this setting is the usage of a traitor tracing scheme that enables the recovery of the identities of the subscribers who collaborated in the construction of the pirate decoder (the traitors). An important type of tracing which we deal with here is “black-box traitor tracing” which reveals the traitors’ identity using only black-box access to the pirate decoder. The only existing general scheme which is successful in general black-box traitor tracing was introduced by Chor Fiat and Naor. Still, this scheme employs a pirate decoder model that despite its generality it is not intended to apply to all settings. In particular it is assumed that (1) the pirate decoder is “resettable”, i.e. the tracer is allowed to reset the pirate decoder to its initial state after each trial (but in many settings this is not possible: the pirate decoder is “history-recording”), and that (2) the pirate decoder is “available”, i.e. it does not employ an internal reactive mechanism that, say, disables the tracing process (such as shutting down) — we will call such reactive decoders “abrupt”.In this work we discuss pirate-decoders of various types which we categorize according to their capabilities: resettable vs. history recording, and available vs. abrupt. These (crafty) pirate decoders of “enhanced capabilities” (compared to the model of Chor et al.) appear in many plausible piracy scenarios. We then present new (foxy) black-box traitor tracing schemes which cope with such pirate decoders. We present a generic black box traitor tracing technique against any abrupt/resettable decoder. This generic tracing method can be implemented readily in a linear ciphertext size traitor tracing scheme. By employing a new relaxation technique, which we call list-tracing, we describe a traitor tracing scheme with sublinear ciphertext size that is successful against abrupt/resettable pirate decoders. Finally, we present the first black-box traitor-tracing scheme and techniques that are successful against abrupt/history-recording pirate decoders (in the multimedia transmission setting).