Collusion-aware traitor tracing in multimedia fingerprinting using sparse signal approximation

We pose the problem of tracing traitors, who have colluded to circumvent a multimedia fingerprinting system, as a sparse underdeter-mined linear problem. We propose a range of detection algorithms, based on sparse signal approximation, that span a tradeoff between performance and complexity. These algorithms are superior to conventional detection by correlation because they are collusion-aware. The simplest algorithm among them is more expensive than correlation by only a constant factor, and the second simplest one is more expensive by only a factor linear in the maximum number of traitors. We demonstrate that our proposed algorithms extend the robustness of already deployed fingerprinting schemes under both linear and nonlinear collusion attacks. For example, roughly twice as many traitors can be traced reliably than by using correlation, under mean or median collusion followed by compression.