The Tardos scheme is a well-known traitor tracing scheme to protect copyrighted content against collusion attacks. The original scheme contained some suboptimal design choices, such as the score function and the distribution function used for generating the biases. previously showed that a symbol-symmetric score function leads to shorter codes, while obtained the optimal distribution functions for arbitrary coalition sizes. Later, showed that combining these results leads to even shorter codes when the coalition size is small. We extend their analysis to the case of large coalitions and prove that these optimal distributions converge to the arcsine distribution, thus showing that the arcsine distribution is asymptotically optimal in the symmetric Tardos scheme. We also present a new, practical alternative to the discrete distributions of and give a comparison of the estimated lengths of the fingerprinting codes for each of these distributions.
Besides practical constructions of traitor tracing schemes, some papers have also studied absolute lower bounds on the asymptotic code lengths that any secure traitor tracing scheme must satisfy. Huang and Moulin @cite_8 and Amiri and Tardos @cite_2 showed that for large @math , the code length constant of any scheme must satisfy @math , but no practical constructions of schemes achieving this lower bound are known. Huang and Moulin did show that this lower bound is tight, and that in the related min-max game between the traitors and the tracer, the optimal pirate strategy is to use the interleaving attack, and the optimal tracing strategy is to use a Tardos-like code with biases distributed according to the arcsine distribution. Note that this does not say anything about specific schemes such as the Tardos scheme, for which the related min-max games are different and may lead to a completely different optimal pirate strategy and tracing strategy.
@cite_2 @cite_8
1560505065 2083594366
Including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. Codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes. In this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. We conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. We prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes. On the downside the accusation algorithm of our codes are much slower than those of earlier codes. We introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. We construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. In fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound. Using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. To our surprise these rates asymptotically agree, that is, their ratio tends to 1 as t goes to infinity. Although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do. 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.