Dynamic subtree tracing and its application in pay-TV systems

A traitor tracing algorithm can be used to identify content decoders that are used in the process of committing piracy. Fiat and Tassa introduced the concept of dynamic traitor tracing. A dynamic traitor tracing algorithm is based on examining content, either rendered illegally by a decoder or re-broadcast by the pirate. In addition, real-time feedback from the pirate’s network is used to adapt the state of the algorithm. This results in very efficient schemes, measured by the number of iterations required to identify all traitors. Drawbacks of currently available dynamic traitor tracing algorithms are that the best-known, real-time computational cost and bandwidth usage depend linearly on the number of content decoders. In particular, for large populations of content decoders, for example, common in pay-TV applications, these schemes can become impractical as system requirements can no longer be fulfilled. This paper presents a new dynamic traitor tracing algorithm, referred to as dynamic subtree tracing. The new algorithm inherits the advantages of the previously presented dynamic schemes and eliminates their disadvantages. In particular, it is shown that the number of iterations, the computational cost, the bandwidth usage, and the amount of storage in a decoder are all logarithmic in the number of content decoders. This makes the new scheme attractive for application in pay-TV systems, as illustrated with numerical examples.