text: We study the large-coalition asymptotics of fingerprinting and group testing and derive explicit decoders that provably achieve capacity for many of the considered models. We do this both for simple decoders (which are fast but commonly require larger code lengths) and for joint decoders (which may be slower but achieve the best code lengths). We further make the distinction between informed decoding, where the pirate strategy is exactly known, and uninformed decoding, and we design decoding schemes for both settings. For fingerprinting, we show that if the pirate strategy is known, the Neyman-Pearson-based log-likelihood decoders provably achieve capacity, regardless of the strategy. The decoder built against the interleaving attack is further shown to be a universal decoder, able to deal with arbitrary attacks and achieving the uninformed capacity. This universal decoder is shown to be closely related to the Lagrange-optimized decoder of and the empirical mutual information decoder of Moulin. Joint decoders are also proposed, and we conjecture that these also achieve the corresponding joint capacities. For group testing, the simple decoder for the classical model is shown to be more efficient than the one of and it provably achieves the simple group testing capacity. For generalizations of this model such as noisy group testing, the resulting simple decoders also achieve the corresponding simple capacities.
  @cite_38: We investigate alternative suspicion functions for bias-based traitor tracing schemes, and present a practical construction of a simple decoder that attains capacity in the limit of large coalition size @math . We derive optimal suspicion functions in both the restricted-digit model and the combined-digit model. These functions 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 codelength scaling @math changes to a lower power of @math , e.g., @math . We find that the interleaving strategy is an especially powerful attack. The suspicion function tailored against interleaving is the key ingredient of the capacity-achieving construction.
  @cite_26: 
  @cite_4: 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.
  @cite_22: 
  @cite_21: 
  @cite_1: 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.
  @cite_31: The class of joint decoder in fingerprinting codes is of utmost importance in theoretical papers to establish the concept of fingerprint capacity. However, no implementation supporting a large user base is known to date. This paper presents an iterative decoder which is the first attempt toward practical large-scale joint decoding. The discriminative feature of the scores benefits on one hand from the side-information of previously found users, and on the other hand, from recently introduced universal linear decoders for compound channels. Neither the code construction nor the decoder makes assumptions about the collusion size and strategy, provided it is a memoryless and fair attack. The extension to incorporate soft outputs from the watermarking layer is straightforward. An extensive experimental work benchmarks the very good performance and offers a clear comparison with previous state-of-the-art decoders.
  @cite_13: We study the Tardos' probabilistic fingerprinting scheme and show that its codeword length may be shortened by a factor of approximately 4. We achieve this by retracing Tardos' analysis of the scheme and extracting from it all constants that were arbitrarily selected. We replace those constants with parameters and derive a set of inequalities that those parameters must satisfy so that the desired security properties of the scheme still hold. Then we look for a solution of those inequalities in which the parameter that governs the codeword length is minimal. A further reduction in the codeword length is achieved by decoupling the error probability of falsely accusing innocent users from the error probability of missing all colluding pirates. Finally, we simulate the Tardos scheme and show that, in practice, one may use codewords that are shorter than those in the original Tardos scheme by a factor of at least 16.
  @cite_20: Over discrete memoryless channels (DMC), linear decoders (maximizing additive metrics) afford several nice properties. In particular, if suitable encoders are employed, the use of decoding algorithms with manageable complexities is permitted. For a compound DMC, decoders that perform well without the channel's knowledge are required in order to achieve capacity. Several such decoders have been studied in the literature, however, there is no such known decoder which is linear. Hence, the problem of finding linear decoders achieving capacity for compound DMC is addressed, and it is shown that under minor concessions, such decoders exist and can be constructed. A geometric method based on the very noisy transformation is developed and used to solve this problem.
  @cite_11: 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.
summary: Based on channel capacities, Amiri and Tardos @cite_1 and Huang and Moulin @cite_11 independently derived the optimal leading constant to be @math (i.e. an asymptotic code length of @math ) and many improvements to Tardos's original scheme were made @cite_13 @cite_26 @cite_21 @cite_22 to reduce the leading constant from @math to @math . Recently it was shown that with Tardos' original score function' one cannot achieve capacity @cite_4 , which lead to the study of different score functions. Based on a result of Abbe and Zheng @cite_20 , Meerwald and Furon @cite_31 noted that a score function designed against the worst-case attack achieves capacity against arbitrary attacks. This also lead to a proposal for a capacity-achieving score function in @cite_38 , which achieves the lower bound on the leading constant of @math .