Randomised dynamic traitor tracing

Dynamic traitor tracing schemes are used to trace the source of piracy in broadcast environments such as cable TV. Dynamic schemes divide content into a series of watermarked segments that are then broadcast. The broadcast provider can adapt the watermarks according to the pirate's response and eventually trace him/her. As dynamic algorithms are deterministic, for a given set of inputs, the tracing algorithm will execute exactly the same way each time. An adversary can use this knowledge to ensure that the tracing algorithm is forced into executing at its worst case bound. In this paper we review dynamic traitor tracing schemes and describe why determinism is a problem. We amend several existing dynamic tracing algorithms by incorporating randomised decisions. This eliminates any advantage an adversary has in terms of the aforementioned attack, as he/she no longer knows exactly how the tracing algorithm will execute. Simulations show that the randomising modifications influence each dynamic algorithm to run at its average case complexity in terms of tracing time. We provide an efficiency analysis of the amended algorithms and give some recommendations for reducing overhead