Combining an information-theoretic approach to fingerprinting with a more constructive, statistical approach, we derive new results on the fingerprinting capacities for various informed settings, as well as new log-likelihood decoders with provable code lengths that asymptotically match these capacities. The simple decoder built against the interleaving attack is further shown to achieve the simple capacity for unknown attacks, and is argued to be an improved version of the recently proposed decoder of With this new universal decoder, cut-offs on the bias distribution function can finally be dismissed. Besides the application of these results to fingerprinting, a direct consequence of our results to group testing is that (i) a simple decoder asymptotically requires a factor 1.44 more tests to find defectives than a joint decoder, and (ii) the simple decoder presented in this paper provably achieves this bound.
Later work on the constructive side of fingerprinting focused on improving upon Tardos' result by sharpening the bounds @cite_10 @cite_16 , optimizing the distribution functions @cite_12 , improving the score function @cite_27 , tightening the bounds again with this improved score function @cite_4 @cite_26 @cite_17 @cite_40 @cite_20 @cite_43 , optimizing the score function @cite_39 , and again tightening the bounds with this optimized score function @cite_23 @cite_22 to finally end up with a sufficient asymptotic code length of @math for large @math . This construction can be extended to larger alphabets, in which case the code length scales as @math . Other work on practical constructions focused on joint decoders, which are computationally more involved but may work with shorter codes @cite_29 @cite_6 @cite_42 , and side-informed fingerprinting games @cite_31 @cite_45 @cite_32 @cite_0 , where estimating the collusion channel @math was considered to get an improved performance.
@cite_22 @cite_29 @cite_42 @cite_43 @cite_10 @cite_20 @cite_4 @cite_39 @cite_23 @cite_17 @cite_26 @cite_32 @cite_6 @cite_27 @cite_40 @cite_16 @cite_12 @cite_0 @cite_45 @cite_31
2092811336 2087879325 2168868689 2129115163 1969848549 1977832049 1541113101 2010291444
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. 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. 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. 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. We study the asymptotic-capacity-achieving score function that was recently proposed by for bias-based traitor tracing codes. For the bias function, we choose the Dirichlet distribution with a cutoff. Using Bernstein's inequality and Bennett's inequality, we upper bound the false-positive and false-negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size c0 and obtain asymptotic solutions for the cutoff, the sufficient code length, and the corresponding accusation threshold. We find that the code length converges to its asymptote approximately as c0?1 2 @math , which is faster than the c0?1 3 @math of Tardos' score function. MSC:94B60 Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for symmetric' coalition strategies. For binary alphabets and a false accusation probability @math , a code length of @math symbols is provably sufficient, for large c 0, to withstand collusion attacks of up to c 0 colluders. This improves Tardos' construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c 0, we show that even a code length of @math is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35 is achievable for q = 3 and 80 for q = 10. It is known that Tardos's collusion-secure probabilistic fingerprinting code (Tardos code) has length of theoretically minimal order. However, Tardos code uses certain continuous probability distribution, which causes that huge amount of extra memory is required in a practical use. An essential solution is to replace the continuous distributions with finite discrete ones, preserving the security. In this paper, we determine the optimal finite distribution for the purpose of reducing memory amount; the required extra memory is reduced to less than 1 32 of the original in some practical setting. Moreover, the code length is also reduced (to, asymptotically, about 20.6 of Tardos code), and some further practical problems such as approximation errors are also considered. This paper presents our recent works on multimedia fingerprinting, which consists in improving both the fingerprinting code and the watermarking scheme. The fingerprinting code is the well known Tardos code. Our contributions only focus on deriving a better accusation process. It appears that Tardos orginal decoding is very conservative: its performances are guaranteed whatever the collusion strategy. Indeed, major improvements stems from the knowledge of the collusion strategy. Therefore, this paper investigates whether it is possible to learn and adapt to the collusion strategy. This done with an iterative algorithm a la EM, where a better estimation of their strategy yields a better tracing of the colluders, which in return yields a better estimation of their strategy etc. The second part focuses on the multimedia watermarking scheme. In a previous paper, we already used the Broken Arrows' technique as the watermarking layer for multimedia fingerprinting. However, a recent paper from A. Westfeld discloses a flaw in this technique. We just present a counter-measure which blocks this security hole while preserving the robustness of the original technique.