We give a generic divide-and-conquer approach for constructing collusion-resistant probabilistic dynamic traitor tracing schemes with larger alphabets from schemes with smaller alphabets. This construction offers a linear tradeoff between the alphabet size and the codelength. In particular, we show that applying our results to the binary dynamic Tardos scheme of leads to schemes that are shorter by a factor equal to half the alphabet size. Asymptotically, these codelengths correspond, up to a constant factor, to the fingerprinting capacity for static probabilistic schemes. This gives a hierarchy of probabilistic dynamic traitor tracing schemes, and bridges the gap between the low bandwidth, high codelength scheme of and the high bandwidth, low codelength scheme of Fiat and Tassa.
Besides constructions of traitor tracing schemes, several papers have also investigated theoretical bounds on the codelength needed to catch a certain number of colluders. So far, these have all focused on probabilistic static schemes. Tardos @cite_9 showed that his codelength is optimal up to a constant factor. Huang and Moulin @cite_0 gave the exact capacity of the binary fingerprinting game, by showing that for large @math , a codelength of @math is both necessary and sufficient. This was then extended to the @math -ary setting independently by Boesten and S kori ' c @cite_13 and Huang and Moulin @cite_11 , showing that the @math -ary capacity corresponds to @math bits of information, or a codelength of @math symbols from a @math -ary alphabet.
@cite_0 @cite_9 @cite_13 @cite_11
1991439166 2083594366 2145102561 2129115163
We give a generic divide-and-conquer approach for constructing collusion-resistant probabilistic dynamic traitor tracing schemes with larger alphabets from schemes with smaller alphabets. This construction offers a linear tradeoff between the alphabet size and the codelength. In particular, we show that applying our results to the binary dynamic Tardos scheme of leads to schemes that are shorter by a factor equal to half the alphabet size. Asymptotically, these codelengths correspond, up to a constant factor, to the fingerprinting capacity for static probabilistic schemes. This gives a hierarchy of probabilistic dynamic traitor tracing schemes, and bridges the gap between the low bandwidth, high codelength scheme of and the high bandwidth, low codelength scheme of Fiat and Tassa. We study a fingerprinting game in which the number of colluders and the collusion channel are unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maximin games with mutual information as their payoff functions. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprinting alphabet is binary, we show that capacity decays quadratically with k. Furthermore, we prove rigorously that the asymptotic capacity is 1 (k221n2) and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotics, numerical solutions to the game for small k are also presented. For the Tardos traitor tracing scheme, we show that by combining the symbol-symmetric accusation function of ? with the improved analysis of Blayer and Tassa we get further improvements. Our construction gives codes that are up to four times shorter than Blayer and Tassa's, and up to two times shorter than the codes from ? Asymptotically, we achieve the theoretical optimal codelength for Tardos' distribution function and the symmetric score function. For large coalitions, our codelengths are asymptotically about 4.93 of Tardos' original codelengths, which also improves upon results from We investigate alternative suspicion functions for Tardos traitor tracing schemes. In the simple decoder approach (computation of a score for every user independently) we derive suspicion functions that optimize a performance indicator related to the sufficient code length l in the limit of large coalition size c. Our results hold for the Restricted-Digit Model as well as the Combined-Digit Model. The scores depend on information that is usually not available to the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such results can be used in realistic contexts. We study several combinations of coalition attack strategy versus suspicion function optimized against some attack (another attack or the same). In many of these combinations the usual scaling l c2 is replaced by a lower power of c, e.g. c3 2. We find that the interleaving strategy is an especially powerful attack, and the suspicion function tailored against interleaving is effective against all considered attacks.